Page 109 - 4204

ЛЕКЦІЯ 8. ЗАДАЧІ МЕРЕЖЕВОГО АНАЛІЗУ З ЕЛЕМЕНТАМИ ТЕОРІЇ ГРАФІВ

такий замкнутий маршрут, який мав проходити через всі чотири частини

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

знайти такий маршрут були невдалими.

Рисунок 8.1. Схема кенігсберзьких мостів та відповідний їй граф

Щоб довести неможливість існування такого маршруту, Ейлер

позначив кожну частину суші точкою (вершиною, або вузлом), а

кожен міст – лінією (ребром), що з’єднує відповідні точки, і оде-

ржав «граф» (рис. 8.1, б). Твердження про неіснування маршруту

рівносильне неможливості вказаним чином обійти граф. Виходя-

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

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

Зв’язний граф є ейлеровим тоді і тільки тоді, коли кожна

його вершина має парний степінь.

Зв’язний граф має ейлерів ланцюг (незамкнений маршрут у

якого всі ребра різні) тоді й тільки тоді, коли він має не більше

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

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

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

108