Algorytm Edmondsa

W teorii grafów algorytm Edmondsa lub algorytm Chu – Liu / Edmondsa jest algorytmem znajdowania rozpiętości drzew o minimalnej wadze (czasami nazywanej optymalnym rozgałęzieniem ). Jest to ukierunkowany analog problemu minimalnego drzewa rozpinającego . Algorytm został zaproponowany niezależnie najpierw przez Yoeng-Jin Chu i Tseng-Hong Liu (1965), a następnie przez Jacka Edmondsa (1967).

Algorytm

Opis

Algorytm przyjmuje jako $dane$ $skierowany$ $wykres$ gdzie a zbiorem skierowanych krawędzi, wyróżniony wierzchołek $displaystyle$ pierwiastkiem i $wartościach$ rzeczywistych każdej $e \w E}$ . Zwraca rozciągającą się $zakorzenioną$ w minimalnej $wadze$ , gdzie waga arborescencji jest zdefiniowana jako suma wag jej krawędzi ${\ Displaystyle w (A) = \ suma _ {e \ w A} {w (e)}}$ .

Algorytm ma opis rekurencyjny. Niech ${\ displaystyle f (D, r, w)}$ oznacza funkcję, która zwraca rozpiętą drzewiastość zakorzenioną $.$ minimalnej wadze Najpierw usuwamy każdą krawędź z $displaystyle$ miejscem docelowym jest $r}$ . Możemy również zastąpić dowolny zestaw krawędzi równoległych (krawędzie między tą samą parą wierzchołków w tym samym kierunku) pojedynczą krawędzią o wadze równej minimalnej wadze tych równoległych krawędzi.

Teraz dla każdego węzła $.$ $najniższej$ znajdź krawędź dochodzącą do wagi (z arbitralnie zerwanymi wiązaniami) Oznacz źródło tej krawędzi przez ${\ Displaystyle \ pi (v)}$ . P. $\ in V \ setminus \ {r \} \}}$ nie zawiera żadnych cykli, to ${\ Displaystyle f (D, r, w) = P}$ .

W przeciwnym razie $. Dowolnie wybierz$ co najmniej jeden cykl $go$ z tych cykli i nazwij . Definiujemy $_$ _ jest „zakontraktowany” do jednego węzła w następujący sposób: do {\ displaystyle $}$

Węzły z $}$ $displaystyle V$ to węzły z $displaystyle V}$ nie w plus nowy węzeł oznaczony ${\ displaystyle v_ {C$ .

( ${\ Displaystyle (u, v)}$ krawędzią w ${\ Displaystyle E}$ z ${\ Displaystyle u \ notin C}$ i $\ w C}$ ( krawędź wchodząca w cykl), a następnie uwzględnij w ${\ Displaystyle E ^ {\ liczba pierwsza}}$ i mi $}$ ) zdefiniować ${\ Displaystyle w ^ {\ pierwsza} (e) = w (u, v) -w (\ pi (v) ,v)}$ .
( ${\ Displaystyle (u, v)}$ jest krawędzią w ${\ Displaystyle E}$ i ${\ Displaystyle u \ in C}$ v $\ notin C}$ { \ Displaystyle krawędź odchodząca od cyklu), a następnie uwzględnij w nowej krawędzi ${\ Displaystyle E ^ {\ pierwsza}} , mi$ $\ Displaystyle e = (v_ {C}, v)$ } i zdefiniuj ${\ Displaystyle w ^ {\ pierwsza} (e) = w (u, v)}$ .
( ${\ Displaystyle (u, v)}$ krawędzią w ${\ Displaystyle E}$ ${\ Displaystyle u \ notin C}$ i ( i $}$ krawędź niezwiązana z cyklem), a następnie uwzględnij w $i$ ′ ${\ Displaystyle w ^ {\ pierwsza} (e) = w (u, v)}$ $Displaystyle E ^ {$ zdefiniuj .

$Dla$ każdej krawędzi w $pamiętamy,$ krawędzi w odpowiada.

$f ( D^{\prime},r,w^{\prime})}$ znajdź minimalną rozpiętą arborescencję $za$ wywołania $do$ fa . Ponieważ $drzewicą$ , każdy wierzchołek ma dokładnie jedną krawędź wejściową Niech $})}$ będzie unikalną krawędzią przychodzącą do ${\ displaystyle v_ {C}}$ w ${\ Displaystyle A ^ {\ pierwsza}}$ . Ta krawędź odpowiada krawędzi ${\ Displaystyle (u, v) \ in E}$ ${\ displaystyle v \ in C}$ v . Usuń krawędź z , przerywając cykl ${\ Displaystyle (\ pi (v), v$ $)$ Zaznacz każdą pozostałą $krawędź$ . Dla każdej krawędzi w $,$ $odpowiadającą$ krawędź . $Teraz$ definiujemy zaznaczonych krawędzi,

$\$ re $Displaystyle$ , , gdzie ma znacznie mniej wierzchołków niż ${\ displaystyle$ $^ {\ displaystyle D}$ . Znalezienie wykresu jednowierzchołkowego jest trywialne (jest to po prostu sam), więc algorytm rekurencyjny gwarantuje zakończenie $, w ) {$ $f ($ .

Czas działania

Czas działania tego algorytmu to ${\ Displaystyle O (EV)}$ . Szybsza $)}$ algorytmu dzięki Robertowi Tarjanowi czasie dla rzadkich wykresów i $\ log V$ ${\ Displaystyle O (E$ dla gęstych grafów. Jest to tak szybkie, jak algorytm Prim dla nieskierowanego minimalnego drzewa rozpinającego. W $_$ Gabow , Galil i Tarjan szybszą _

Chu, Yeong-Jin; Liu, Tseng-Hong (1965), „Na najkrótszym drzewie skierowanego wykresu” (PDF) , Scientia Sinica: Chung-kuo k`o hsueh , XIV (10): 1396–1400
Edmonds, J. (1967), „Optymalne rozgałęzienia”, Journal of Research of the National Bureau of Standards Section B , 71B (4): 233–240, doi : 10.6028/jres.071b.032
Tarjan, RE (1977), „Znajdowanie optymalnych rozgałęzień”, Networks , 7 : 25–35, doi : 10.1002/net.3230070103
Camerini, PM; Fratta, L.; Maffioli, F. (1979), „Uwaga na temat znajdowania optymalnych rozgałęzień”, Networks , 9 (4): 309–312, doi : 10.1002/net.3230090403
Gibbons, Alan (1985), Algorytmiczna teoria grafów , Cambridge University Press, ISBN 0-521-28881-9
Gabow, HN ; Galil, Z .; Spencer, T.; Tarjan, RE (1986), „Wydajne algorytmy znajdowania minimalnych drzew rozpinających w grafach nieskierowanych i skierowanych”, Combinatorica , 6 (2): 109–122, doi : 10.1007 / bf02579168 , S2CID 35618095

Linki zewnętrzne

Algorytm Edmondsa (edmonds-alg) – Implementacja algorytmu Edmondsa napisana w C++ i licencjonowana na licencji MIT . To źródło używa implementacji Tarjana dla gęstego grafu.
NetworkX, biblioteka Pythona dystrybuowana pod BSD , posiada implementację algorytmu Edmondsa .