Algorytm Borůvki

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 unikalny 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 {n}{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ź incydenta do v₁ więc $C(e_{i})<C(e_{j})$. Ale skoro e_j została dołączona jako najlżejsza krawędź incydenta 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})\land 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}$ incydenta 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})\land 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ł cyl. 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(n)$. Złożoność obliczeniowa całości zależy więc od sposobu implementacji kroków 1,2 algorytmu. Zastosowanie w implementacji struktur Union-find pozwala osiągnąć złożoność na poziomie $O(log(n)*m)$. Można zmodyfikować go tak, aby osiągnąć złożoność $O(log(n)*m-n)$ - algorytm działa wtedy znacznie szybciej dla grafów rzadkich; dla grafów gęstych modyfikacja nie daje dużych zysków czasowych.

Szablon:Stub

Zobacz też

• Algorytm Prima
• Algorytm Kruskala
• Minimalne drzewo rozpinające