- •Тема 3. Алгоритми розв'язання проблем, сформульованих у термінах графів
- •Лекція 3.2. Алгоритми визначення двохзв’язних компонент і їх оцінка
- •Б езперечно, що
- •Лекція 3.1. Розробка й оцінка алгоритмів пошуку найкоротших шляхів у графах
- •Допустимо тепер, що V(( ( V(. Оскільки V одержує постійну мітку l(V) з V((, а не з V(, те
- •Таким чином, і у випадку б) вірна нерівність w(p() ( w(p*), тобто p( – найкоротший (s, V)-пута.
- •Будемо вважати, что граф g заданий матрицею ваг.
- •Кожне виконання п. 5 збільшує на одиницю число вершин
- •Л егко бачити, что трудомісткість кожного з пп. 1 – 9 не перевершує т ому час роботи алгоритму в цілому оцінюється зверху величиною
Будемо вважати, что граф g заданий матрицею ваг.
Алгоритм А9 побудови зробленого паросполучення мінімальної ваги в двочастковому зваженому графі.
Побудувати граф T = (X, Y, U), U = {xy: w(x, y) = 0}.\
Знайти в графі Т максимальне паросполучення М. Нехай XM і YM – безлічі вершин, не насичених паросполученням М и вхідних, відповідно, у частки X і Y.
Якщо XM = YM = (, то кінець [М – оптимальний розв’язок задачі]. Інакше побудувати граф(T = (T(T, M).
Застосувати до графа(T пошук у ширину (алгоритм А6) з безлічі XM. Якщо знайдений (x, y)-шлях Р, x(XM, y( YM, то перейти до п. 5. Інакше до п. 7.
Перетворити графT,
замінивши в ньому кожну дугу шляху Р на зворотню. Нехай
[ шляхом зміни М уздовж ланцюга, що збільшує, знайдене нове паросполучення в T T = (X, Y, U), XM ( X, YM ( Y - підмножини вершин Т Т, не насичених новим паросполученням].
Якщо XM = YM = (, то кінець [безліч усіх таких ребер xy, x ( X, y ( Y і (y, x) – дуга графа(Т, складає зроблене паросполучення мінімальної ваги у вихідному графі G]. Інакше перейти до п. 4.
Нехай X( ( X і Y( ( Y – підмножина вершин графа(Т, що одержала позначки в результаті пошуку в ширину (у п. 4). Серед ребер графа G, що мають вид xy, x ( X(, y ( Y – Y(, знайти ребро мінімальної ваги. Нехай ??– вага цього ребра.
Модифікувати ваги дуг графа G, застосувавши до нього операцію (X(,Y(,().
Модифікувати граф(T додавши до нього всі такі дуги (x, y), що x ( X(, y ( Y – Y(, w(x, y) = 0, і видаливши всі такі дуги (x, y), що x ( X – X(, y ( Y(. Перейти до п. 4.
Займемося тепер обґрунтуванням алгоритму А9. Корективность пп. 1 – 3 не викликає сумнівів. Легко бачити також, что кожний з цих пунктів можна виконати за час
І нші пункти алгоритму розглянемо більш докладно.
Кожне виконання п. 5 збільшує на одиницю число вершин
О тже, цей пункт виконується не більш n раз. Наша найближча мета – показати, що після виконання пп. 4, 6 – 9 не більш ніж n раз підряд обов'язково відбудеться перехід до п. 5., тобто очевидне виконання п. 4 закінчиться відшуканням шляху Р. Розглянемо докладніше пп. 7 – 9. Після закінчення п. 4 і переходу до п. 7 кожна дуга графа(T інцидентна принаймні одній вершині безлічі (X – X() ( Y(. Це відразу випливає з твердження 77.4. Таким чином, кожне ребро нульової ваги в графі G інцидентно однієї з вершин цієї безлічі. З іншого боку, оскільки XM ( (, Y M ( (, те X( ( X, Y( ( Y. Тому з правила вибору величини ??в п. 7 випливає, що ??> 0. Після модифікації графу G у п. 8 ваги його ребер залишаться невід’ємними (це випливає з правила вибору ?). У результаті наступної модифікації графу(T у (п. 9) володіє двома важливими властивостями. По-перше, вилучені дуги цього графа спрямовані від непомічених вершин частки Х. Тому усі вершини, досяжні з ХМ у “старому” графі(T досяжні з цієї безлічі й у “новому” графі(T. По-друге, додані дуги спрямовані від позначених вершин частки Х к непоміченим вершинам частки Y. Таким чином, застосування пошуку в ширину до модифікованого графа(T (п. 4) приведе до того, що додатково буде позначена принаймні одна вершина частки Y. Оскільки | Y | = n, то після виконання пп. 4, 7 – 9 не більш ніж у n раз підряд позначеної зробить деяка вершина безлічі YM , тобто буде знайдений шлях Р, і потім піде виконання п. 5. Як уже було показано, п. 5 (а виходить, і п. 6) виконується не більш n раз. Тому кожний із пп. 4, 7 – 9 виконується не більш
р аз.