Algorytm Borůvki

Ten artykuł należy dopracować: od 2022-05 → zweryfikować treść i dodać przypisy, od 2022-05 → usunąć/zweryfikować prawdopodobną twórczość własną. Dokładniejsze informacje o tym, co należy poprawić, być może znajdują się w dyskusji tego artykułu. Po wyeliminowaniu niedoskonałości należy usunąć szablon {{Dopracować}} z tego artykułu.

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^[1][2][3]. Algorytm ten został potem ponownie wymyślony przez Choqueta w 1938 r.^[4], potem przez Florka, Łukasiewicza, Perkala, Steinhausa i Zubrzyckiego w 1951 r.^[5] i ostatecznie w latach 60. przez Sollina^[6], od którego nazwiska często jest on nazywany „algorytmem Sollina”.

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 ${\displaystyle v}$ w grafie ${\displaystyle G}$ przejrzyj zbiór incydentnych z nim krawędzi. Dołóż najlżejszą z nich do rozwiązania (zbioru ${\displaystyle E'}$).
2. Po tym etapie graf tymczasowego rozwiązania powinien zawierać nie więcej niż ${\displaystyle {\frac {|V|}{2}}}$ spójnych składowych. Utwórz graf ${\displaystyle 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 ${\displaystyle G}$ podstawiając graf ${\displaystyle G'.}$

Po zakończeniu algorytmu ${\displaystyle G'}$ jest minimalnym drzewem rozpinającym.

W każdym momencie działania algorytmu, oraz po jego zakończeniu w ${\displaystyle 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 ${\displaystyle S.}$ Rozważmy następujące sytuacje:

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

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 ${\displaystyle V_{i},}$ który nie jest minimalnym drzewem rozpinającym poddrzewa złożonego z wierzchołków należących do ${\displaystyle V_{i}.}$ Weźmy więc takie minimalne drzewo rozpinające ${\displaystyle T.}$ Istnieje krawędź ${\displaystyle e_{i}}$ taka, że ${\displaystyle e_{i}\in E(V_{i})\land e_{i}\not \in E(T).}$ Dodajmy ${\displaystyle e_{i}.}$ W ${\displaystyle T}$ powstał cykl. Ponieważ ${\displaystyle e_{i}}$ jest incydenta do pewnego wierzchołka z tego cyklu, istnieje więc inna krawędź ${\displaystyle e'_{i}}$ incydentna do tego samego wierzchołka. Jednak z tego, że ${\displaystyle e_{i}\in E(V_{i})}$ wynika, że ${\displaystyle C(e_{i})<C(e'_{i}).}$ Jeśli usuniemy krawędź ${\displaystyle e'_{i}}$ z ${\displaystyle T}$ otrzymamy mniejsze drzewo rozpinające, co jest sprzeczne z założeniem o minimalności ${\displaystyle 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 ${\displaystyle k}$-ty będzie pierwszym takim etapem, w którym coś się popsuło. Niech ${\displaystyle E'_{1}}$ będzie zbiorem krawędzi przed wywołaniem etapu ${\displaystyle k,}$ a ${\displaystyle E'_{2}}$ będzie zbiorem krawędzi po jego wywołaniu. Niech ${\displaystyle T}$ będzie minimalnym drzewem rozpinającym takim, że ${\displaystyle V(T)=V(V_{i}),}$ ale że ${\displaystyle E(T)\not =E(V_{i}).}$ Istnieje więc krawędź ${\displaystyle e_{i}\in E(V_{i})\land e_{i}\not \in E(T)}$

Fakt: Krawędź ${\displaystyle e_{i}}$ została dodana podczas ${\displaystyle k}$-tego wywołania. (Nie może należeć do ${\displaystyle 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 ${\displaystyle k}$-te jest najmniejszym wywołaniem, które zwróciło nieoptymalne drzewa)

Dodajmy krawędź ${\displaystyle e_{i}}$ do ${\displaystyle E(T).}$ W ${\displaystyle T}$ powstał cykl. Ponieważ ${\displaystyle 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 ${\displaystyle e_{i},}$ zatem zastąpienie jej krawędzią ${\displaystyle e_{i}}$ da nam mniejsze drzewo rozpinające co jest sprzeczne z założeniem o optymalności ${\displaystyle T.}$

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 ${\displaystyle \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 ${\displaystyle O(E\log V).}$ Można zmodyfikować go tak, aby osiągnąć złożoność ${\displaystyle 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.

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

• 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] .