Algorytm Borůvki

Niniejszy artykuł jest częścią cyklu teoria grafów.

Najważniejsze pojęcia graf drzewo podgraf cykl klika stopień wierzchołka stopień grafu dopełnienie grafu obwód grafu pokrycie wierzchołkowe liczba chromatyczna indeks chromatyczny izomorfizm grafów homeomorfizm grafów więcej... Wybrane klasy grafów graf pełny graf spójny drzewo graf dwudzielny graf regularny graf eulerowski graf hamiltonowski graf planarny więcej... Algorytmy grafowe A* Bellmana-Forda Dijkstry Fleury'ego Floyda-Warshalla Johnsona Kruskala Prima przeszukiwanie grafu – wszerz – w głąb najbliższego sąsiada Zagadnienia przedstawiane jako problemy grafowe problem komiwojażera problem chińskiego listonosza problem marszrutyzacji problem kojarzenia małżeństw Inne zagadnienia kod Graya diagram Hassego kod Prüfera

Algorytm Borůvki wyznacza minimalne drzewo rozpinające dla grafu nieskierowanego ważonego, o ile jest on spójny. Innymi słowy, znajduje drzewo zawierające wszystkie wierzchołki grafu, którego waga jest najmniejsza możliwa. Jest to przykład algorytmu zachłannego.

Pierwszy raz opublikowany został w 1926 roku przez Otakara Borůvkę jako metoda efektywnej konstrukcji sieci energetycznych. Algorytm ten został potem ponownie wymyślony przez Choqueta w 1938, potem przez Florka, Łukasiewicza, Perkala, Steinhausa i Zubrzyckiego w 1951 i ostatecznie przez Sollina w latach 60. Ponieważ Sollin był jedynym zachodnim informatykiem wśród wymienionych tu osób, często algorytm jest nazywany jego nazwiskiem.

Algorytm

Algorytm działa poprawnie przy założeniu, że wszystkie krawędzie w grafie mają różne wagi. Jeśli tak nie jest, można np. przypisać każdej krawędzi unikatowy indeks i jeśli dojdzie do porównania dwóch krawędzi o takich samych wagach, wybrać tę, która otrzymała niższy numer.

1. Dla każdego wierzchołka v w grafie G przejrzyj zbiór incydentnych z nim krawędzi. Dołóż najlżejszą z nich do rozwiązania (zbioru E').
2. Po tym etapie graf tymczasowego rozwiązania powinien zawierać nie więcej niż $\frac{|V|}{2}$ spójnych składowych. Utwórz graf G' w którym wierzchołki stanowiące spójne składowe zostaną ze sobą „sklejone” (nowe wierzchołki będziemy nazywać roboczo superwierzchołkami).
3. Dopóki nie otrzymamy jednej spójnej składowej, wywołujemy kroki 1-2 za graf G podstawiając graf G'

Po zakończeniu algorytmu G' jest minimalnym drzewem rozpinającym.

Dowód poprawności

Lemat 1

W każdym momencie działania algorytmu, oraz po jego zakończeniu w E' nie będzie cyklu.

Dowód

Załóżmy nie wprost, że podczas działania algorytmu w którymś etapie pojawiła się spójna składowa, w której jest cykl. Oznaczmy ją jako S. Rozważmy następujące sytuacje:

• S powstała przez połączenie dwóch superwierzchołków v₁ i v₂. Oznacza to, że do zbioru E' zostały dołączone krawędzie e_i i e_j. Ponieważ e_i została dołączona jako najlżejsza krawędź incydentna do v₁ więc $C(e_i) < C(e_j)$. Ale skoro e_j została dołączona jako najlżejsza krawędź incydentna do v₂ to musi zachodzić $C(e_j) < C(e_i)$ (Pamiętajmy, że w grafie nie ma krawędzi o takiej samej wadze) – sprzeczność.
• S powstała przez połączenie się trzech lub więcej superwierzchołków. Podzielmy powstały cykl C na następujące części: niech $v_1,v_2,v_3 ... v_l$ będą kolejnymi superwierzchołkami należącymi do C a $e_1, e_2, ..., e_l$ będą kolejnymi krawędziami należącymi do C, które zostały dodane w zakończonym właśnie etapie algorytmu. W C krawędzie $e_i$ oraz superwierzchołki $v_i$ występują na przemian. Z zasady działania algorytmu możemy stwierdzić, że aby powstał taki cykl, musi zachodzić $C(e_1)<C(e_2)<...<C(e_{l-1})<C(e_l)<C(e_1)$ – Sprzeczność.

Lemat 2

W każdym etapie działania algorytmu otrzymujemy dla każdego superwierzchołka minimalne drzewo rozpinające

Dowód

Gdy zostanie zakończony etap 1:

Załóżmy, że istnieje taki superwierzchołek $V_i$, który nie jest minimalnym drzewem rozpinającym poddrzewa złożonego z wierzchołków należących do $V_i$. Weźmy więc takie minimalne drzewo rozpinające T. Istnieje krawędź $e_i$ taka, że $e_i \in E(V_i) \and e_i \not\in E(T)$. Dodajmy $e_i$. W T powstał cykl. Ponieważ $e_i$ jest incydenta do pewnego wierzchołka z tego cyklu, istnieje więc inna krawędź $e'_i$ incydentna do tego samego wierzchołka. Jednak z tego, że $e_i \in E(V_i)$ wynika, że $C(e_i) < C(e'_i)$. Jeśli usuniemy krawędź $e'_i$ z T otrzymamy mniejsze drzewo rozpinające, co jest sprzeczne z założeniem o minimalności T.

Gdy zostanie zakończony etap 2:

Z poprawności etapu 1 wiemy, że istnieje takie wywołanie etapu 2, w którym każdy z superwierzchołków jest minimalnym drzewem rozpinającym. Jest to choćby pierwsze wywołanie. Załóżmy zatem, że dla pewnego wywołania tego etapu otrzymano superwierzchołki będące minimalnymi drzewami rozpinającymi, jednak scaliło przynajmniej dwa z nich w taki sposób, że dało się otrzymać mniejsze drzewo rozpinające. Niech etap k-ty będzie pierwszym takim etapem, w którym coś się popsuło. Niech $E'_1$ będzie zbiorem krawędzi przed wywołaniem etapu k, a $E'_2$ będzie zbiorem krawędzi po jego wywołaniu. Niech T będzie minimalnym drzewem rozpinającym takim, że $V(T) = V(V_i)$, ale że $E(T) \not= E(V_i)$. Istnieje więc krawędź $e_i \in E(V_i) \and e_i \not\in E(T)$

Fakt: Krawędź $e_i$ dodana podczas k-tego wywołania. (Nie może należeć do $E'_1$, gdyż inaczej superwierzchołek do którego by należała nie byłby minimalnym drzewem rozpinającym, co jest sprzeczne z dowodem dla pierwszego etapu i założeniem, że wywołanie k-te jest najmniejszym wywołaniem, które zwróciło nieoptymalne drzewa)

Dodajmy krawędź $e_i$ do E(T). W T powstał cykl. Ponieważ $e_i$ jest najmniejszą krawędzią incydentną do pewnego superwierzchołka z tego cyklu, istnieje więc inna krawędź incydenta do tego samego superwierzchołka. Jednak jej waga jest większa niż waga krawędzi $e_i$, zatem zastąpienie jej krawędzią $e_i$ da nam mniejsze drzewo rozpinające co jest sprzeczne z założeniem o optymalności T.

Złożoność obliczeniowa

Łatwo udowodnić, że każdym kolejnym wywołaniu liczba wierzchołków zmaleje co najmniej dwukrotnie – zatem wywołań tych będzie co najwyżej $\log V$. Złożoność obliczeniowa całości zależy więc od sposobu implementacji kroków 1,2 algorytmu. Zastosowanie w implementacji struktury zbiorów rozłącznych pozwala osiągnąć złożoność na poziomie $O(E\log V)$. Można zmodyfikować go tak, aby osiągnąć złożoność $O(E\log V - V)$ – algorytm działa wtedy znacznie szybciej dla grafów rzadkich; dla grafów gęstych modyfikacja nie daje dużych zysków czasowych.

Zobacz też

• algorytm Prima
• algorytm Kruskala
• minimalne drzewo rozpinające

Bibliografia

1. Notatka do wykładu z algorytmów i struktur danych prof K. Lorysia
2. [1]