Граф кенігсберзьких мостів. Це — не граф Ейлера, відповідно, розв'язку не існуєКожна вершина цього графу має парний степінь, отже цей граф — Ейлера. Обхід ребер в абетковому порядку дає цикл Ейлера
У теорії графів, ланцюг Ейлера (англ.Eulerian path) — ланцюг у графі, який проходить кожне ребро рівно один раз. Схожим чином, цикл Ейлера — ланцюг Ейлера, який розпочинається та завершується в одній вершині. Вперше розглянуті Леонардом Ейлером під час розв'язання відомої задачі кенігсберзьких мостів в 1736. Математично задача звучить так:
Чи можливо для графу на малюнку праворуч побудувати ланцюг (або цикл), який проходить кожне ребро рівно один раз?
Ейлер довів, що необхідна умова існування циклу — парність степеня кожної вершини графу, і ствердив без доведення, що зв'язний граф з усіма вершинами з парними степенями має цикл Ейлера. Перше повне доведення цього твердження в 1873 оприлюднив Карл Гіргольцер.[1]
Граф Ейлера
Термін граф Ейлера має два загальні значення в теорії графів. Одне значення це наявність в графі циклу Ейлера, друге — парність степеня всіх вершин графу.
Для існування ланцюга Ейлера необхідно, щоби не більше ніж дві вершини мали непарний степінь; це означає, що граф мостів Кенігсберга — не граф Ейлера. Якщо не існує вершин непарних степенів, усі ланцюги Ейлера — цикли. Якщо рівно дві вершини мають непарний степінь, усі ланцюги Ейлера розпочинаються в одній і завершуються в іншій. Іноді граф, який має ланцюг Ейлера, але не має циклу називається напівейлеровим.
Цикл Ейлера в неорієнтованому графі — цикл, який проходить кожне ребро рівно один раз.
Для орієнтованих графів ланцюг заміняється на шлях або орієнтований шлях і цикл на орієнтований цикл. Визначення і властивості ланцюгів, циклів і графів Ейлера залишаються дійсними й у випадку мультиграфа.
Властивості
Зв'язний неорієнтований граф — Ейлера лише тоді, коли кожна вершина графу має парний степінь.
Неорієнтований граф — Ейлера, якщо він зв'язний і може бути розбитим на реберно-неперетинні цикли.
Якщо неорієнтований граф G — Ейлера, тоді його лінійний графL(G) також Ейлера.
Орієнтований граф — Ейлера якщо він сильнозв'язний і кожна вершина має однаковий вхідний і вихідний степінь.
Орієнтований граф — Ейлера, якщо він сильно зв'язний і може бути розбитим на реберно-неперетинні цикли.
Ланцюг Ейлера існує в орієнтованому графі лише тоді, коли відповідний неорієнтований граф зв'язний, не більше ніж одна вершина має вихідний степінь — вхідний степінь = 1, не більше ніж одна вершина має вхідний степінь — вихідний степінь = 1, а всі інші вершини мають рівні вхідні й вихідні степені.
Неорієнтований граф — напів Ейлера, якщо не більше ніж дві вершини в ньому мають непарний степінь.
Алгоритм Гіргольцера
Оберіть будь-яку стартову вершину v та рухайтеся ланцюгом ребер розпочинаючи з цієї вершини допоки не повернетесь у v. Неможливо застрягнути в будь-якій вершині окрім v, бо парний степінь кожної вершини гарантує, що коли ланцюг досягає іншої вершини w, то мусить існувати невикористане ребро з w. Ланцюг, сформований таким чином — замкнений, тобто цикл, але може не покривати всіх ребер початкового графу.
Допоки існує вершина u, яка не належить до поточного ланцюга, але має інцидентні ребра не в ланцюзі, розпочніть інший ланцюг з u, слідуючи невикористаними ребрами допоки не повернетеся в u та приєднайте новий цикл до вже наявного.
Використання такої структури як двобічно зв'язаний список уможливлює виконання кожної операції за сталий час (знаходження невикористаних ребер для кожної вершини, знаходження нової стартової вершини й поєднання двох циклів зі спільною вершиною), таким чином весь алгоритм потребує лінійного часу, .[2]
Примітки
↑N. L. Biggs, E. K. Lloyd and R. J. Wilson, Graph Theory 1736—1936, Clarendon Press, Oxford, 1976, 8-9, ISBN 0-19-853901-0.
