ЗВ’ЯЗНІСТЬ ГРАФІВ. ЕЙЛЕРОВІ ТА ГАМІЛЬТОНОВІ ГРАФИ

Ознайомлення на практичних прикладах з основними поняттями зв’язності графів, з їх метричними характеристиками. Вивчення способів визначення ейлерових та гамільтонових графів. Ознайомлення з алгоритмами знаходження ейлерова циклу (ейлерова графа), гамільтонова шляху (гамільтонова графа).

4.2 Методичні вказівки з організації самостійної роботи студентів

Під час підготовки до практичного заняття необхідно повторити лекційний матеріал, розділи літератури [1–8, 10–12] з таких питань: поняття зв’язності графів, властивості зв’язних графів; метричні характеристики зв’язних графів; ейлерові графи; теорема Ейлера про наявність ейлерова циклу; алгоритм знаходження ейлерова циклу (теорема Флері); гамільтонові графи; ознаки існування гамільтонових циклів, шляхів і контурів.

Підготовка і виконання практичного заняття проводиться за два етапи.

Перший етап пов’язаний з вивченням на практичних прикладах таких основних понять і визначень теми «Зв’язність графів. Ейлерові та гамільтонові графи»: маршрут; довжина маршруту; замкнений маршрут; коло; просте коло; цикл; дуга; орієнтований маршрут; шлях; контур; зв’язний граф; незв’язний граф; сильно зв’язний граф; підграф; компонента зв’язності; n -зв’язний граф; степінь зв’язності графа; число вершинної зв’язності; число реберної зв’язності; точка зчленування графа; міст; відстань між вершинами графа; діаметр графа; ексцентриситет вершини; радіус графа; центральна вершина графа; центр графа; грань (комірка) геометричного графа; необмежена грань (зовнішня грань); внутрішня грань; границя грані; ейлерове коло; ейлерів цикл; ейлерів граф; власний ейлерів шлях; алгоритм знаходження ейлерова циклу (алгоритм Флері); гамільтонів шлях (гамільтонів ланцюг); гамільтонів граф.

Під час виконання першого етапу практичного заняття студент має запропонувати і записати індивідуальний приклад для кожного з розглянутих вище понять і визначень.

Другий етап виконання практичного заняття пов’язаний з розв’язанням практичних завдань, поданих у підрозділі 4.3, на основі запропонованих типових прикладів (див. підрозділ 4.4).

4.3 Контрольні запитання і завдання

4.3.1 Контрольні запитання

1. Дайте визначення зв’язному і незв’язному графам.

2. Що є компонентою зв’язності графа? Наведіть приклади компонент зв’язності.

3. Що називається степенем зв’язності графа?

4. Перелічіть властивості зв’язних графів.

5. Наведіть приклади метричних характеристик зв’язних графів.

6. Якщо граф зв’язний і – число його вершин, то яка нижня оцінка для числа його ребер?

7. Дайте визначення ейлеровому циклу (ейлеровому колу, замкненому ейлеровому колу).

8. Який граф називається ейлеровим?

9. Для розв’язання яких практичних задач використовується теорема Ейлера?

10. Поясніть використання алгоритму знаходження ейлерева циклу (теорема Флері).

11. Дайте визначення гамільтонова шляху (гамільтонова ланцюга), гамільтонова циклу.

12. Який граф називається гамільтоновим?

13. Дайте характеристику алгоритму Робертса-Флореса. Для яких цілей він використовується?

14. Назвіть основні ознаки існування гамільтонових циклів, шляхів і контурів.

15. Охарактеризуйте теорему (умову Дірака) для визначення гамільтонова графа.

4.3.2 Контрольні завдання

Завдання 1. Визначити, чи є для графа , зображеного на рис. 4.1, маршрут колом, циклом, простим циклом, якщо маршрут задається як:
1) ; 2) ; 3) ; 4) .

Завдання 2. Який з наведених на рис. 4.2 орієнтованих графів є зв’язним? Який з графів є сильно зв’язним?

Завдання 3. Визначити число компонент зв’язності в графах та (рис. 4.3), якщо ці графи задаються так

Завдання 4. Визначити компоненти зв’язності в графі (рис. 4.4) і знайти маршрути довжини три (три дуги), які виходять з вершини .

Завдання 5. Знайти в графі (рис. 4.5) усі точки зчленування і мости.

Завдання 6. Знайти такі метричні характеристики графа (рис. 4.6): ексцентриситети усіх вершин графа, діаметр графа, радіус графа, периферійні вершини графа, діаметральні кола, центральні вершини графа, центр графа.

Завдання 7. Знайти для графа , який зображений на рис. 4.7, центр, радіус, діаметр, периферійні точки.

Завдання 8. Визначити, чи є графи і , зображені на рис. 4.8, ейлеровими (мають ейлерів цикл).

Завдання 9. Серед графів, які зображені на рис. 4.9, знайдіть ті, які мають власний ейлерів шлях.

Завдання 10.

Поясніть, які з орієнтованих графів, зображених на рис. 4.10, мають ейлерів цикл?

Завдання 11.

Найдіть гамільтонів цикл, якщо він існує, для кожного з графів, які зображені на рис. 4.11.

Завдання 12.

Нарисуйте такі графи: а) ; б) ; в) ; г) .

4.4 Приклади аудиторних і домашніх завдань

Завдання 1. Визначити, чи є для графа , зображеного на рис. 4.1, відповідний маршрут колом, простим колом, циклом, простим циклом, якщо маршрут заданий як: 1) ; 2) ; 3) ; 4) ; 5) .

Розв’язок. Відповідно до визначення кола, простого кола, циклу, простого циклу одержимо: 1) простий цикл (усі вершини й ребра різні); 2) цикл (усі ребра різні, а вершини ні); 3) просте коло; 4) маршрут (є однакові ребра й вершини); 5) просте коло.

Завдання 2. Визначити число компонент зв’язності в графі , якщо граф задається так (рис. 4.12)

Рисунок 4.12 – Граф , для якого визначається число компонент зв’язності

Розв’язок. Граф має дві компоненти зв’язності, в першу входять вершини , в другу – .

Завдання 3. Розкласти орграф , зображений на рис. 4.13, на сильно зв’язані компоненти.

Розв’язок. Граф розкладається на три сильно зв’язані компоненти , , (рис. 4.14)

Знайти в графі , зображеному на рис. 4.15, всі точки зчленування і мости.

Послідовно розглянемо ребра графа, вилучаючи їх із графа. Тільки вилучення ребра призводить до збільшення числа компонент зв’язності, тому є мостом. Аналогічно розглядаємо вершини графа і знаходимо, що вершини 3 і 5 є точками зчленування, тому що вилучення їх із графа призводить до збільшення числа компонент зв’язності.

Знайти такі метричні характеристики графа (рис. 4.16): ексцентриситети усіх вершин графа, діаметр графа, радіус графа, периферійні вершини графа, діаметральні кола, центральні вершини графа, центр графа.

Ексцентриситетом вершини є відстань від до найбільш віддаленої від неї вершини, тому , , . Максимальний з усіх ексцентриситетів є діаметром графа, тобто . Найменший з ексцентриситетів є радіусом графа, тобто . Вершина є периферійною, якщо її ексцентриситет дорівнює діаметру графа, тобто , тому периферійними вершинами графа є вершини і . Просте коло, відстань між кінцями якого дорівнює , називається діаметральним колом ом, тому діаметральними ланцюгами графа є такі ланцюги: і . Вершина називається центральною вершиною графа, якщо на ній досягається мінімум ексцентриситетів, тобто , тому центральною вершиною графа є вершина . Множина усіх центральних вершин графа є центром графа, тому центром графа є .

Визначити, чи є граф , зображений на рис. 4.17, ейлеровим.

Використаємо теорему Ейлера: граф є ейлеровим (містить ейлерів цикл) тоді і тільки тоді, коли він зв’язний і степені всіх його вершин – парні.

Граф є зв’язним. Степені його вершин такі: , , . Граф не є ейлеровим, тому що не всі степені вершин є парними.

Чи має граф, зображений на рис. 4.18, власний ейлерів шлях?

Використаємо таку теорему: граф (мультограф або псевдограф) має власний ейлерів шлях тоді й тільки тоді, коли він зв’язний і рівно дві його вершини мають непарний степінь. Граф, зображений на рис. 4.18, зв’язний, має власний ейлерів шлях, оскільки рівно дві його вершини ( і ) мають непарний степінь, тобто .

Чи має орієнтований граф, зображений на рис. 4.19, ейлерів цикл?

Використаємо таку теорему: орієнтований граф має ейлерів цикл тоді й тільки тоді, коли він зв’язний, і півстепені виходу та заходу у вершині рівні. Орієнтований граф, зображений на рис. 4.19, не містить ейлерів цикл, тому що півстепені виходу та заходу у вершинах і не дорівнюють відповідно один одному.

Знайдіть гамільтонів цикл, якщо він існує, у графі , що зображений на рис. 4.20.

Гамільтонів цикл для графа буде таким .

Пошук Ейлерового циклу в неорієнтованому графі

Ейлеровим циклом (також відомий як Ейлерів ланцюг) називається замкнутий маршрут, в якому кожне ребро графа зустрічається точно один раз. Для існування такого маршруту в зв’язному неорієнтованому графі необхідно і достатньо, щоб степінь для всіх його вершин була парною. Сьогодні, розглянемо алгоритм, основна ідея якого збігається з алгоритмом обходу графа в глибину, та з його допомогою, для деякого неорієнтований граф , знайдемо Ейлерів цикл. Для цього, припустимо, що вимога зв’язності і парності степенів для нього виконується. Відмітимо, що в такому випадку граф є, принаймі, двозв’язним а отже, містить цикл.

Графічне представлення алгоритму пошуку Ейлерового циклу

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

Позначимо знайдений таким чином цикл як . Якщо включає всі ребра графа , то Ейлерів цикл побудовано. В іншому випадку, переходимо до розгляду графа , який отримуємо шляхом видалення з графа всіх ребер, що входять до графу . Цей граф може бути як зв’язним, так і не зв’язним, але будь-яка його компонента в силу зв’язності має хоча б одну загальну вершину з графом . Так як кожна вершина в і має парну степінь, то і в степінь всіх вершин повинна бути парною.

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

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

Зауваження: головна відмінність розглядуваного алгоритму від пошуку в глибину полягає в тому, що як пройдені позначаються саме ребра, а не вершини. Тому одна і та ж вершина може відвідувати кілька разів, але кожне ребро проходиться не більше одного разу, так що в отриманому маршруті ребра не повторюватимуться.

Ейлерів цикл в неорієнтованому графі – приклад знаходження:

Побудувати Ейлерів цикл для неорієнтованого графа наступного вигляду.

Неорієнтований граф задачі

Проаналізувавши заданий граф бачимо, що кожна з його вершина має парну степінь, тому цей граф Ейлерів, а отже містить Ейлерів цикл. Застосуємо для нього розглянутий вище алгоритм. Для цього, на першому кроці, виберемо в якості початкової вершину номер «1», та скориставшись одним з не пройдених інцидентних їй ребер, наприклад , переходимо у вершину номер «2». Ребро після цього вважається пройденим. Після цього, скориставшись не пройденим інцидентним ребер, але на цей раз для вершини «2», переходимо у вершину «3». Продовжуючи аналогічні дії далі, отримаємо список вершин, послідовний обхід яких і утворюватиме для заданого графа наступний Ейлерів ланцюг: .

Лекція 23. Зв’язність графів

Означення 23.1. Дві вершини v і w називаються зв’язаними, якщо існує маршрут вигляду (…, v₁, e₁, v₂, e₂, …, v_n-1, e_n-1, v_n, …) із кінцями v та w. В цьому випадку також говорять, що вершина v досяжна з вершини w.

За означенням кожна вершина зв’язана сама з собою маршрутом довжиною 0.

Означення 23.2. Граф називається зв’язним, якщо будь-яка пара його вершин є зв’язаною. Зв’язністю графа називається мінімальна кількість вершин, вилучення яких приводить до утворення незв’язного графа.

Зв’язність – це бінарне відношення на множині вершин. Воно рефлексивне (кожна вершина зв’язана сама із собою за означенням), симетричне (для кожного маршруту є обернений маршрут) та транзитивне. Транзитивність означає, що якщо є маршрут з v до w та маршрут з w до u, то є маршрут з v до u. Це очевидно: щоб отримати такий маршрут, достатньо до послідовності ребер, які ведуть з v до w, дописати справа послідовність ребер, яка веде з w до u.

Таким чином, відношення зв’язності є відношенням еквівалентності на множині вершин графа G і розбиває цю множину на підмножини, що не перетинаються, – класи еквівалентності. Всі вершини одного класу зв’язані між собою, вершини різних класів між собою не зв’язані. Підграф, утворений всіма вершинами одного класу, називається компонентною зв’язності графа G.

Неважко показати, що справджується наступна лема.

Лема 23.1. Нехай G = (V, E) – граф із p компонентами зв’язності G₁ = (V₁, E₁), …, G_p = (V_p, E_p). Тоді

Теорема 23.1. Якщо дві вершини зв’язані між собою, то існує простий ланцюг, який іх зв’язує.

Доведення. Дійсно, якщо маршрут, який зв’язує дві вершини, не є простим ланцюгом, то в ньому є вершина v, яка інцидентна більш ніж двом ребрам цього маршруту. Нехай e_i – перше з цих ребер, e_j – останнє (j > i+1). Тоді з даного маршруту можна видалити ділянку від i+1-го ребра до j-1-го. Отримана послідовність залишиться маршрутом: в ній всі ребра e_i та e_j стануть сусідніми, і при цьому вони мають спільну вершину v. Якщо отриманий маршрут не є простим ланцюгом, то процес повторюється до отримання простого ланцюга. ►

Розглянемо неорієнтовані графи K_n та C_n. Обидва ці графи зв’язані, проте інтуїтивно зрозуміло, що для n>3 граф K_n «сильніше зв’язаний», ніж граф C_n. Розглянемо два поняття, які характеризують міру зв’язності простого графу.

Означення 23.3. Числом вершинної зв’язності (G) простого графа G називають найменшу кількість вершин, вилучення яких утворює незв’язаний або одновершинний граф. Зазначимо, що вершину вилучають разом із інцидентними їй ребрами.

Означення 23.4. Нехай G – простий граф з n>1 вершинами. Числом реберної зв’язності (G) графа G називають найменшу кількість ребер, вилучення яких дає незв’язаний граф. Число реберної зв’язності одновершинного графа вважають рівним 0.

Означення 23.5. Вершину u простого графа G називають точкою з’єднання, якщо граф G в разі її вилучення матиме більше компонент, ніж даний граф G. Тобто кількість компонент зв’язності при вилученні цієї вершини у графа G збільшується. Множина ребер графа називається розрізом, якщо вилучення цих ребер з графа G приводить до збільшення кількості компонент зв’язності. Якщо розріз містить одне ребро, то його називають мостом.

Граф називається роздільним, якщо він містить хоча б одну точку з’єднання, та нероздільним в іншому випадку. Максимальні нероздільні підграфи графа називаються блоками.

Отже, точки з’єднання й мости – це своєрідні «вузькі місця» простого графа.

Граф на рис. 23.1 має три точки з’єднання v₄, v₅ та v₇ й один міст (v₄, v₅).

Позначимо як (G) мінімальний степінь вершин графа G. Можна довести, що (G)(G) (G).

Означення 23.6. Простий граф називається t-зв’язним, якщо (G)t, тобто, якщо, вилучаючи будь-яку його t-1 вершину, не можна порушити його зв’язність, а при вилученні деяких t вершин зв’язність може порушитися. Граф називається t-ребернозв’язним, якщо (G)t, тобто якщо t – максимальне з таких p, що при вилученні будь-яких p-1 ребер зв’язність графа не порушується.

Теорема 23.2. Вершина v є точкою з’єднання зв’язного графа G тоді й тільки тоді, коли існують такі вершини w та u, відмінні від v, що довільний маршрут між ними проходить через v.

Доведення. Нехай v – точка з’єднання. Її видалення дає новий граф G’, який містить декілька компонент зв’язності. Оберемо вершини w та u таким чином, щоб вони містились в різних компонентах зв’язності. Тоді у G’ між ними немає маршруту. Але в G (в силу його зв’язності) між ними є маршрути (принаймні один). Отже, саме видалення v розірвало ці маршрути, а, відповідно, всі вони проходять через v.

Нехай тепер існують вершини w та u, вказані в умові теореми. Тоді видалення v розірве всі маршрути між ними, граф стає незв’язним, і, відповідно, v – точка з’єднання. ►

Очевидно, що кількість ребер у зв’язномі графі з n вершинами не перевищує кількості ребер у графі K_n, тобто n(n-1)/2. Але скільки може бути ребер у простому графі з n вершинами й фіксованою кількістю компонент?

Теорема 23.3. Якщо простий граф G має n вершин і k компонент зв’язності, то кількість m його ребер задовольняє нерівності

Доведення. Доведемо спочатку верхню оцінку. Нехай G – простий граф з n вершинами, k компонентами й максимальною для таких графів кількістю ребер m_max. Очевидно, що кожна компонента графа G – повний граф. Нехай K_p, K_q – дві компоненти, pq>1, v – вершина з другої компоненти. Вилучимо з графа всі ребра, інцидентні вершині v, і з’єднаємо цю вершину ребром із кожною вершиною першої компоненти. Кількість вершин і компонент при цьому не зміниться, а кількість ребер зросте на p – (q–1) = p – q + 1, що неможливо, бо граф G має максимально можливу кількість ребер. Отже, лише одна компонента графа G являє собою повний граф із більшою ніж 1 кількістю вершин n – (k – 1) = n – k +1. Отже, m_max = (1/2)(n–k)( n – k +1).

Доведемо нижню оцінку математичною індукцією за кількістю ребер m. Для m=0 твердження очевидне, оскільки тоді k=n і, отже, 00. Нехай тепер m>0, і нижня оцінка справджується для графів із меншою кількістю ребер, ніж m. Припустимо, що граф G має найменшу можливу кількість ребер m_min серед усіх простих графів з n вершинами й k компонентами. Вилучивши довільне ребро отримаємо граф з n вершинами, k+1 компонентою й m_min – 1 ребром. Для нього справджується припущення індукції: n – (k + 1)  m_min – 1, звідки випливає нерівність n – k  m_min. ►

Наслідок. Всякий граф порядку n, який має більше (n – 1)(n – 2)/2 ребер, зв’язний.

Доведення. Дійсно, в цьому випадку число компонентів зв’язності такого графа повинне бути строго менше двох. Отже, k=1, тобто граф зв’язний. ►

Теорема 23.4. Для будь-якого графа G або він сам, або його доповнення є зв’язним.

Доведення. Нехай G=(V, E) – незв’язний граф, А – одна із його компонент зв’язності і B = V\A. Тоді для будь-яких вершин u із А і v із В в графі є маршрут довжиною 1, оскільки ці вершини зв’язані ребром (u,v). Отже, всяка вершина із В зв’язана з вершиною u маршрутом довжини 1, а всяка вершина із А – з u маршрутом довжини, не більше 2. Тобто всяка вершина u зв’язана з будь-якою вершиною v маршрутом. Значить, – зв’язний граф. ►

Теорема 23.5. Нехай G=(V, E) – зв’язний граф і eE – деяке його ребро. Тоді якщо е належить деякому циклу, то G-e зв’язний. Якщо ж e не належить жодному циклу, то граф G-е має рівно дві компоненти зв’язності.

Доведення. Нехай e=(v,u) належить деякому циклу C графа G. Виконаємо заміну в кожному ланцюгові, який з’єднує вершини x та y і включає ребро e, ланцюгом C-e. Отримаємо маршрут з вершин х в вершину у, який не має ребра е. Тобто в графі G всякі дві вершини, які не співпадають між собою, з’єднані маршрутом. А це означає, що G-e зв’язний.

Нехай тепер e=(v,u) не входить в жодний цикл графа G. Тоді очевидно, що вершини u і v належать різним компонентам зв’язності, наприклад: G_v і відповідно G_u графа G-e. Для довільної вершини xv в G існує маршрут із x в v в силу зв’язності G. Якщо е в цей маршрут не входить, то xG_u. Тобто G_v і G_u – компоненти зв’язності. ►

Ці теореми дають деяку характеристику операцій вилучення ребра по відношенню до властивості зв’язності. Ясно, що обернена операція – операція введення ребра – не порушує цієї властивості.