Головна

Ейлерови і Гамільтона шляху. Критерій існування ейлерового шляху.

Визначення. Нехай дано граф G = (V, E,) і кількість ребер дорівнює m. ейлеровим шляхом називається замкнутий шлях довжини m складається з різних ребер без повторень. Якщо умова замкнутості прибрати, то отримаємо визначення полуейлерового шляху.

Визначення. Нехай дано граф G = (V, E,) і кількість вершин одно n . гамільтоновим шляхом називається замкнута ланцюг довжини n. Якщо умова замкнутості прибрати, то отримаємо визначення полугамільтонового шляху.

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

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

Доведення. Припустимо граф містить Ейлером цикл. Пройдемо з цього циклу, тоді вершина відвідана k раз (за винятком початкової) повинна мати ступінь 2k, так як при кожному відвідуванні по одному ребру входимо і по одному виходимо, збільшуючи ступінь вершини на 2. Для початкової вершини, при першому відвідуванні тільки виходимо з деякого ребру, а при останньому тільки входимо, отже, ступінь дорівнюватиме 2 (k - 1).

Нехай ступеня всіх вершин парні. Розглянемо ланцюг максимальної довжини: C = v0e0v1e1. . . ekvk + 1.

Всі ребра інцидентні vk + 1 вже зустрічаються в цьому ланцюзі, інакше її можна було б

продовжити. За припущенням, число таких ребер парне, отже vk + 1 = v0, так як ek інцидентне vk + 1, а всі інші входження vk + 1 збільшують ступінь вершини на 2. Припустимо, що C НЕ Ейлером цикл. Тоді існує ребро e 'що не належить циклу C. Eсли e "не інцидентне ніякої вершині циклу C, то розглянемо шлях соедіняющй, наприклад, вершину v0 і один з кінців ребра e 'і виберіть перший ребро e що не належить циклу C. Тоді це рeбро

іцідентно деякої вершини vi циклу, і нехай має вигляд e = {vi, u}.

Тоді ланцюг C '= ueviei. . . ekvk + 1e0v1,. . . vi-1ei-1vi має довжину більшу ніж C, що суперечить вибору C.


 



 Вершин, ребер і компонент зв'язності. |  Теорема Келі про кількість дерев на n вершинах. Коди Прюфера.

 штрих Шеффера |  Знаходження мінімальної ДНФ. |  приклади |  Лемма про несамодвойственной функції. Лемма про немонотонної функції. |  Лемма про функції, які не зберігають T_0 і T_1. Теорема Поста про повноту (доказ теореми справа наліво). |  Неорієнтовані графи. Ступені вершин. Сума ступенів вершин графа. Ізоморфізм графів. Приклад неізоморфних графів з однаковими ступенями. |  Доведення формули Ейлера для плоских зв'язкових графів |  доведення коректності |  алгоритм |  Операції об'єднання і перетину регулярних мов |

© um.co.ua - учбові матеріали та реферати