Ейлерови цикли і ланцюги

Ейлером цикл - цикл, що містить всі ребра графа. Ейлеров граф - граф, який має Ейлером цикл.

Поняття ейлерова циклу пов'язано з відомою завданням Ейлера про Кенигсбергских мостах на річці Прегал. Схема цих мостів, що з'єднують береги річки 2,3 з двома її островами 1,4 і острова між собою, наведена на рис. 3.8а. Ейлер сформулював це завдання так: чи можна, почавши з деякою точки, пройти всі мости по одному разу і повернутися у вихідний пункт. Для вирішення завдання Ейлер перетворив малюнок в граф, позначивши берега річки і острова як вершини графа, а мости як ребра графа (рис. 3.8.b).

Мал. 3.8 Схема і граф для завдання про Кенигсбергских мостах.

Легко бачити, що в такій постановці завдання про Кенигсбергских мостах еквівалентна задачі визначення на графі такого циклу (циклічного маршруту, що не містить повторюваних ребер), який проходить через всі ребра графа. Її рішення дається наступною теоремою.

Теорема Ейлера. кінцевий неорієнтований граф ейлерів тоді і тільки тоді, коли він пов'язаний і ступеня всіх його вершин парні.

Необхідність цих умов досить очевидна. У незв'язному графі кожен цикл належить будь-якої його зв'язковий частини, тобто не проходить через все його частини. З іншого боку, кожен раз, коли Ейлером цикл приходить в будь-яку вершину, він повинен вийти з неї по іншому ребру, тобто інцидентні вершинам ребра можна розбити на пари сусідніх в ейлеровом циклі. Це відноситься і до початкової вершини, яка одночасно є і кінцевою. Для неї інцідентние ребра також розпадаються на пари, але, крім того, є ребро, що відноситься до початку циклу і ребро, що відноситься до кінця циклу.

Близькою за змістом до задачі пошуку ейлерова графа є так звана задача графопостроителя. Вона може бути сформульована таким чином: заданий плоский граф необхідно викреслити, не відриваючи олівця від паперу і не обводячи двічі одне й те саме ребро.

Завдання графопостроителя не є еквівалентною задачі про Кенигсбергских мостах і допускає рішення не тільки в класі ейлерових циклів, так як не вимагає, щоб головка графопостроителя поверталася у вихідну точку. Рішення може лежати і в класі ейлерових ланцюгів.

Ейлерова ланцюг - ланцюг, що включає всі ребра даного н-графа. однак вона має різні початкову і кінцеву вершини.

Теорема. Щоб в кінцевому н-графі існувала ейлерова ланцюг, необхідні і достатні його зв'язність і парність ступенів усіх вершин, крім початкової і кінцевої, які повинні мати непарні ступеня.

Розглянемо деякі приклади.

Приклад. Схема і граф для завдання про Кенигсбергских мостах наведені на рис. 3.8.

У графі всі вершини мають непарні ступеня. Отже, граф не має ейлерова циклу і рішення поставленого завдання неможливо.

Приклад. Чи мають п'ятикутник і пятіграннік-піраміда, наведені на малюнку 3.9, Ейлером цикл (ланцюг)?

Локальна ступінь кожної вершини п'ятикутника дорівнює двом, тобто парна. Відповідно, п'ятикутник - Ейлером граф.

Пятіграннік-піраміда має непарні ступеня всіх вершин і не є ейлеровим графом.

Приклад. Знайти Ейлером цикл для графа, представленого на рис. 3.10.

Мал. 3.10. Знаходження ейлерова циклу

Граф зв'язний і має 6 вершин, всі парні. Отже, даний граф - Ейлером і може бути намальований одним розчерком пера. Звідки ж починати креслення?

Існує наступний спосіб визначення порядку креслення: в графі слід вибрати одну область і заштрихувати її; область, що межує з заштрихованої, пропустити, а має лише загальну вершину заштрихувати, і так діяти до тих пір, поки всі можливі області не будуть заштриховані (рис. 3.10b).

Далі заштрихований граф слід роз'єднати в одній або декількох вершинах так, щоб утворилася однозв'язна (без «дірок») заштрихованная область (ріс.3.10с). Таким чином, теорія графів дала не тільки умови розв'язання задачі, але і конструктивний метод її вирішення.