твердження леми очевидно. Тому надалі будемо припускати, що є простим графом. Нехай х - довільна вершина графа.
Побудуємо по індукції маршрут
обираючи вершину, суміжну з, а при обираючи вершину, суміжну з і відмінну від (існування такої вершини треба з умови леми). Оскільки має кінцеве число вершин, то врешті-решт ми прийдемо до вершини, з якої вийшли. Отримаємо цикл.
Лема доведена.
Теорема 2.1
Для зв'язного графа наступні умови еквівалентні:
1.- Ейлеровимі граф;
2. кожна вершина має парну ступінь;
. множина ребер графа можна розбити на прості цикли.
Доказ.
Нехай - ейлеровскій цикл графа. Будемо рухатися по циклу. Проходження кожної вершини збільшує ступінь кожної вершини на 2, і оскільки кожне ребро входить в рівно п раз, то будь вершина має парну ступінь.
Оскільки - зв'язний граф, ступінь кожної вершини дорівнює принаймні 2, бо в силу леми 2.1 містить простий цикл С. Виключимо ребра циклу, отримаємо остовно підграф, в якому кожна вершина має парну ступінь. Якщо у немає ребер, то (3) доведено. В іншому випадку застосуємо проведені вище міркування до, отримаємо граф, в якому ступені всіх вершин є парними і так далі. Одночасно з порожнім графом, отримаємо розбиття множини ребер на циклів
Нехай множина ребер можна розбити на прості цикли. Нехай - один з простих циклів. Якщо складається тільки з цього циклу, то -ейлеровскій граф. У протилежному випадку існує інший простий цикл, який має вершину, загальну з. Ланцюг, яка починається з і складається з циклу і наступного за ним циклу, є замкнутим ланцюгом, яка містить всі ребра графа, кожне один раз. Отже, - ейлеровскій граф.
З теореми 2.1 слід наступна теорема.
Теорема 2.2. Зв'язний граф є ейлеровим тоді і тільки тоді, коли кожна його вершина має парну ступінь.
.
Рис.2.6 Приклад ейлерового графа в теоремі 2.2
Доказ. Граф зображений на малюнку 2.6. є ейлеровимі, ??оскільки:
. Ступінь вершин А, F, D, C, Q=4 (чорні).
. Ступінь вершин B, E=2 (чорні)
. Безліч ребер цього графа є об'єднання двох простих циклів і.
Теорема 2.3. Зв'язний граф є полуейлеровім тоді і тільки тоді, коли в ньому не більше двох вершин непарного ступеня ..
Рис. 2.7 Приклад полуейлерового графа до теоремі 2.3
Доказ. Граф зображений на малюнку 2.7. є полуейлеровім, оскільки:
. Ступінь вершин А, F, C=4 (парні);
. Ступінь вершин B=2 (парні);
. Ступінь вершин E, D=3 (непарні);
. Ось один з можливих варіантів обходу. Початковою точкою маршруту є точка, а кінцевим є точка.
Якщо граф має дві вершини з непарними ступенями (див. рис. 2.7), то для будь-якої полуейлеровой ланцюга одна з цих вершин буде початковою, а інша кінцевої. Для доказу досить сполучити відрізком вершини з непарними ступенями.
Зауважимо, що згідно «лемі про рукостисканні» - число вершин непарного ступеня є парним.
Спробуємо для довільного графа вказати найменше число ланцюгів таких, що: ніякі дві не мають спільних ребер і всі вони повністю накривають разом весь граф. Очевидно, якщо на графі є таке сімейство ланцюгів, то кожна вершина непарного степеня повинна бути або початкової або кінцевої вершиною якийсь ланцюга. Загальне число вершин з непарної ступенем згідно лемі про рукостискання є парним, скажімо рівним.
Таким чином, кожне сімейство ланцюгів, що накривають граф, повинно містити принаймні ланцюгів.
Доведемо, що існування вершин з непарним ступенем є і достатньою умовою існування ланцюгів накривають граф.
Теорема 2.4. На будь-якому зв'язкового графі з вершинами непарної ступеня існує сімейство ланцюгів, які в сукупності містять всі ребра графа в точності один раз кожне.
Доказ. Позначимо вершини з непарними ступенями
Якщо ми додамо до нашого графу ребра
то всі вершини отриманого графа будуть парними і на ньому знайдеться Ейлером цикл. При відкиданні доданих ребер цикл розпадеться на окремих ланцюгів, які містять всі ребра графа.
Граф, зображений на малюнку 2.8 має чотири вершини з непарними ступенями і накривається двома ланцюгами і.
Рис.2.8 Граф з непарної ступенем вершин до теореми 2.4
У розважальній математиці ось уже протягом кількох століть рассмотриваются завдання, які можна сформулювати як завдання пошуку певних маршрутів в графах, зокрема, пошуку ейлерових циклів.
Так, граф на малюнку 2.9. називається «шаблею Магомета», а ейлеровимі цикл необхідно побудувати за маршрутом, не відриваючи пера ручки від малюнка за один раз (тобто розчерком), представлену на рис.2.9.
Рис. 2.9 ейлеровимі цикл в графі - «Шабля Магомета»
Більшість зб...
