Елементи теорії графів та гіперграфів

Графом G = (V, E) називається об’єкт, який заданий парою множин (V, E), де V – множина вершин, E ⊆ V×V – множина ребер.

Граф називається скінченним, якщо множини його вершин і ребер є скінченними. Множину вершин графу G позначають V(G), а множину ребер – E(G). Кількість вершин графу n(G) = |V(G)|, а кількість ребер m(G) = |E(G)|.

Кількість вершин n(G) графу називають його порядком.

Якщо для деякого ребра e = (v, w) ∈ E(G), то кажуть:

· Вершини v та w суміжні;

· Вершини v та w інцидентні ребру e;

· Ребро e інцидентне вершинам v і w.

Множина ребер E може бути порожньою. Такий граф називається нуль-графом і позначається ∅. Якщо ж множина вершин V – порожня, то порожньою є також множина E. Такий граф називається порожнім.

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

Цей випадок відповідає наявності в множині E пар вигляду (v, v).

Різні ребра можуть бути інцидентними одній і тій самій парі вершин (тобто одну й ту саму пару вершин з’єднує більше ніж одне ребро), такі ребра називаються кратними.

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

Граф називається мультиграфом, якщо він має кратні ребра.

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

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

Ребро графа називається орієнтованим, якщо цей порядок істотний. У цьому випадку говорять, що для ребра g = (x_i, x_j): x_i - початкова, a x_j - кінцева вершини ребра. Орієнтоване ребро називають дугою графа.

Граф називається неорієнтованим, якщо кожне його ребро є неорієнтованим, і орієнтованим, якщо кожне його ребро є орієнтованим. Якщо граф містить орієнтовані та неорієнтовані ребра, він називається змішаним.

Повним неорієнтованим графом називається граф U(X), ребрами якого є всі можливі пари (x_i, x_j) для всіх вершин x_i, x_j Î X, i ¹ j. У такому графі всі вершини є суміжними.

Повним орієнтованим графом U₀(X) називається граф, у якого будь-які дві вершини з'єднані хоча б в одному напрямку.

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

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

· Ланцюг ― послідовність ребер S = S = (g₁, g₂,..., g_n), в якій у кожного ребра g_k одна з вершин є вершиною ребра g_k-1, а інша - вершиною ребра g_k+1. При цьому одне і те ж ребро або вершина може зустрічатися декілька разів. Ланцюг називається простим, якщо всі ребра в ньому різні, і складним – в іншому випадку. Вершини в простому ланцюзі можуть повторюватися. Ланцюг називається елементарним, якщо в ньому жодна з вершин не повторюється.

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

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

· Шляхом у графі G (X) називається така послідовність дуг (g_l, g₂, …), що кінець кожної попередньої дуги є початком наступної. Існують прості, складні й елементарні шляхи.

· Контур графа – це кінцевий шлях, у якого початкова вершина збігається з кінцевою. Існують прості, складні (складені) і елементарні контури.

· Довжиною шляху є число дуг L(s) в послідовності дуг шляху s. У разі нескінченного шляху L (s) = ¥.

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

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

· Граф називається симетричним, якщо " x_i, x_j з того, що x_i Î G(x_j) Þ x_j Î G(x_i), тобто дві суміжні вершини x_i, x_j завжди з'єднані протилежно орієнтованими дугами.

· Граф називається антисиметричним, якщо " x_i, x_j x_i Î G(x_j) Þ x_j Ï G(x_i), тобто кожна пара суміжних вершин з'єднана тільки в одному напрямку.

Граф Н(х) називається частковим для графа G(X), якщо всі ребра Н(Х) є ребрами G(X) і множина вершин графа Н(Х) збігається з безліччю вершин графа G(X), тобто Н(х) Ì G(x) " х Î X.

Частковий граф містить частину ребер (дуг). Він також може бути орієнтованим або неорієнтованим залежно від вихідного графа.

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

Підграфом G_A(A) графа G(X), де А Ì X, називається граф, вершинами якого є елементи множини А Ì X, а ребрами – все ребра з G, кінцеві вершини яких лежать в А.

Таким чином, підграф містить частину вершин разом з ребрами, що з'єднують ці вершини. Інакше, G_A(A) – підграф графа G(X), якщо А Ì X і G_A(x) = G(x)ÇА " х Î Х.

Якщо А = X, то G_A(A) = G(X). Для єдиної вершини А = {а} підграф GA (a) складається з петель навколо а. Підграфом G_A(A) графа G (X) буде нуль-граф, якщо А Ì X є підмножиною ізольованих вершин графа.

Підграф буде орієнтованим або неорієнтованим залежно від вихідного графа.

Частковим підграфом Н_А(А), А Ì X графа G(X) називається підграф, ребрами якого є деякі ребра з G(X), обидва кінці яких лежать в А. Інакше, Н_А(А) – частковий підграф графа G(X), якщо А Ì X і Н_А(х) Ì G(x) Ç A " х Î Х.

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

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

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

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

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

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

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

Прадеревом називається орієнтований граф G(X) з коренем х₀ Î X, якщо в кожну вершину х_i ¹ х₀ (х_i Î X) заходить рівно одна дуга, а в корінь х₀ не заходить жодна дуга.

Якщо в графі G(X) через а_ij позначити число дуг, що йдуть із x_i в x_j, то матриця A = | | а_ij | | (i = 1,..., n; j = 1,..., n; де n – число вершин графа) називається матрицею суміжності вершин графа. Наявність нульового елемента на головній діагоналі означає відсутність петлі у відповідній вершині.

Матрицею суміжності ребер графа називається така матриця В = | | b_ij | | (i = 1,..., m; j = 1,..., m; де m – число ребер графа), що:

b_ij =

Нехай g₁,..., g_m – дуги, х₁,..., х_n – вершини орієнтованого графа G(X). Матриця S = || s_ij || (I = 1,..., n – номер вершини графа, j = 1,..., m – номер дуги графа), така що:

s_ij =

називається матрицею інцидентності для дуг графа.

Для неорієнтованого графа матриця R = | | r_ij | | розміром n х m, де:

r_ij =

називається матрицею інцидентності для ребер графа.

 

Гіперграф — узагальнення графа, в якому ребром називається не пара вершин графа, а довільна підмножина вершин графа.

Математично, гіперграф представляє собою пару (V, E), де

· V — непорожня множина об'єктів деякої природи, які називають вершинами гіперграфа,

· E — сімейство непорожніх підмножин множини V, які називають ребрами гіперграфа.

У гіперграфах дві вершини вважаються суміжними, якщо існує ребро e_i, яка їх містить.

 

Алгоритм Дейкстри — алгоритм на графах, відкритий Дейкстрою. Знаходить найкоротший шлях від однієї вершини графа до всіх інших вершин. Класичний алгоритм Дейкстри працює тільки для графів без циклів від'ємної довжини.

Крок 1. Ініціалізація. Відстань до всіх вершин графа V = . Відстань до а = 0. Жодна вершина графа ще не опрацьована.

Крок 2. Знаходимо таку вершину (із ще не оброблених), поточна найкоротша відстань до якої мінімальна. В нашому випадку це вершина 1. Обходимо всіх її сусідів і, якщо шлях в сусідню вершину через 1 менший за поточний мінімальний шлях в цю сусідню вершину, то запам'ятовуємо цей новий, коротший шлях як поточний найкоротший шлях до сусіда.

Крок 3. Перший по порядку сусід 1-ї вершини — 2-а вершина. Шлях до неї через 1-у вершину дорівнює найкоротшій відстані до 1-ї вершини + довжина дуги між 1-ю та 2-ю вершиною, тобто 0 + 7 = 7. Це менше поточного найкоротшого шляху до 2-ї вершини, тому найкоротший шлях до 2-ї вершини дорівнює 7.

Кроки 4, 5. Аналогічну операцію проробляєм з двома іншими сусідами 1-ї вершини — 3-ю та 6-ю.

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

Крок 7. Знову знаходимо «найближчу» необроблену (невикреслену) вершину. Це вершина 2 з поточною найкоротшою відстанню до неї = 7.

І знову намагаємося зменшити відстань до всіх сусідів 2-ої вершини, намагаючись пройти в них через 2-у. Сусідами 2-ої вершини є 1, 3, 4.

Крок 8. Перший (по порядку) сусід вершини № 2 — 1-а вершина. Але вона вже оброблена. Тому з 1-ою вершиною нічого не робимо.

Інший сусід вершини 2 — вершина 4. Якщо йти в неї через 2-у, то шлях буде = найкоротша відстань до 2-ої + відстань між 2-ою і 4-ою вершинами = 7 + 15 = 22. Оскільки 22 < ∞, встановлюємо відстань до вершини № 4 рівним 22.

Крок 9. Ще один сусід вершини 2 — вершина 3. Якщо йти в неї через 2-у, то шлях буде = 7 + 10 = 17. Але 17 більше за відстань, що вже запам'ятали раніше до вершини № 3 і дорівнює 9, тому поточну відстань до 3-ої вершини не міняємо.

Крок 10. Всі сусіди вершини 2 переглянуті, заморожуємо відстань до неї і викреслюємо її з графа.

Крок 11. По вже «відпрацьованій» схемі повторюємо кроки 2 — 6 для решти вершин.

Алгоритм закінчує роботу, коли викреслені всі вершини.

 

Складність алгоритму Дейкстри залежить від способу знаходження вершини v, а також способу зберігання множини невідвіданих вершин і способу оновлення міток. Позначимо через n кількість вершин, а через m – кількість ребер в графі G.

· У простому випадку, коли для пошуку вершини з мінімальним d[v] проглядається вся множина вершин, а для зберігання величин d використовується масив, час роботи алгоритму є O(n²). Основний цикл виконується порядку n раз, в кожному з них на знаходження мінімуму витрачається близько n операцій. На цикли по сусідах кожної відвідуваної вершини витрачається кількість операцій, пропорційна кількості ребер m (оскільки кожне ребро зустрічається в цих циклах рівно двічі і вимагає константне число операцій). Таким чином, загальний час роботи алгоритму O (n² + m), але, так як m n(n - 1), він становить O (n²).

 

Алгоритм Прима – алгоритм побудови мінімального кістякового дерева зваженого зв'язного неорієнтованого графа. Це жадібний алгоритм.

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

Крок 1. Спочатку ребра сортують за зростанням ваги.

Крок 2. Додають найменше ребро в дерево.

Крок 3. Зі списку ребер із найменшою вагою вибирають таке нове ребро, щоб одна з його вершин належала дереву, а інша — ні.

Крок 4. Це ребро додають у дерево і знову переходять до кроку 3.

Крок 5. Робота закінчується, коли всі вершини будуть у дереві.

Обчислювальна складність – O (n²), де n – кількість вершин.