Page 45 - 4386

проїжджати. Виходить, що найкращим маршрутом бригади буде

саме ейлеровий цикл, який починається та закінчується на базі.

Приклад 4.1. Чи мають графи G та G , зображені на рис. 4.2
2
1
ейлерові цикл.

Рисунок 4.2

Розв'язок.
Обчислимо степені вершин графів:

G : δ(v )=4, δ(v )=2, δ(v )=4, δ(v )=2, δ(v )=2. Степені всіх
1
4
5
3
1
2
вершин графа G парні, отже, граф має ейлеровий цикл,
1
наприклад v v v v v v v v .
1 2 3 4 1 3 5 1
G : δ(v )=3, δ(v )=2, δ(v )=2, δ(v )=5, δ(v )=2, δ(v )=2. Степені
6
1
2
3
4
2
5
вершин v та v графа G непарні, отже, граф не має ейлерового
2
1
4
циклу.
Що ж стосується кенігсбергських мостів, то можна
поставити іншу задачу: чи можливо пройти кожен міст по одному
разу та не обов'язково повертатися у вихідну точку маршруту?
Оскільки граф для задачі про кенігсбергські мости має

чотири вершини з непарними степенями, то можна зробити

висновок про те, що даний граф не має ейлерового ланцюга, а

отже, неможливо пройти кожен міст по одному разу, навіть якщо

не потрібно повертатися у вихідну точку маршруту.

Так, наприклад, граф G , зображений на рис. 4.2, не має
2
ейлерового циклу, але має ейлеровий ланцюг v v v v v v v v v ,
1 2 4 1 3 4 5 6 4
тому що дві його вершини мають непарний степінь.

44