Algorytm Borůvki: Różnice pomiędzy wersjami
| [wersja przejrzana] | [wersja przejrzana] |
Usunięta treść Dodana treść
Poprawiono niedziałający link |
poprawa linków, lit. |
||
Linia 3:
'''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 [[algorytm zachłanny|algorytmu zachłannego]].
Pierwszy raz opublikowany został w 1926 roku przez [[Otakar Borůvka|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 ==
Linia 24:
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<sub>1</sub> i v<sub>2</sub>. Oznacza to, że do zbioru E' zostały dołączone krawędzie e<sub>i</sub> i e<sub>j</sub>. Ponieważ e<sub>i</sub> została dołączona jako najlżejsza krawędź
* 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 <math>v_1,v_2,v_3 ... v_l</math> będą kolejnymi superwierzchołkami należącymi do C a <math>e_1, e_2, ..., e_l</math> 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 <math>e_i</math> oraz superwierzchołki <math>v_i</math> występują na przemian. Z zasady działania algorytmu możemy stwierdzić, że aby powstał taki cykl, musi zachodzić <math>C(e_1)<C(e_2)<...<C(e_{l-1})<C(e_l)<C(e_1)</math> - Sprzeczność.
Linia 35:
Załóżmy, że istnieje taki superwierzchołek <math>V_i</math>, który nie jest minimalnym drzewem rozpinającym poddrzewa złożonego z wierzchołków należących do <math>V_i</math>. Weźmy więc takie minimalne drzewo rozpinające T. Istnieje krawędź <math>e_i</math> taka, że <math>e_i \in E(V_i) \and e_i \not\in E(T)</math>. Dodajmy <math>e_i</math>. W T powstał cykl. Ponieważ <math>e_i</math> jest incydenta do pewnego wierzchołka z tego cyklu, istnieje więc inna krawędź <math>e'_i</math>
Gdy zostanie zakończony etap 2 :
Linia 44:
'''Fakt:''' Krawędź <math>e_i</math> dodana podczas k-tego wywołania. (Nie może należeć do <math>E'_1</math> 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ź <math>e_i</math> do E(T). W T powstał
==Złożoność obliczeniowa==
| |||