Algorytm Borůvki
Algorytm Borůvki to technika służąca do wyznaczania minimalnego drzewa rozpinającego w spójnym, nieskierowanym grafie ważonym. W praktyce oznacza to, że algorytm ten identyfikuje drzewo obejmujące wszystkie wierzchołki grafu, którego całkowita waga jest najmniejsza. Jest to przykład algorytmu zachłannego.
Pierwsze publikacje na temat tego algorytmu pojawiły się w 1926 roku, kiedy to został on zaprezentowany przez Otakara Borůvkę jako efektywna metoda budowy sieci energetycznych. W 1938 roku algorytm został ponownie opracowany przez Choqueta, a później przez Florka, Łukasiewicza, Perkala, Steinhausa i Zubrzyckiego w 1951 roku. Ostatecznie w latach 60. XX wieku algorytm został przypisany Sollinowi, stąd często określany jest jako „algorytm Sollina”.
Algorytm
Algorytm funkcjonuje poprawnie pod warunkiem, że wszystkie krawędzie grafu mają różne wagi. W przeciwnym razie można nadać każdej krawędzi unikalny indeks. W przypadku porównania dwóch krawędzi o identycznej wadze, wybierana jest ta z niższym numerem.
Dla każdego wierzchołka v w grafie G, przeglądany jest zbiór krawędzi z nim incydentnych. Najlżejsza krawędź jest dodawana do zbioru rozwiązań (zbioru E’). Po tym kroku graf tymczasowego rozwiązania powinien mieć nie więcej niż |V|/2 spójnych składowych. Następnie tworzony jest graf G’, w którym wierzchołki tworzące spójne składowe są łączone (nowe wierzchołki nazywamy roboczo superwierzchołkami).
Operacje 1 i 2 powtarzane są, aż do uzyskania jednej spójnej składowej, przy czym graf G zastępowany jest przez G’. Po zakończeniu algorytmu, G’ stanowi minimalne drzewo rozpinające.
Dowód poprawności
Lemat 1
W każdym momencie działania algorytmu oraz po jego zakończeniu w zbiorze E’ nie występuje cykl.
Dowód: Załóżmy nie wprost, że w pewnym momencie działania algorytmu pojawiła się spójna składowa zawierająca cykl, oznaczmy ją jako S. Rozważmy sytuację, w której S powstała przez połączenie dwóch superwierzchołków v1 i v2. To oznacza, że do zbioru E’ dodano krawędzie ei i ej. Skoro ei została dodana jako najlżejsza krawędź incydentna do v1, to musi zachodzić C(ei) < C(ej). Jednak jeżeli ej została dołączona jako najlżejsza krawędź incydentna do v2, to musi zachodzić C(ej) < C(ei), co prowadzi do sprzeczności (przypominając, że w grafie nie ma krawędzi o tej samej wadze).
Możemy także rozważyć przypadek, w którym S powstała z trzech lub więcej superwierzchołków, dzieląc cykl C na części, co prowadzi do podobnych wniosków jak powyżej.
Lemat 2
W każdym etapie działania algorytmu dla każdego superwierzchołka uzyskujemy minimalne drzewo rozpinające.
Dowód: Po zakończeniu etapu 1, zakładamy, że istnieje superwierzchołek Vi, który nie jest minimalnym drzewem rozpinającym dla poddrzewa zbudowanego z wierzchołków należących do Vi. Z tego można wywnioskować, że istnieje krawędź ei, która nie została dodana do T, co prowadzi do sprzeczności z założeniem minimalności T.
Po zakończeniu etapu 2, zakładamy, że superwierzchołki są minimalnymi drzewami rozpinającymi, ale łącząc je w sposób, który prowadzi do mniejszego drzewa rozpinającego, co jest sprzeczne z założeniem, że k jest pierwszym takim etapem.
Złożoność obliczeniowa
Można udowodnić, że z każdym kolejnym wywołaniem liczba wierzchołków zmniejsza się co najmniej dwukrotnie, co oznacza, że maksymalna liczba wywołań wynosi log V. Całkowita złożoność obliczeniowa zależy od sposobu implementacji kroków 1 i 2 algorytmu. Zastosowanie struktury zbiorów rozłącznych pozwala uzyskać złożoność na poziomie O(E log V). Alternatywnie, można zmodyfikować algorytm, aby osiągnąć złożoność O(E log V – V), co może znacznie przyspieszyć działanie dla rzadkich grafów, podczas gdy w przypadku grafów gęstych modyfikacja nie przynosi znaczących zysków czasowych.
Zobacz też
Przypisy
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].
