Algorytm Borůvki

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacja, szukaj
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]

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ż 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]

Lemat 1[edytuj]

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 . Ale skoro ej została dołączona jako najlżejsza krawędź incydentna do v2 to musi zachodzić (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 będą kolejnymi superwierzchołkami należącymi do C a 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 oraz superwierzchołki występują na przemian. Z zasady działania algorytmu możemy stwierdzić, że aby powstał taki cykl, musi zachodzić – Sprzeczność.

Lemat 2[edytuj]

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 , który nie jest minimalnym drzewem rozpinającym poddrzewa złożonego z wierzchołków należących do . Weźmy więc takie minimalne drzewo rozpinające T. Istnieje krawędź taka, że . Dodajmy . W T powstał cykl. Ponieważ jest incydenta do pewnego wierzchołka z tego cyklu, istnieje więc inna krawędź incydentna do tego samego wierzchołka. Jednak z tego, że wynika, że . Jeśli usuniemy krawędź 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 będzie zbiorem krawędzi przed wywołaniem etapu k, a będzie zbiorem krawędzi po jego wywołaniu. Niech T będzie minimalnym drzewem rozpinającym takim, że , ale że . Istnieje więc krawędź

Fakt: Krawędź została dodana podczas k-tego wywołania. (Nie może należeć do , 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ź do E(T). W T powstał cykl. Ponieważ 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 , zatem zastąpienie jej krawędzią da nam mniejsze drzewo rozpinające co jest sprzeczne z założeniem o optymalności T.

Złożoność obliczeniowa[edytuj]

Ł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 . 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 . Można zmodyfikować go tak, aby osiągnąć złożoność – 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]

Bibliografia[edytuj]

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