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

У теорії графів, ланцюг Ейлера (англ. Eulerian path) — ланцюг у графі, який проходить кожне ребро рівно один раз. Схожим чином, цикл Ейлера — ланцюг Ейлера, який розпочинається та завершується в одній вершині. Вперше розглянуті Леонардом Ейлером під час розв'язання відомої задачі кенігсберзьких мостів в 1736. Математично задача звучить так:

Чи можливо для графу на малюнку праворуч побудувати ланцюг (або цикл), який проходить кожне ребро рівно один раз?
Граф кенігсберзьких мостів. Це — не граф Ейлера, відповідно, розв'язку не існує
Кожна вершина цього графу має парний степінь, отже цей граф — Ейлера. Обхід ребер в абетковому порядку дає цикл Ейлера

Ейлер довів, що необхідна умова існування циклу — парність степеня кожної вершини графу, і ствердив без доведення, що зв'язний граф з усіма вершинами з парними степенями має цикл Ейлера. Перше повне доведення цього твердження в 1873 оприлюднив Карл Гіргольцер.[1]

Граф Ейлера

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

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

Визначення

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

Цикл Ейлера в неорієнтованому графі — цикл, який проходить кожне ребро рівно один раз.

Для орієнтованих графів ланцюг заміняється на шлях або орієнтований шлях і цикл на орієнтований цикл.

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

Властивості
  • Зв'язний неорієнтований граф — Ейлера лише тоді, коли кожна вершина графу має парний степінь.
  • Неорієнтований граф — Ейлера, якщо він зв'язний і може бути розбитим на реберно-неперетинні цикли.
  • Якщо неорієнтований граф G — Ейлера, тоді його лінійний граф L(G) також Ейлера.
  • Орієнтований граф — Ейлера якщо він сильнозв'язний і кожна вершина має однаковий вхідний і вихідний степінь.
  • Орієнтований граф — Ейлера, якщо він сильно зв'язний і може бути розбитим на реберно-неперетинні цикли.
  • Ланцюг Ейлера існує в орієнтованому графі лише тоді, коли відповідний неорієнтований граф зв'язний, не більше ніж одна вершина має вихідний степінь — вхідний степінь = 1, не більше ніж одна вершина має вхідний степінь — вихідний степінь = 1, а всі інші вершини мають рівні вхідні й вихідні степені.
  • Неорієнтований граф — напів Ейлера, якщо не більше ніж дві вершини в ньому мають непарний степінь.

Алгоритм Гіргольцера
  • Оберіть будь-яку стартову вершину v та рухайтеся ланцюгом ребер розпочинаючи з цієї вершини допоки не повернетесь у v. Неможливо застрягнути в будь-якій вершині окрім v, бо парний степінь кожної вершини гарантує, що коли ланцюг досягає іншої вершини w, то мусить існувати невикористане ребро з w. Ланцюг, сформований таким чином — замкнений, тобто цикл, але може не покривати всіх ребер початкового графу.
  • Допоки існує вершина u, яка не належить до поточного ланцюга, але має інцидентні ребра не в ланцюзі, розпочніть інший ланцюг з u, слідуючи невикористаними ребрами допоки не повернетеся в u та приєднайте новий цикл до вже наявного.

Використання такої структури як двобічно зв'язаний список уможливлює виконання кожної операції за сталий час (знаходження невикористаних ребер для кожної вершини, знаходження нової стартової вершини й поєднання двох циклів зі спільною вершиною), таким чином весь алгоритм потребує лінійного часу, .[2]

Примітки
  1. 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.
  2. 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..
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.