Рассмотри изображённые графы и заполни пропуски. В графе на рисунке А Выбери ответ эйлеров путь. В графе на рисунке Б Выбери ответ эйлеров путь.

Решение:

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

В графе на рисунке А:

• Степень вершины A: 2
• Степень вершины C: 2
• Степень вершины K: 3
• Степень вершины E: 3
• Степень вершины L: 2
• Степень вершины M: 2
• Степень вершины B: 3
• Степень вершины D: 3

В этом графе 4 вершины с нечётной степенью (K, E, B, D). Следовательно, в графе нет эйлерова пути или эйлеровой цепи.

В графе на рисунке Б:

• Степень вершины C: 4
• Степень вершины B: 2
• Степень вершины A: 3
• Степень вершины K: 2
• Степень вершины D: 4
• Степень вершины E: 3
• Степень вершины L: 2
• Степень вершины M: 2

В этом графе 2 вершины с нечётной степенью (A, E). Следовательно, в графе существует эйлеров путь, который начинается в одной из вершин с нечётной степенью (A или E) и заканчивается в другой.

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

Ответ:

В графе на рисунке А нет эйлеров путь.

В графе на рисунке Б есть эйлеров путь.