Материал: discrete_mathematics

двічі, почавши й закінчивши процедуру в одній із вершин фігури? Уперше відповідь на це запитання дав Л. Ейлер у 1736 р. Його роботу, у якій викладено розв'язок задачі, вважають початком теорії графів.

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

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

Оскільки для графа G на рис. 4.11, б умови теореми Ейлера не виконуються, то в задачі про кенігсберзькі мости відповідь негативна.

Приклад 4.20. Довести, що для довільного зв'язного графа існує циклічний маршрут, який починається з будь-якої вершини й містить усі ребра графа, причому кожне з них – двічі.

Подвоїмо кожне ребро графа G, перетворивши його на мультиграф G′ (див. п. 4.11). Степені всіх вершин G′ парні, тому за теоремою Ейлера в G′ існує цикл, що містить усі його ребра. Циклу відповідає шуканий циклічний маршрут у графі G. ◄

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

Для знаходження якогось ейлерового циклу в ейлеровому графі G можна застосувати алгоритм Фльорі. Фіксуємо довільну початкову вершину циклу. На кожному кроці процедури до шуканого циклу обираємо (доки це можливо) те ребро, після вилучення якого граф не розіб'ється на дві нетривіальні зв'язні компоненти. Кожне обране ребро вилучаємо із G. Процедуру завершуємо, коли всі ребра буде вичерпано. Сформульований алгоритм будує ейлерів цикл графа G.

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

вають гамільтоновим циклом. Граф називають гамільтоновим,

якщо він має гамільтонів цикл.

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

191

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

Незамкнений ланцюг, що містить усі ребра графа, називають ейлеровим, а простий незамкнений ланцюг, що містить усі вер-

шини графа, – гамільтоновим ланцюгом.

Приклад 4.21. Навести приклади ейлерового графа, який не є гамільтоновим, а також гамільтонового графа, якийнеєейлеровим.

Граф G = (V, E), де

V = {1, 2, 3, 4, 5}, E = {(1,2), (1,3), (2,3), (3,4), (3,5), (4,5)},

є ейлеровим, однак не є гамільтоновим. А будь-який повний граф Kn для непарного n є гамільтоновим, але не ейлеровим. ◄

Завдання для самостійної роботи

1.Визначити, які з повних графів Kn є ейлеровими.

2.Для яких значень n і m повний двочастковий граф Kn,m є ейлеровим?

3.Довести, що зв'язний граф має ейлерів ланцюг тоді й тільки тоді, коли він має тільки дві вершини з непарними степенями.

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

5.Довести, що в повному графі Kn існує гамільтонів цикл для довільного n ≥ 3.

4.11. Орієнтовані графи

Крім моделі, розглянутої у попередніх параграфах, у теорії графів досліджують також інші типи графів. Наприклад, муль тиграф − граф, у якому дозволяються кратні ребра, тобто будьякі дві вершини можна з'єднати кількома ребрами. Псевдограф − це мультиграф, який може мати петлі, тобто ребра, що з'єднують вершину саму із собою. Гіперграф − граф, у якому ребрами можуть бути не лише двоелементні, але й довільні підмножини множини вершин. Нарешті, важливою для різноманітних практичних застосувань є модель, яку називають орієнто

192

ваним графом (або орграфом). Подамо короткий огляд основних понять і результатів для орграфів.

Орієнтованим графом (орграфом) G називають пару мно-

жин (V, E), де Е V × V. Елементи множини V називають вер шинами, а елементи множини Е − дугами орграфа G = (V, E). Отже, дуга − це впорядкована пара вершин; V називають мно жиною вершин, Е − множиною дуг орграфа G.

Якщо е = (v, w) − дуга, то вершину v називають початком, а вершину w − кінцем дуги е. Кажуть, що дуга е веде із вершини v у вершину w, або виходить із v і заходить у w. Дугу е та вершини v і w називають інцидентними між собою, а вершини v i w

– суміжними.

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

Як і звичайний граф, орграф G = (V, E) можна задавати переліком елементів скінченних множин V i E, діаграмою або за допомогою матриць.

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

Поставимо у відповідність усім вершинам орграфа G = (V, E) натуральні числа від 1 до n; дістанемо множину вершин V у вигляді {v1, v2, …, vn}. Матрицею суміжності А орграфа G називають квадратну матрицю порядку n, у якій елемент і-го рядка та j-го стовпчикаaij дорівнює 1, якщо (vi, vj) E, і дорівнює 0 в іншому разі.

Занумеруємо всі вершини орграфа G = (V, E) числами від 1

до n, а дуги − числами від 1 до m. Матрицею інцидентності В

орграфа G називають n ×m-матриця, у якій елемент і-го рядка та j-го стовпчика bij дорівнює 1, якщо вершина vi є початком дуги ej, bij дорівнює −1, якщо вершина vi є кінцем дуги ej, і bij дорівнює 0, якщо вершина vi і дуга ej неінцидентні.

Орграфи G1 = (V1, E1) i G2 = (V2, E2) називають ізоморфними, якщо існує таке взаємно однозначне відображення ϕ множини

V1 на множину V2, що дуга (v, w) Е1 тоді й тільки тоді, коли ду-

га (ϕ(v), ϕ(w)) Е2.

Напівстепенем виходу вершини v (позначають δ+(v)) орграфа

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

193

Напівстепенем заходу вершини v (позначають δ–(v)) орграфа

G називають кількість дуг орграфа G, кінцем яких є вершина v.

Приклад 4.22.

1. Довести, що для довільного орграфа G = (V, E) виконується

рівність

∑δ(v) = ∑δ− (v).

v V v V

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

2. Чи існує орграф із п'ятьма вершинами, напівстепені виходу вершин якого дорівнюють 4, 2, 1, 0, 1, а відповідні напівстепені заходу − 3, 2, 1, 1, 2?

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

3. Чи існує орграф із чотирма вершинами, напівстепені виходу вершин якого дорівнюють 3, 1, 3, 0, а відповідні напівстепені заходу − 1, 2, 1, 3?

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

Маршрутом, або шляхом, в орграфі G = (V, E) називають та-

ду, тобто v1, v2, … , vk + 1.

Маршрут, у якому всі дуги попарно різні, називають ланцю гом, а маршрут, у якому всі вершини попарно різні, – простим

194