Page 44 - 4386

Перш ніж дати відповідь до задачі про кенігсбергські мости,

розглянемо ряд визначень та тверджень.

Цикл, який містить усі ребра графа, називається ейлеровим

циклом. Зв’язний граф, який має ейлеровий цикл, називається

ейлеровим графом.

Наприклад, у графі K з множиною вершин {v , v , v , v , v }
5
5
4
1
2
3
існує ейлеровий цикл v v v v v v v v v v v .
1 2 3 4 5 1 3 5 2 4 1
Якщо G − ейлеровий граф, то будь-який його ейлеровий
цикл не єдиний і відрізняється від інших ейлерових циклів графа
G принаймні або зміною початкової вершини і/або зміною

порядку проходження.

Теорема Ейлера. Зв’язний граф G є ейлеровим тоді і

тільки тоді, коли степені всіх його вершин парні.

Ейлеровим ланцюгом називається ланцюг, що проходить

через усі ребра графа. Нетривіальний зв’язний граф має

ейлеровий ланцюг тоді і тільки тоді, коли він має тільки дві

вершини з непарними степенями.

Таким чином, для відповіді на запитання жителів

Кенігсберга, підрахуємо степені вершин графа, побудованого

Ейлером (рис. 4.1 б): δ(A)=5; δ(B)=δ(C)=δ(D)=3. Даний граф має

непарні степені вершин. Отже, він не має ейлерового циклу.

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

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

Ейлерові цикли виникають у практичних задачах,

пов’язаних з обходом усіх ребер графа по одному разу.

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

Ремонтна бригада має проїхати через усі ці шляхи, починаючи

від своєї бази. Бригада має спеціальну техніку, яка рухається

дуже повільно, тому бажано двічі тим самим шляхом не

43