Algorytm Borůvki

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacji, wyszukiwania
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


Wybrane klasy grafów
graf pełny
graf spójny
drzewo
graf dwudzielny
graf regularny
graf eulerowski
graf hamiltonowski
graf planarny


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[edytuj | edytuj kod]

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[edytuj | edytuj kod]

Lemat 1[edytuj | edytuj kod]

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 v1 i v2. Oznacza to, że do zbioru E' zostały dołączone krawędzie ei i ej. Ponieważ ei została dołączona jako najlżejsza krawędź incydentna do v1 więc C(e_i) < C(e_j). Ale skoro ej została dołączona jako najlżejsza krawędź incydentna do v2 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[edytuj | edytuj kod]

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[edytuj | edytuj kod]

Ł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ż[edytuj | edytuj kod]

Bibliografia[edytuj | edytuj kod]

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