Algorytm Borůvki

Algorytm Borůvki – algorytm wyznaczający 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 r., potem przez Florka, Łukasiewicza, Perkala, Steinhausa i Zubrzyckiego w 1951 r. i ostatecznie w latach 60. przez Sollina, od którego nazwiska często jest on nazywany „algorytmem Sollina”.

Algorytm

Przykład działania algorytmu Borůvki

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_{1}$ i $v_{2}.$ 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_{1}$ więc $C(e_{i})<C(e_{j}).$ Ale skoro e_j została dołączona jako najlżejsza krawędź incydentna do $v_{2}$ 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},\dots ,v_{l}$ będą kolejnymi superwierzchołkami należącymi do $C$ a $e_{1},e_{2},\dots ,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})<\dots <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}$ 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})\land e_{i}\not \in E(T)$

Fakt: Krawędź $e_{i}$ została 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

Można 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 Kruskala
• algorytm Prima
• minimalne drzewo rozpinające

Linki zewnętrzne

• K.K. Loryś K.K., Algorytmy zachłanne. Notatka nr 2 do wykładu z algorytmów i struktur danych [plik PostScript], Instytut Informatyki UWr, 22 lutego 2006 [dostęp 2022-05-30] .