143 Какими цифрами на рисунке 37 обозначены эйлеровы графы?

Решение:

Эйлеров граф — это связный граф, в котором можно пройти по каждому ребру ровно один раз и вернуться в исходную вершину. Такое возможно, если все вершины графа имеют чётную степень. Если в графе есть ровно две вершины нечётной степени, то существует эйлеров путь (начинается в одной нечётной вершине и заканчивается в другой).

Рассмотрим рисунок 37:

• Граф под цифрой 1: пять вершин. Все вершины имеют степень 2 (чётная). Граф является эйлеровым.
• Граф под цифрой 2: четыре вершины. Все вершины имеют степень 2 (чётная). Граф является эйлеровым.
• Граф под цифрой 3: шесть вершин. Две вершины имеют степень 2 (чётная), две вершины имеют степень 3 (нечётная), две вершины имеют степень 4 (чётная). Так как в графе есть вершины с нечётной степенью (две вершины степени 3), то граф не является эйлеровым, но в нём существует эйлеров путь.
• Граф под цифрой 4: пять вершин. Две вершины имеют степень 2 (чётная), одна вершина имеет степень 3 (нечётная), две вершины имеют степень 4 (чётная). Так как в графе есть вершина с нечётной степенью, то граф не является эйлеровым, но в нём существует эйлеров путь.

Ответ: 1, 2