Algorytm Borůvki: Różnice pomiędzy wersjami

Dodane 24 bajty ,  10 lat temu
poprawa linków, lit.
(Poprawiono niedziałający link)
(poprawa linków, lit.)
'''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 ==
 
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ź incydentaincydentna do v<sub>1</sub> więc <math>C(e_i) < C(e_j)</math>. Ale skoro e<sub>j</sub> została dołączona jako najlżejsza krawędź incydentaincydentna do v<sub>2</sub> to musi zachodzić <math>C(e_j) < C(e_i) </math> (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 <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ść.
 
 
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>
incydentaincydentna do tego samego wierzchołka. Jednak z tego, że <math>e_i \in E(V_i)</math> wynika, że <math>C(e_i) < C(e'_i)</math>. Jeśli usuniemy krawędź <math>e'_i</math> z T otrzymamy mniejsze drzewo rozpinające, co jest sprzeczne z założeniem o minimalności T.
 
Gdy zostanie zakończony etap 2 :
'''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ł cylcykl. Ponieważ <math>e_i</math> 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 <math>e_i</math>, zatem zastąpienie jej krawędzią <math>e_i</math> da nam mniejsze drzewo rozpinające co jest sprzeczne z założeniem o optymalności T.
 
==Złożoność obliczeniowa==
Anonimowy użytkownik