Ейлерів ланцюг
У теорії графів, ланцюг Ейлера (англ. 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.
- ↑ Fleischner, Herbert (1991), X.1 Algorithms for Eulerian Trails, Eulerian Graphs and Related Topics: Part 1, Volume 2, Annals of Discrete Mathematics, т. 50, Elsevier, с. X.1–13, ISBN 978-0-444-89110-5.
| Вікісховище має мультимедійні дані за темою: Ейлерів ланцюг |