2.4 Алгоритми на графах
Графи є зручними моделями при аналізі роботи і проектуванні комп’ютерних мереж.
Граф є кінцева множина V, яка називається множиною вершин, і множина Е двоелементних підмножин множини V. Множина Е носить назву множини ребер. Елемент множини Е називають ребром. Граф позначають G(V,E).
Зазвичай кінцевий граф, зображають у вигляді діаграми, на якій вершини це точки, а лінії – ребра.
Якщо {a,b} – ребра, тоді вершини a і b називають їх кінцями. Ребро (a,b) називають інцедентним вершинам a і b. І, навпаки, вершини a і b інцедентні ребру (a,b). Дві вершини називають суміжними, якщо вони є кінцями ребра (інцедентні ребру). Два ребра називають суміжними, якщо вони інцедентні одній вершині (рис. 2.5)
Рисунок 2.5 – Суміжні ребра (a,b) і (b,с) |
Приклад. Граф з множиною вершин V={a,b,c,d,e} і множиною ребер E={(a,b), (a,e), (b,e), (b,c), (b,d), (c,d)} показаний на рис. 2.6 |
Визначені нами графи носять назву – простих. Обмеження на існування тільки одного ребра між двома вершинами дає можливість подати будь – яке ребро не як елемент множини Е. |
|
Рисунок 2.6 – Граф з множиною вершин V і множиною ребер Е. |
Наше визначення виключає також ребра, які називають петлями (рис. 2.7). Ребро яке з’єднує вершину саму з собою називається петлею. Граф, в якому є петлі, називають графом з петлями.
Рисунок 2.7 – Граф з петлею |
Якщо в графі є більше одного ребра між двома вершинами, то він носить назву мультиграфа (рис. 2.8)
Рисунок 2.8 – Мультиграф. |
Якщо граф має петлі і вершини, які з’єднані більше ніж одним ребром, то такий граф називають псевдографом
Степеню вершини , позначають deg(v), називають кількість ребер, які інцидентні даній вершині V. Вершина степені 0 називається ізольованою.
Граф, який складається із множини вершин V і множини Е упорядкованих пар елементів із V називається орієнтованим графом або орграфом. Ребра такого графа називають дугами. Якщо , то а – початкова, а b – кінцева вершини. Відмітимо, що поняття орграфа допускає наявність петель, чого не було у випадку простих графів. Це пояснюються тим, що орграф допускає відношення між елементами, а простий граф визначений як множина вершин і ребер, а в множині два однакових елементи вважаються одним елементом.
Якщо а – початкова, а b – кінцева вершини орграфа G(V,E), то вершини a і b інцидентні ребру (a,b); вершина а суміжна до вершини b, і, навпаки, вершина b також суміжна до вершини а.
Степеню виходу вершини називається кількість ребер, для яких є початковою вершиною, позначається outdeg( ). Степеню входу вершини називається кількість ребер, для яких є кінцевою вершиною і позначається . Якщо =0, то називається джерелом. Якщо outdeg( )=0, то вершина називається стоком (рис. 2.9).
Існує два способи подання граф як набір списків суміжних вершин або як матрицю суміжності.
Подання графа у вигляді списку суміжних вершин використовує масив із списків – по одному на кожну вершину ( - кількість вершин графа). Для кожної вершини список суміжних вершин вміщує у довільному порядку всі суміжні з нею вершини, для яких . На рис. 2.10,б показано подання неорієнтованого графа (рис.2.10,а) за допомогою списку суміжних вершин, а на рис 2.10,в той же граф поданий за допомогою матриці суміжності.
Рисунок 2.9 - Орграф, в якому є джерело і стік
а б в
Рисунок 2.10 – Два подання неорієнтованого графа
Аналогічним чином можна подати і орграф: у вигляді списку суміжних вершин (рис. 2.11,б) та у вигляді матриці суміжності (рис. 2.11,в).
Для орієнтованого графа сума всіх елементів матриці суміжності дорівнює числу його дуг (орієнтованих ребер), а для неорієнтованого графа – подвоєній сумі елементів матриці суміжності, так як ребро асоційовано в таблиці суміжності з двома елементами: як з вершиною , так і з вершиною . В обох випадках кількість пам’яті є . Списки суміжних вершин зручні для зберігання графів з вагами, в якому кожному ребру назначена певна вага (вагова функція). Недолік такого способу наступному: якщо необхідно дізнатись чи є у графа ребро із у , то необхідно проглянути увесь список у пошуку . Цього можна уникнути, подавши граф у вигляді матриці суміжності – але тоді буде потрібно більше пам’яті.
а б в
Рисунок 2.11 – Два подання орієнтованого графа
При використанні матриці суміжності будемо нумерувати вершини графа числами 1, 2, …, і розглядатимемо матрицю розміром , елементи якої
На рис. 2.10,б і 2.11,б наведені матриці суміжності для неорієнтованого і орієнтованого графів відповідною. Матриця суміжності вимагає пам’яті незалежно від кількості ребер.
Оскільки матриця суміжності неорієнтованого графа симетрично, то вона співпадає зі своєю транспонованою матрицею, тобто . Завдяки симетрії матриці у пам’яті машини можна зберігати лише числа на головній діагоналі і числа, які розміщені вище головної діагоналі. Зберігання ваг ребер графа у пам’яті машини здійснюється у матриці на пересіченні лінійки і стовпця.