Тема 11. Маршрути орієнтованих і неорієнтованих графів.
Питання теми
1. Ланцюги і цикли в графах.
2. Ейлерів цикл і граф.
3. Гамільтонів цикл і граф.
Основні терміни теми : маршрут, ланцюг, цикл.
1. Ланцюги і цикли в графах.
Часто задачі на графах вимагають відокремлення різних маршрутів, які мають певні властивості і характеристики.
Рис. 1. Псевдограф.
Маршрут довжини m визначають як послідовність m ребер графа ( не обов’язково різних), таких, що кордонні вершини двох сусідніх ребер співпадають. Маршрут проходить і через всі вершини, інцидентні ребрам, які н нього входять. Прикладами маршрутів на графі рис.1, а могуть служити послідовності (е , е , е , е , е ), (е , е , е , е ). Перший маршрут проходить через послідовність вершин (v , v , v , v , v , v ) і об’єднує вершини v i v , а другий - через послідовність вершин (v , v , v , v , v ) і об’єднує вершини v i v . Замкнутий маршрут приводить у ту ж саму вершину, з якої він почався.
Маршрут, всі ребра якого різні, називається ланцюгом, а , ланцюг для якого різні всі вершини називається простим ланцюгом. Замкнений ланцюг називається циклом, а простий ланцюг - простим циклом. Так на графі рис. 1, а - ланцюг, - простий ланцюг, - цикл, - простий цикл.
2. Ейлерів цикл і граф.
Цикл, який має всі ребра графа, називається ейлеревим циклом, а граф, в якому є такий цикл, називається ейлеревим графом.
Зв'язний граф G називається напівейлеревим, якщо в ньому існує ланцюг, який включає кожне його ребро. Таким чином, всякий ейлерів граф буде напівейлеревим.
Виникає природне питання: як встановити, що заданий граф є ейлеревим? Відповідь на це питання дають такі твердження.
Теорема 1. Якщо ступінь кожної вершини скінченого графа не менше двох, то граф має цикл.
Доведення. Нехай v - довільна вершина графа G. Корис¬туючись методом побудови по індукції, побудуємо маршрут v, v,, ..., vk,... так, що vj+l суміжна з v. і відмінна від УИ. ІСНУВАННЯ ТАКОЇ вершини випливає з умов теореми. Оскільки граф G скінчений, то на деякому кроці побудови нашого маршруту прийдемо до вершини, вибраної раніше. Нехай vk - перша з таких вершин, тоді частина маршруту, яка лежить між першою і другою появою vk в цьому маршруті, і є шуканим циклом.
Теорема доведена.
Зауважимо, що дана теорема справедлива для псевдографа (який має петлі) і для мультиграфа (який має кратні ребра).
Теорема 2. Зв'язний граф G є ейлерів тоді і тільки тоді, коли кожна вершина G має парний ступінь.
Доведення. Нехай G має ейлерів ланцюг Р, тоді при всякому проходженні ланцюга Р через будь-яку із вершин графа G ступінь цієї вершини збільшується на 2. А оскільки кожне ребро зустрічається в Р тільки один раз, то кожна вершина повинна мати парний ступінь.
Доведення у зворотному напрямку проводиться індукцією за числом ребер в графі G.
Наслідок 1. Зв'язний граф ейлерів тоді і тільки тоді, коли множину його ребер можна розбити на цикли, які не перетинаються.
Наслідок 2. Зв'язний граф напівейлерів тоді і тільки тоді, коли він має не більше двох вершин непарного ступеня.
Зауважимо, що дана теорема справедлива для псевдографів (які мають петлі) і для мультиграфів (які мають кратні ребра).
Слід також зауважити, що коли напівейлерів граф має рівно дві вершини непарного ступеня, то у всякого напівейлеревого ланцюга (сенс поняття очевидний) обов'язково одна з цих вершин початкова, а друга кінцева. З леми про рукостискання випливає, що граф не може мати тільки одну вершину непарного ступеня.
Теорема Флері. Нехай G = (V, Е) - ейлерів граф, тоді наступна процедура завжди можлива і веде до ейлеревого ланцюга в графі G: виходячи з будь-якої вершини u є V, ідемо по ребрах графа G довільним чином згідно з такими правилами:
(і) стираємо ребра, які пройдені, і стираємо ізольовані вершини, які при цьому виникають;
(іі) на кожному етапі ідемо по мосту лише тоді, коли немає інших можливостей.
3. Гамільтонів цикл і граф.
Розглянута вище проблема існування замкнутого ланцюга, який проходить через кожне ребро заданого зв'язного графа G, аналогічно може бути сформульована і для вершин. Тобто, чи існує замкнутий ланцюг в заданому зв'язному графі G, який проходить рівно один раз через кожну вершину графа G. Очевидно, що такий ланцюг повинен бути циклом. Якщо такий цикл в графі G існує, то він називається гамільтоновим циклом, а граф G -гамільтоновим графом.
Пошук критерію гамільтоновості графа - це одна з основних невирішених проблем теорії графів. Про гамільтонові графи відомо ще зовсім мало. Один з найбільш відомих результатів загального характеру – це:
Теорема Дірака. Якщо в графі G = (V, Е) з п > 3 вершинами (v є V) n(v) > п / 2, то граф G являється гамільтоновим.
Доведення. Введемо в граф G k нових вершин і з'єднаємо кожну з цих вершин з кожною вершиною графа G. Будемо вважати, що k - найменше число вершин, які потрібно ввести в граф G для того, щоб одержаний граф G' став гамільтоновим.
Припустимо, що k > 0 і v, р, w,..., v - гамільтоновий цикл, де v і w - вершини з G, а р - одна з нових вершин. Тоді v і w не суміжні, оскільки в протилежному випадку вершина р зайва, а це суперечить мінімальності k. Більше того, вершина (наприклад, w' суміжна з вершиною w, не може безпосередньо йти за вершиною v', суміжною з v, оскільки тоді ми могли б замінити v, р, w, ..., v', w', ..., v на v, v', ..., w, w', ..., v, перевернувши частину циклу, яка знаходиться між вершинами w і v'. Звідси випливає, що число вершин графа G', не суміжних з w, не менше числа вершин, суміжних з v, тобто, у крайньому випадку, дорівнює п / 2 + k. З іншого боку, очевидно, що число вершин графа G', суміжних з w, теж не менше п / 2 + k. Оскільки всяка вершина графа G' не може бути одночасно суміжною і не суміжною з w, то загальна кількість вершин графа G', яка дорівнює п + k, не менша п + 2k. Це може бути лише тоді, коли k = 0.
Одержана суперечність доводить теорему.
Якщо в графі G = (V, Е) порядку п зафіксувати одну з вершин і обхід графа завжди починати з неї, то всякому гамільтоновому циклу буде відповідати перестановка елементів множини V. Отже, знайти гамільтонів цикл або переконатися в його відсутності можна шляхом перебору (п - 1)! перестановок. Якщо граф G гамільтонів, то цей перебір в повному обсязі необхідно буде зробити лише у випадку великого невезіння, тобто коли перестановка, що відповідає гамільтоновому циклу, зустрічається в цьому процесі останньою. Якщо ж граф G - не гамільтонів, то, діючи таким чином, необхідно перебрати всі (п - 1)! перестановок. Хоча на практиці користуються різними алгоритмами часткового перебору, але складність цих алгоритмів залишається високою (пропорціональною (п - 1)!).
Орієнтовані маршрути на орграфі визначаються аналогічно, з тією різницею, що початкова вершина кожної поступової дуги повинна співпадати з кінцевою вершиною попередньої дуги. Інакше кажучи, рух по маршруту дозволяється тільки в направленнях, вказаних стрілками. Маршрут, який не має дуг, що повторюються, називається шляхом, а який не має вершин, що повторюються - простим шляхом. Замкнутий шлях називається контуром, а простий замкнутий шлях - простим контуром. Граф (орграф) називається циклічним (контурним), якщо він має хоча б один цикл(контур), в протилежному випадку він називаються ациклічним (безконтурним).
Поняття ланцюга та циклу застосовані і з орграфом. При цьому направлення дуг не беруться на увагу, таким чином замість орграфа розглядається неорієнтований співвіднесений йому граф.