Algorytm Borůvki
![Sprzątanie Wikipedii](http://upload.wikimedia.org/wikipedia/commons/thumb/2/2c/Broom_icon.svg/35px-Broom_icon.svg.png)
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
![](http://upload.wikimedia.org/wikipedia/commons/thumb/2/2e/Boruvka%27s_algorithm_%28Sollin%27s_algorithm%29_Anim.gif/500px-Boruvka%27s_algorithm_%28Sollin%27s_algorithm%29_Anim.gif)
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.
- Dla każdego wierzchołka w grafie przejrzyj zbiór incydentnych z nim krawędzi. Dołóż najlżejszą z nich do rozwiązania (zbioru ).
- Po tym etapie graf tymczasowego rozwiązania powinien zawierać nie więcej niż spójnych składowych. Utwórz graf w którym wierzchołki stanowiące spójne składowe zostaną ze sobą „sklejone” (nowe wierzchołki będziemy nazywać roboczo superwierzchołkami).
- Dopóki nie otrzymamy jednej spójnej składowej, wywołujemy kroki 1–2, za graf podstawiając graf
Po zakończeniu algorytmu jest minimalnym drzewem rozpinającym.
Dowód poprawności
Lemat 1
W każdym momencie działania algorytmu, oraz po jego zakończeniu w 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 Rozważmy następujące sytuacje:
- powstała przez połączenie dwóch superwierzchołków i Oznacza to, że do zbioru zostały dołączone krawędzie i Ponieważ ei została dołączona jako najlżejsza krawędź incydentna do więc Ale skoro ej została dołączona jako najlżejsza krawędź incydentna do to musi zachodzić (Pamiętajmy, że w grafie nie ma krawędzi o takiej samej wadze) – sprzeczność.
- powstała przez połączenie się trzech lub więcej superwierzchołków. Podzielmy powstały cykl na następujące części: niech będą kolejnymi superwierzchołkami należącymi do a będą kolejnymi krawędziami należącymi do które zostały dodane w zakończonym właśnie etapie algorytmu. W 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
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 Istnieje krawędź taka, że Dodajmy W 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 otrzymamy mniejsze drzewo rozpinające, co jest sprzeczne z założeniem o minimalności
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 -ty będzie pierwszym takim etapem, w którym coś się popsuło. Niech będzie zbiorem krawędzi przed wywołaniem etapu a będzie zbiorem krawędzi po jego wywołaniu. Niech będzie minimalnym drzewem rozpinającym takim, że ale że Istnieje więc krawędź
Fakt: Krawędź została dodana podczas -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 -te jest najmniejszym wywołaniem, które zwróciło nieoptymalne drzewa)
Dodajmy krawędź do W 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
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 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ż
- algorytm Kruskala
- algorytm Prima
- minimalne drzewo rozpinające
Przypisy
- ↑ OtakarO. Borůvka OtakarO., O jistém problému minimálním / Über ein Minimalproblem, „Práce Mor. Přírodověd. Spol. V Brně III”, 3, 1926, s. 37–58 [dostęp 2022-05-30] (cz. • niem.).
- ↑ OtakarO. Borůvka OtakarO., Příspěvek k řešení otázky ekonomické stavby elektrovodních sítí, „Elektronický Obzor”, 15, 1926, s. 153–154 (cz.).
- ↑ JaroslavJ. Nešetřil JaroslavJ., EvaE. Milková EvaE., HelenaH. Nešetřilová HelenaH., Otakar Borůvka on minimum spanning tree problem Translation of both the 1926 papers, comments, history, „Discrete Mathematics”, 233 (1-3), 2001, s. 3–36, DOI: 10.1016/S0012-365X(00)00224-7 [dostęp 2022-05-30] (ang.).
- ↑ GustaveG. Choquet GustaveG., Étude de certains réseaux de routes, „Comptes Rendus de l'Académie des Sciences”, 206, 1938, s. 310–313 (fr.).
- ↑ K.K. Florek K.K. i inni, Sur la liaison et la division des points d'un ensemble fini, „Colloquium Mathematicum”, 2 (3-4), 1951, s. 282–285 [dostęp 2022-05-30] (fr.).
- ↑ GeorgesG. Sollin GeorgesG., Le tracé de canalisation, [w:] ClaudeC. Berge, AlainA. Ghouila-Houri (red.), Programming, Games, and Transportation Networks, John Wiley & Sons, 1965, LCCN 66001179, OCLC 564487249 (fr.).
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] .
- p
- d
- e
Najważniejsze pojęcia |
więcej... |
---|---|
Wybrane klasy grafów | |
Algorytmy grafowe | |
problemy grafowe | |
Inne zagadnienia |