Ейлером шлях - це

Існування ейлерова циклу і ейлерова шляху

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

У неорієнтованому графі

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

Теорема: Ейлеров шлях в графі існує тоді і тільки тоді, коли граф зв'язний і містить не більше ніж дві вершини непарної ступеня. [1] [2]

В орієнтованому графі

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

Пошук ейлерова шляху в графі

Можна завжди звести задачу пошуку ейлерова шляху до задачі пошуку ейлерова циклу. Дійсно, припустимо, що ейлерова циклу не існує, а Ейлером шлях існує. Тоді в графі буде рівно 2 вершини непарної ступеня. З'єднаємо ці вершини ребром, і отримаємо граф, в якому всі вершини парному ступеня, і Ейлером цикл в ньому існує. Знайдемо в цьому графі Ейлером цикл (алгоритмом. Описаним нижче), а потім видалимо з відповіді несуществуещее ребро.

Пошук ейлерова циклу в графі

Будемо розглядати самий загальний випадок - випадок орієнтованого мультиграфом. можливо, з петлями. Також ми припускаємо, що Ейлером цикл в графі існує (і складається хоча б з однієї вершини). Для пошуку ейлерова циклу скористаємося тим, що Ейлером цикл - це об'єднання всіх простих циклів графа. Отже, наше завдання - ефективно знайти всі цикли і ефективно об'єднати їх в один.

Реалізувати це можна, наприклад, так, рекурсивно:

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

Для пошуку циклу на кроці 1 використовуємо пошук в глибину.

Складність отриманого алгоритму - O (M), тобто лінійна щодо кількості ребер М в даному графі.

Приклад реалізації на C ++

Дивитися що таке "Ейлеров шлях" в інших словниках:

Ейлером цикл - Граф Кенігсбергськая мостів. Цей граф не є ейлеровим, тому рішення не існує ... Вікіпедія

Шлях в орграфе - Тут зібрані визначення термінів з теорії графів. Курсивом виділено посилання на терміни в цьому словнику (на цій сторінці). # А Б В Г Д Е Е Ж З И Й К Л М Н О П Р С Т У Ф ... Вікіпедія

Простий шлях в орграфе - Тут зібрані визначення термінів з теорії графів. Курсивом виділено посилання на терміни в цьому словнику (на цій сторінці). # А Б В Г Д Е Е Ж З И Й К Л М Н О П Р С Т У Ф ... Вікіпедія

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

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

Граф (математика) - Цей термін має також інші значення див. Граф (значення). Неорієнтовані граф з шістьма вершинами і сім'ю ребрами У математичної теорії графів і інформатики граф це сукупність непорожньої безлічі вершин і безлічі пар ... ... Вікіпедія