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

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

Чи можливо для графу на малюнку праворуч побудувати ланцюг (або цикл), який проходить кожне ребро рівно один раз?

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

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

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

Граф Ейлера

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

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

Визначення

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

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

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

Властивості

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

Алгоритм Гіргольцера

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

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