Основні поняття і терміни теорії графів.

Перш, ніж розпочати огляд термінології, введемо поняття множини.

Множина — це сукупність однотипних оєктів, елементів. Позначається великими латинськими літерами (A, B, M, N, …), а елементи множини маленькими (a, b, m, n, …). Множина може бути скінченною або нескінченною.

Порожня множина не має жодного елемента. Вираз означає, що елемент a належить множині B. Всі елементи множини M є також елементами множини N записується виразом . Операції над множинами і детальніше про множини див. [16].

Нехай V  деяка непорожня скінченна множина, а Е  множина всіх двоелементних підмножин (невпорядкованих пар різних елементів) множини V. Графом (неорієнтованим графом) G називається пара множин (V,E).

Елементи множини V називаються вершинами графа G, а елементи множини E  ребрами графа G.

Традиційно ребра неорієнтованого графа записуються малими латинськими літерами е_1, е₂, … як елементи множини Е, або за допомогою круглих фігурних дужок з елементами множини V, які утворюють ребро {v,w}, оскільки порядок вершин неістотний.

Граф, який складається з однієї вершини, називається тривіальним.

Нехай задано граф G =(V,E ). Якщо {v,w}Е, то кажуть, що вершини v i w є суміжними, у протилежному випадку вершини v i w є несуміжними. Якщо е=(v,w) — ребро графа, то вершини v i w називаються кінцями ребра е. У цьому випадку кажуть також, що ребро е з’єднує вершини v i w. Вершина v і ребро е називаються інцидентними, якщо v є кінцем е.

Два ребра суміжні, якщо вони мають спільну вершину.

Одним зі способів задання графа G =(V,E ) є задання кожної з множин V і E за допомогою переліку їх елементів.

Приклад. Граф G₁=(V₁,E₁), V₁={v₁,v₂,v₃,v₄} і E₁={(v₁,v₃), (v₁,v₄),(v₂,v₃),(v₂,v₄),(v₃,v₄)} — це граф із чотирма вершинами і п’ятьма ребрами.

Граф G =(V,E ) зручно зображати графічно. Вершинам графа G є точки площини; точки, що відповідають вершинам v i w, з’єднуються лінією, коли v i w суміжні вершини.

Приклад. На рис. 1 зображений графічно граф G₁ з попереднього прикладу.

G₁

Рис. 1.

Графи можна задавати також за допомогою матриць, занумерувавши всі вершини графа G натуральними числами від 1 до n. Матрицею суміжності A графа G називається квадратна nхn-матриця, в якій елемент a_ij i-го рядка і j-го стовпчика дорівнює 1, якщо вершини v_i та v_j з номерами i та j суміжні, і дорівнює 0 в іншому випадку.

Приклад. Для графа G₁

A₁=

Очевидно, що матриці суміжності графів  симетричні.

Занумеруємо всі вершини графа G числами від 1 до n і всі його ребра  числами від 1 до m. Матрицею інцидентності B графа G називається nхm-матриця, в якій елемент b_ij i-го рядка і j-го стовпчика дорівнює 1, якщо вершина v_i з номером i інцидентна ребру e_j з номером j, і дорівнює 0 у противному разі.

Приклад. Для графів G₁

B₁=

Ще одним способом завдання графів є списки суміжності. Кожній вершині графа відповідає свій список. У список, що відповідає вершині v, послідовно записуються всі суміжні їй вершини.

Приклад. Для графів G₁ маємо список

G₁:

v₁: v₃,v₄

v₂: v₃,v₄

v₃: v₁,v₂,v₄

v₄: v₁,v₂,v₃

Граф G₁=(V₁,E₁) називається підграфом графа G =(V,E ), якщо V₁ V i E₁ E.

Важливі класи підграфів складають підграфи, які отримуються в результаті застосування до заданого графа операції вилучення вершини і/або операції вилучення ребра.

Операція вилучення вершини v з графа G =(V,E ) полягає у вилученні з множини V елемента v, а з множини E  всіх ребер, інцидентних v.

Операція вилучення ребра e з графа G =(V,E )  це вилучення елемента e з множини E. При цьому всі вершини зберігаються.

Графи називаються ізоморфними, якщо вони відрізняються фактично лише ідентифікаторами (іменами) своїх вершин.

Степенем (v) вершини v називається кількість ребер, інцидентних вершині v.

Вершина степеня 0 називається ізольованою, а вершина степеня 1  кінцевою (або висячою) вершиною.

У будь-якому графі G =(V,E ) (v)=2|E |.

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

У будь-якому графі G =(V,E ) кількість вершин непарного степеня парна.

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

v₁, e₁, v₂, e₂, … , e_k, v_k +1

вершин v_i і ребер e_i така, що кожні два сусідні ребра в цій послідовності мають спільну вершину, отже, e_i=(v_i,v_i +1), i=1,2,…,k. Вершина v₁ називається початком шляху, а вершина v_k +1  кінцем шляху. Всі інші вершини цього шляху називаються проміжними, або внутрішніми, вершинами.

Кількість k ребер у маршруті називається довжиною маршруту. Кажуть, що цей маршрут з’єднує вершини v₁ і v_k +1 або веде з вершини v₁ у вершину v_k +1.

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

Маршрут v₁, e₁, v₂, e₂, … , e_k, v_k +1 називається замкненим (або циклічним), якщо v₁=v_k +1. Замкнений ланцюг називається циклом, а замкнений простий ланцюг  простим циклом.

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

Граф називається зв’язним, якщо будь-яка пара його вершин може бути з’єднана деяким маршрутом.

Компонентою зв’язності (або зв’язною компонентою) графа G називається його зв’язний підграф такий, що він не є власним підграфом жодного іншого зв’язного підграфа графа G.

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

Для будь-яких вершин v,w,  uV виконується

1) d (v,w)  0; d (v,w)=0 тоді і тільки тоді, коли v = w;

2) d (v,w)=d (w,v);

3) d (v,w)  d (v,u)+d (u,w).

Ексцентриситетом e(v) довільної вершини v зв’язного графа G =(V,E ) називається найбільша з відстаней між вершиною v і всіма іншими вершинами графа G, тобто e(v)= {d(v,w)}.

Діаметром зв’язного графа G (позначається D (G )) називається максимальний з усіх ексцентриситетів вершин графа G. Мінімальний з усіх ексцентриситетів вершин зв’язного графа G називається його радіусом і позначається R (G ).

Вершина v називається центральною, якщо e (v)=R (G ). Центром графа G називається множина всіх його центральних вершин.

Вершини v i w графа G називаються зв’язаними, якщо в G існує маршрут, що з’єднує v і w.

Для різних практичних застосувань теорії графів важливою є проблема систематичного обходу (перебору) всіх вершин і/або ребер графа. Двома класичними методами розв’язання цих проблем є: метод пошуку (обходу графа) вшир та метод пошуку (обходу графа) вглиб.

Алгоритми, які шукають шляхи найменшої вартості називаються алгоритмами пошуку найкоротших шляхів. Вони описані в [2,7,8].

Граф без циклів називається ациклічним.

Ациклічний зв’язний граф називається деревом.

Довільний ациклічний граф називається лісом.

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

Існують й інші, рівносильні наведеному, означення дерева, які можна розглядати як характеристичні властивості дерева.

Для графа G  =(V,E ), |V |=n, |E |=m такі твердження рівносильні:

1) G  дерево (ациклічний зв’язний граф);

2) G  зв’язний граф і m =n 1;

3) G  ациклічний граф і m = n 1;

4) для будь-яких вершин v і w графа G існує лише один простий ланцюг, що з’єднує v і w ;

5) G  ациклічний граф такий, що коли будь-які його несуміжні вершини v i w з’єднати ребром (v,w), то одержаний граф міститиме рівно один цикл.

Кістяковим (каркасним) деревом зв’язного графа G =(V,E ) називається дерево T = (V,E_T) таке, що E_T   E.

Кістяковим (каркасним) лісом незв’язного графа G =(V,E ) називається сукупність кістякових (каркасних) дерев зв’язних компонент графа G.

Для зв’язного графа G =(V,E ) можна вказати |E ||V |+1 ребро, після вилучення яких отримаємо кістякове дерево графа G.

Нехай граф G =(V,E ) має k компонент зв’язності. Для отримання його кістякового лісу з графа G необхідно вилучити |E | |V |+k ребер.

Число |E | |V |+k називається цикломатичним числом графа G і позначається (G ).

Лема.

1). Для довільного графа G виконується (G )  0.

2). Граф G є лісом тоді і тільки тоді, коли (G ) = 0.

3). Граф G має рівно один простий цикл тоді і тільки тоді, коли (G )=1.

4). Кількість циклів у графі G не менша ніж (G ).

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

Граф називають планарним, якщо він ізоморфний деякому плоскому графу.

Наприклад, граф, зображений на рис. 2.а, планарний, оскільки він ізоморфний графу, зображеному поруч. Простий цикл, дерево і ліс  це також планарні графи.

Очевидними є такі твердження.

1). Будь-який підграф планарного графа є планарним.

2). Граф є планарним тоді і тільки тоді, коли кожна його зв’язна компонента  планарний граф.

Про планарні графи кажуть, що вони укладаються на площині або мають плоске укладання.

а) б)

Рис. 2.

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

На рис. 3 зображено плоский граф із п’ятьма гранями.

v₁₃

v₁₄

Рис. 3. ([9])

Отже, плоский граф розбиває всю множину точок площини на грані так, що кожна точка належить деякій грані. Відзначимо, що плоский граф має одну, причому єдину, необмежену грань (на рис.3 це грань 5). Таку грань будемо називати зовнішньою, а всі інші  внутрішніми гранями.

Множину граней плоского графа позначатимемо через P.

Степенем грані r називатимемо довжину циклічного шляху, що обмежує грань r (тобто довжину межі грані r ); позначається _r.

Теорема Ейлера. Для будь-якого зв’язного плоского графа G =(V,E ) виконується рівність

|V ||E |+|P |=2.

При дослідженні плоских графів особливе місце займають графи K₅ i K_3,3, зображені на рис. 4.

K₅ K_3,3

Рис. 4.

Теорема. Графи K₅ i K_3,3 не є планарними.

Значення графів K₅ i K_3,3 полягає в тому, що всі інші непланарні графи містять у собі підграфи "подібні" до K₅ або K_3,3. Характер цієї подібності розкривається за допомогою таких понять.

Елементарним стягуванням графа G =(V,E ) називається вилучення в графі G деякого ребра (v_i,v_j)E і злиття вершин v_i i v_j в одну вершину v, причому v інцидентна всім тим відмінним від (v_i,v_j) ребрам графа G, які були інцидентні або v_i , або v_j.

Кажуть, що граф G стягується до графа G , якщо G  можна отримати з G за допомогою послідовності елементарних стягувань.

Приклад. На рис. 5 зображено графи G i G , при цьому G стягується до G .

G G 

Рис. 5.

Наведемо важливу теорему теорії графів.

Теорема Куратовського. Граф G є планарним тоді і тільки тоді, коли він не містить підграфів, що стягуються до K₅ або K_3,3.

Нехай G =(V,E ) довільний граф, а N_k={1,2,...,k }.

Будь-яке відображення f :V  N_k, яке ставить у відповідність кожній вершині v V деяке натуральне число f (v) N_k, називається розфарбуванням графа G. Число f  (v) називається кольором або номером фарби вершини v.

Розфарбування f графа G називається правильним, якщо для будь-яких його суміжних вершин v і w виконується f  (v)  f (w).

Мінімальне число k, для якого існує правильне розфарбування графа G, називається хроматичним числом графа G і позначається (G ).

Мінімальним правильним розфарбуванням графа G називається правильне розфарбування для k=(G ).

Справедливими є такі твердження.

Якщо кожна зв’язна компонента графа G потребує для свого правильного розфарбування не більше k фарб, то (G )k.

Граф є біхроматичний тоді і тільки тоді, коли він не має циклів непарної довжини.

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

Теорема. Позначимо через (G ) найбільший зі степенів вершин графа G, тоді (G )  (G )+1.

Як наслідок, для правильного розфарбування довільного кубічного графа достатньо чотири фарби.

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

Грані плоскої карти назвемо суміжними, якщо їхні межі мають принаймні одне спільне ребро.

Гіпотеза чотирьох фарб виникла у зв’язку з розфарбуванням друкованих географічних карт (звідси й термін "плоска карта") і формулювалась так:

“Грані довільної плоскої карти можна розфарбувати не більше ніж чотирма фарбами так, що будь-які суміжні грані матимуть різні кольори”.

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

Для правильного розфарбування вершин довільного планарного графа потрібно не більше чотирьох фарб.

Справедливі наступні твердження.

Теорема. Планарний граф є біхроматичний тоді і тільки тоді, коли степені всіх його граней парні.

Теорема. Для правильного розфарбування довільного планарного графа потрібно не більше шести фарб.

Початок теорії графів пов’язують із задачею про кенігсберзькі мости. Сім мостів міста Кенігсберга були розташовані на річці Прегель так, як зображено на рис. 6,а.

а) б)

Рис. 6. ([9])

Задача полягає в тому, чи можна, починаючи з будь-якої точки (А,B,C або D), здійснити прогулянку (обхід) через усі мости так, щоб пройти кожен міст тільки один раз і повернутися у вихідну точку.

Оскільки суттєвими є тільки переходи через мости, то план міста можна зобразити у вигляді графа G , вершинами якого є береги і острови (точки А,В,С і D), а ребрами  мости (див. рис. 6,б). Тоді задачу про кенігсберзькі мости можна мовою теорії графів сформулювати таким чином: чи існує в графі G цикл, який містить усі ребра цього графа? Інше відоме формулювання цієї проблеми виглядає так: чи можна намалювати фігуру, що зображає граф G, не відриваючи олівця від паперу і не повторюючи ліній двічі, почавши і закінчивши цю процедуру в одній з вершин фігури? Вперше відповідь на це питання дав Л.Ейлер у 1736 році. Робота Ейлера, яка містить цей розв’язок, вважається початком теорії графів.

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

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

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

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

Для знаходження деякого ейлерового циклу в ейлеровому графі G можна застосувати так званий алгоритм Фльорі.

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

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

Орієнтованим графом, або орграфом, G називається пара множин (V,E ), де Е V V. Елементи множини V називаються вершинами орграфа G, а елементи множини Е  дугами орграфа 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 у вигляді {v₁,v₂,...,v_n}. Матрицею суміжності А орграфа G називається квадратна матриця порядку n, в якій елемент і-го рядка і j-го стовпчика

1, якщо (v_i,v_j)E ;

a_ij =

0, у протилежному випадку.

Занумеруємо всі вершини орграфа G =(V,E ) числами від 1 до n, а дуги  числами від 1 до m. Матрицею інцидентності В орграфа G називається nm-матриця, в якій елемент і-го рядка і j-го стовпчика

1, якщо вершина v_i є початком дуги e_j ;

b_ij = 1, якщо вершина v_i є кінцем дуги e_j ;

0, якщо вершина v_i і дуга e_j неінцидентні.

Півстепенем виходу вершини v (позначається ⁺(v)) орграфа G називається кількість дуг орграфа G, початком яких є вершина v. Півстепенем заходу вершини v (позначається ^—(v)) орграфа G називається кількість дуг орграфа G, кінцем яких є вершина v.

Теорема. Для будь-якого орграфа G =(V,E ) виконуються рівності

⁺(v) = ^—(v)= |E |.

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

Маршрутом або шляхом в орграфі G =(V,E ) називається послідовність його вершин і дуг

v₁, e₁, v₂, e₂, … , e_k, v_k +1

така, що e_i = (v_i,v_i +1), i=1,2,...,k. Кажуть, що цей маршрут веде з вершини v₁ у вершину v_k +1. Число k дуг у маршруті називається його довжиною.

Маршрут, в якому всі дуги попарно різні, називається ланцюгом. Маршрут, в якому всі вершини попарно різні, називається простим ланцюгом. Маршрут називається замкненим (або циклічним), якщо v₁=v_k +1. Замкнений ланцюг називається циклом, а замкнений простий ланцюг  простим циклом, або контуром.

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

Якщо існує маршрут, який веде з вершини v у вершину w, то кажуть, що вершина w є досяжною з вершини v. У цьому випадку відстанню d (v,w) від вершини v до вершини w називається довжина найкоротшого маршруту, що веде з v y w. Відстань між вершиною v i вершиною w, яка є недосяжною з v, позначається символом .

Повним орграфом (або турніром) називається орграф G, в якому будь-які дві вершини є інцидентними одній і тільки одній дузі орграфа G.

Для повних орграфів справедливі такі твердження:

У будь-якому повному орграфі завжди є принаймні одне джерело і принаймні один стік.

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

Послідовність v₁, e₁, v₂, e₂, … , e_k, v_k +1 називається напівмаршрутом, якщо при побудові ігноруємо орієнтацію дуг орграфа. Аналогічно означаються напівланцюг, напівцикл і напівконтур.

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

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

Теорема. Орграф є сильно зв’язним тоді і тільки тоді, коли він має замкнений кістяковий маршрут.

Теорема. Орграф є однобічно зв’язним тоді і тільки тоді, коли він має кістяковий маршрут.

Теорема. Орграф є слабо зв’язним тоді і тільки тоді, коли він має кістяковий напівмаршрут.

Орграф, у якому є джерело і немає жодного напівконтура, називається кореневим деревом. Вхідне дерево  це орграф, який має стік і не має жодного напівконтура.

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

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

Гамільтоновим контуром називається контур, що містить усі вершини орграфа. Орграф, який має гамільтонів контур, називається гамільтоновим орграфом. Простий ланцюг, що містить всі вершини орграфа, називається гамільтоновим.