Алгоритмы теории графов
К сожалению только на украинском языке
АЛГОРИТМИ ТЕОРІЇ ГРАФІВ
Основні визначення теорії графів
Орієнтований граф, як пишуть у [1] – це «пара (V, E), де V – кінцева множина, а E – бінарне відношення на V, тобто підмножина множини V*V… …множину V називають множиною вершин графа, а множину E – множиною ребер».
У неорієнтованому графі множина V складається з неупорядкованих пар вершин. Парою називається множина {u,v}, де u і v належать V.
Якщо в графі є ребро (u,v), то говорять, що вершина u суміжна з вершиною v. Для неорієнтованих графів відношення суміжності є симетричним.
Шлях довжини k з вершини u у вершину v визначається як послідовність вершин v0, v1, v2, … vk, у який v0 = u, vk = v, а (vi-1, vi) – ребро графа.
Циклом в орієнтованому графі називається шлях, у якому початкова вершина збігається з кінцевою і який містить хоча б одне ребро. Граф, у якому немає циклів, називається ациклічним.
Представлення графів
Є два стандартних способи представлення графів: як список суміжних вершин чи як матрицю суміжності. Обидва способи мають свої плюси і недоліки.
Список суміжних вершин дуже зручний при представленні розріджених графів. Він дає вигідне зменшення займаного обсягу пам'яті. Але при цьому цей спосіб не дає можливості швидко перевірити наявність ребра між двома довільними вершинами. Це представлення графу використовує масив списків по одному списку для кожної вершини. Список зберігає усі вершини, суміжні з даною вершиною в довільному порядку.
Матриця суміжності займає більший обсяг пам'яті, але зручна для представлення щільних графів. Тут кожен елемент Mij матриці позначає наявність ребра межу вершиною i та вершиною j. Якщо граф – зважений, то Mij може позначати вагу ребра (i,j).
Алгоритм пошуку в ширину
Алгоритм пошуку в ширину (Breadth-first search) – один з базисних алгоритмів, що є основою багатьох інших. Наприклад, алгоритм Дейкстри пошуку найкоротших шляхів з однієї вершини й алгоритм Прима пошуку мінімального покриваючого дерева можуть розглядатися як узагальнення пошуку в ширину..
Нехай заданий граф G і фіксована початкова вершина s. Алгоритм пошуку в ширину перелічує всі досяжні з s (якщо йти по ребрах) вершини в порядку збільшення відстані від s. У процесі пошуку з графу виділяється частина, що називається «деревом пошуку в ширину» з коренем s. Вона містить усі досяжні з s вершини (і тільки їх). Для кожної з них шлях з кореня в дереві пошуку буде одним з найкоротших шляхів до s. Алгоритм можна застосувати і до орієнтованих, і до неорієнтованих графів.
Назва пояснюється тим, що в процесі пошуку ми йдемо в широчінь, а не в глиб (з початку переглядаємо сусідні вершини, потім сусідів сусідів, і т.д.).
Для наочності будемо вважати, що в процесі роботи алгоритму вершини графа можуть бути білими, сірими і чорними. Спочатку вони всі білі, а в ході роботи алгоритму біла вершина може стати сірою, сіра - чорною, але не навпаки. Зустрівши нову вершину, алгоритм пошуку фарбує її, так що сірі і чорні вершини - уже виявлені вершини. Різниця між сірими і чорними вершинами використовується алгоритмом для керування порядком обходу: сірі вершини утворять "лінію фронту", а чорні - "тил". Таким чином, тільки сірі вершини можуть мати суміжні невиявлені вершини.
Спочатку дерево пошуку складається тільки з початкової вершини s. Як тільки алгоритм виявляє нову вершину v, суміжну з раніше знайденою вершиною u, вершина v разом з ребром (u, v) додається до дерева пошуку, стаючи дитиною вершини u, а u стає батьком v. Кожна вершина виявляється тільки один раз, так що двох батьків у вершини бути не може.
Оцінюючи складність цього алгоритму, ми зауважуємо, що вершини тільки сутеніють, отже, кожна вершина обробляється тільки один раз. При цьому для обходу суміжних вершин для даної вершини використовується часу O(E). Отже, обчислювальна складність алгоритму пошуку в ширину – O(V+E), де V – кількість вершин у графі, а E – кількість ребер.
Алгоритм пошуку в глибину
Пошук у глибину – ще один спосіб обходу графу. Він застосовується в таких алгоритмах, як алгоритм топологічного сортування, алгоритм пошуку сильно зв'язаних компонентів.
Стратегія пошуку в глибину така: йти вглиб, поки це можливо (є непройдені вихідні ребра), повертатися і шукати інший шлях, коли таких ребер немає. Якщо після цього залишаються недоторкані вершини - можна вибрати одну з них і повторювати процес доти, поки залишаються невиявлені вершини.
Знайшовши уперше вершину v, суміжну з u, ми відзначаємо цю подію, записуючи в поле ?[v] значення u. Утворюється дерево чи кілька дерев.
Як і пошук у ширину, алгоритм пошуку в глибину використовує кольори вершин. Спочатку усі вершини - білі. При виявленні нової вершини, вона фарбується в сірий колір. Коли вершина цілком оброблена, вона фарбується в чорний колір.
Крім цього пошук у глибину ставить на вершинах мітки часу. Кожна вершина має дві мітки: d[v] показує, коли вершина була виявлена, f[v] - коли оброблена. Ці мітки використовуються в багатьох алгоритмах на графах.
Під час виконання цього алгоритму, обробка кожної вершини відбувається рівно один раз. Отже, складність роботи даного алгоритму становить O(V+E), де V – кількість вершин у графі, а E – кількість ребер.
Алгоритм Дейкстри пошуку найкоротших шляхів
Уявимо собі карту автомобільних шляхів України. Як знайти найкоротший шлях із Дніпропетровська в Київ? Можна, звичайно, перебрати всі можливі варіанти і вибрати мінімальний з них. Але тоді ми одержуємо мільйони свідомо невірних операцій (наприклад, навіщо нам їхати з Дніпропетровська в Київ через Донецьк, що знаходиться зовсім в іншому боці). Далі буде розглянутий спосіб ефективного рішення цієї задачі.
Тут буде розглядатися тільки пошук найкоротших шляхів з однієї вершини: даний зважений граф G і початкова вершина s. Потрібно знайти всі найкоротші шляхи з s в усі вершини графу. Алгоритм Дейкстри здатний знайти найкоротший шлях тільки для графів, у яких усі ребра недодатньої ваги.
Багато алгоритмів пошуку найкоротших шляхів використовують особливу техніку – техніку релаксації. І алгоритм Дейскстри – не виключення. Техніка релаксації полягає в наступному: для кожної вершини v ми зберігаємо деяке число d[v], що є верхньою оцінкою ваги найкоротшого шляху з s у v. Початкове значення оцінки найкоротшого шляху і масиву ? (масиву предків) задається наступною процедурою:
Initialize-Single-Source(G, s)
1 for (для) усіх вершин v
2 do d[v] = ?
3 ?[v] = NIL
4 d[s] = 0
Релаксація ребра (u,v) полягає в наступному: значення d[v] зменшується до d[u]+w(u,v) (якщо друге значення менше попереднього). При цьому d[v] залишається верхньою оцінкою.
Relax(u, v, w)
1 if d[v] > d[u] + w(u,w)
2 then d[v] = d[u] + w(u,w)
3 ?[v] = u
По своїй суттевості, алгоритм Дейкстри є жадним алгоритмом.
У процесі роботи алгоритму Дейкстри підтримується множина S, що складається з вершин v, для яких знайдений найкоротший шлях. Алгоритм вибирає вершину u з найменшим d[u], додає її до множини S і здійснює релаксацію всіх ребер, що виходять з u, після чого цикл повторюється.
Складність роботи алгоритму Дейкстри становить O(V2)
Пошук максимального паросполучення
Нехай G(V, E) - неорієнтований граф. Паросполученням назвемо множину ребер M, що не мають спільних кінців (кожна вершина v з V є кінцем максимум одного ребра з M). Будемо говорити, що вершина v з V входить у паросполучення M, якщо в M є ребро з кінцем v. У противному випадку v вільна. Максимальне паросполучення - це паросполучення M, що містить максимально можливе число ребер.
Для рішення задачі про найбільше паросполучення використовується метод ланцюгів, що чергуються. Нехай M - паросполучення в двочастковому графі G. Ланцюг, у який по черзі входять ребра з M і з "не-M", назвемо ланцюгом, що чергується. Вершини, инцидентні ребрам з M, назвемо насиченими. Чергуючийся відносно M ланцюг з ненасиченими вершинами називається ланцюгом, що збільшує, відносно M.
Паросполучення M є максимальним тоді і тільки тоді, коли немає збільшуючих відносно M ланцюгів
Для задач про максимальне паросполучення є безліч метафор. Ось одна з них: є множина чоловіків і множина наречених. Ребро (u,v) означає, що чоловік u і наречена v згодні оженитися. Максимальне паросполучення доставляє ЗАГСу більше всього роботи.
Алгоритм пошуку максимального паросполучення такий:
1. Ініціалізація
2. Побудова жадібного паросполучення.
3. У циклі по i з I' застосувати алгоритм знаходження всіх досяжних вершин з
i. Якщо серед них виявиться вершина з J', то збільшити ланцюг.
4. Якщо множини I' і J' непорожні і на кроці 3 удалося збільшити ланцюг, то перейти до 3
5. Видати рішення
Тут I' і J' - множини ненасичених вершин із двох часток графа. "Збільшити ланцюг" - говорячи простою мовою - означає розгорнути ребра графа.
Взято с Vingrad.ru https://forum.vingrad.ru