Тема 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)!).

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

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

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17  Наверх ↑