мулюють достатні умови існування гамільтонового циклу в заданому графі. Доведення таких теорем зазвичай містять і алгоритми побудови відповідних гамільтонових циклів.
Незамкнений ланцюг, що містить усі ребра графа, називають ейлеровим, а простий незамкнений ланцюг, що містить усі вер-
шини графа, – гамільтоновим ланцюгом.
Приклад 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?
0 |
1 |
1 |
1 |
|
|
|
|
0 |
0 |
0 |
1 |
|
|
Так, А= |
|
− його матриця суміжності. ◄ |
||||
|
1 |
1 |
0 |
1 |
|
|
|
0 |
0 |
0 |
0 |
|
|
|
|
|
||||
Чималу частку властивостей і тверджень стосовно звичайних графів можна без змін сформулювати й для орграфів. Зокрема, це стосується цілих розділів (таких, наприклад, як планарність або розфарбування графів), у яких властивість орієнтації ребер неістотна. Певні особливості в означеннях, постановках задач і методах їх розв'язання виникають при дослідженні проблем, по- в'язаних із маршрутами, зв'язністю, обходами графів тощо.
Маршрутом, або шляхом, в орграфі G = (V, E) називають та-
ку послідовність його вершин і дуг |
|
|
|
|
(4.4)з |
||
|
v1, e1, v2, e2, … , ek, vk + 1, |
|
|
|
|||
що ei = (vi, vi + 1), i = 1, 2, …, k. Кажуть, що цей маршрут |
|||||||
|
|
|
|
|
|
веде |
|
вершини v у вершину vk + 1. Кількість k дуг у маршруті |
(4.4) |
на- |
|||||
зивають його1 |
довжиною. |
|
|
|
|
||
Як і для графів, розглянутих вище, маршрут |
|
можна запи- |
|||||
сувати лише як послідовність вершин, що |
входять до його скла- |
||||||
|
(4.4) |
|
|
|
|
||
ду, тобто v1, v2, … , vk + 1.
Маршрут, у якому всі дуги попарно різні, називають ланцю гом, а маршрут, у якому всі вершини попарно різні, – простим
194
ланцюгом. Маршрут (4.4) називають замкненим (або цикліч ним), якщо v1 = vk + 1. Замкнений ланцюг називають циклом, а замкнений простий ланцюг − простим циклом, або контуром.
Орграф називають ациклічним (або безконтурним), якщо він не має жодного циклу.
Якщо існує маршрут, який веде з вершини v у вершину w, то кажуть, що вершина w досяжна з вершини v. Тоді відстанню d(v, w) від вершини v до вершини w називають довжину найкоротшого маршруту, що веде з v y w.
Вершину v орграфа G називають джерелом, якщо з неї досяжна будь-яка інша вершина орграфа G. Вершину w називають стоком, якщо вона досяжна з будь-якої іншої вершини орграфа G. Вершина v орграфа G називають тупиковою, якщо жодна із вершин орграфа G не досяжна з v. Вершину v орграфа G називають недосяжною, якщо вона не досяжна з жодної вершини орграфа G.
Повним орграфом (або турніром) називають орграф, у якому будь-які дві вершини інцидентні одній і тільки одній його дузі.
Приклад 4.23.
1. Для довільного повного орграфа G = (V, E) з n вершинами {v1, v2, …, vn} виконуються такі рівності:
n
(а) ∑δ+
i=1
|
|
|
|
n |
n |
(vi ) = |
|
E |
|
; (б) |E| = n(n – 1)/2; в) ∑(т−1−δ+ (vi )) =∑δ+ (vi ). |
|
|
|
||||
|
|
|
|
i=1 |
i=1 |
(а) У будь-якому орграфі G (зокрема повному) кількість дуг |E| збігається з кількістю початків цих дуг (і, відповідно, з кількістю кінців усіх дуг).
(б) Кількість дуг у повному орграфі G збігається з кількістю ребер у відповідному неорієнтованому повному графі G′, тобто в графі, який отримаємо з G, замінивши в ньому всі орієнтовані дуги на неорієнтовані ребра (див. приклад 4.7 (1)).
(в) У повному орграфі з n вершинами для всіх вершин виконуються рівності
n – 1 – δ+(vi) = δ–(vi), i = 1, 2, 3, ..., n.
Отже, сума в лівій частині рівності є кількістю кінців усіх дуг повного орграфа G, а сума в правій частині – кількістю початків усіх його дуг. Ці кількості, очевидно, збігаються.
2. Довести, що в будь-якому повному орграфі G = (V, E) є принаймні одне джерело.
195
Для доведення твердження застосуємо метод математичної індукції за кількістю вершин повного орграфа. База індукції: у повному орграфі з двома вершинами одна з них є джерелом (а інша – стоком). Припустимо, що будь-який повний орграф із n вершинами має джерело. Розглянемо довільний повний орграф G = (V, E) з n + 1 вершиною. Вилучивши одну з його вершин v, отримаємо повний орграф із n вершинами, для якого справджується припущення індукції. Отже, у ньому є принаймні одне джерело. Нехай це буде вершина w. Повернемо на місце вилучену вершину v зі всіма відповідними дугами. Оскільки граф G повний, то його вершини v і w з'єднані дугою. Якщо ця дуга веде з v у w (тобто (v, w) E), то джерелом у графі G буде вершина v. В іншому разі, коли (w, v) E, джерелом залишиться вершина w. ◄
3. Нумерацією орграфа G = (V, E) з n вершинами називатимемо взаємно однозначне відображення
f :V → Nn,
яке кожній вершині v V ставить у відповідність натуральне число f (v) із множини Nn = {1, 2, …, n}.
Довести, що для ациклічного орграфа G = (V, E) існує така нумерація f, що для будь-якої дуги (v, w) E виконується
f (v) < f (w).
Цю нумерацію називають правильною нумерацією, або топо
вершин орграфа G.
Неважко довести (методом від супротивного), що ациклічний орграф G завжди має принаймні один стік. Нехай u1 – стік орграфа G. Покладемо f(u1) = n і вилучимо з G вершину u1. Дістанемо ациклічний орграф G1, у якому існуватиме стік u2. Покладемо f(u2) = n – 1 і вилучимо u2 з G1. Продовжуючи цю процедуру, отримаємо шукану правильну нумерацію. ◄
Послідовність (4.4) називають напівмаршрутом, якщо кожна дуга еі цієї послідовності є такою, що або еi = (vi, vi + 1), або ei = (vi + 1, vi) (можна вважати, що при побудові напівмаршруту ми ігноруємо орієнтацію дуг орграфа). Аналогічно означають
напівланцюг, напівцикл і півконтур.
Орграф називають сильно зв'язним, якщо будь-які дві його вершини досяжні одна з одної. Орграф називають однобічно зв'язним, якщо для будь-яких двох його вершин принаймні одна досяжна з іншої. Орграф називають слабко зв'язним, якщо для
196