Вариант 1 1. Найдется ли эйлеров путь в графе, в котором шесть вершин, степени которых равны 2, 1, 3, 4, 2, 2? (нарисуйте), если нет - объясните почему. 2. Рис.1. Придумайте способ нарисовать граф одним росчерком (не отрывая карандаш от бумаги и не проводя одну линию дважды). 3. Рис.2. Есть ли в графе эйлеров путь? Если есть, запишите какой-нибудь один путь, если нет, объясните почему (с указанием вершин).

1. Эйлеров путь в графе

Сумма степеней всех вершин графа должна быть равна удвоенному числу рёбер. В данном случае, сумма степеней равна 2 + 1 + 3 + 4 + 2 + 2 = 14.

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

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

2. Рисунок 1

Да, граф на рисунке 1 можно нарисовать одним росчерком, так как у него есть две вершины нечетной степени.

Начнем с вершины 1, затем пройдем по вершинам 2, 3, 4, 5, 6 и вернемся в вершину 1.

3. Рисунок 2

Чтобы определить, есть ли в графе эйлеров путь, нужно проверить степени каждой вершины:

• A: степень 2
• B: степень 2
• C: степень 2
• D: степень 3
• E: степень 3
• F: степень 1
• G: степень 1
• H: степень 2

В данном графе 4 вершины с нечетной степенью (D, E, F, G), следовательно, эйлерова пути не существует.