Ейлером цикл - це

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Примітки

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

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

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

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

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

Цикл Гамільтона - Граф додекаедру з виділеним циклом Гамільтона Гамильтонов граф в теорії графів це граф, що містить гамільтоновим ланцюг або гамильтонов цикл. Гамильтонов шлях (або гамільтонова ланцюг) шлях (ланцюг), що містить кожну вершину графа рівно один раз. ... ... Вікіпедія

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

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

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