Algoritme d'Edmond

En teoria de grafos, l'algoritme d'Edmond és un algoritme per a trobar una arborescencia de pes mínim (a voltes cridat d'òptima derivació). És l'equivalent dirigit del arbre recubridor mínim. L'algoritme va estar propost independentment primer per Yoeng-Jin Chu i Tseng-Hong Liu (1965) i posteriorment per Jack Edmonds (1967).

Algoritme

Descripció

L'algoritme pren com a entrada un grafo directe $D=⟨V,E⟩$ a on $V$ és el conjunt de nodos, $E$ és el conjunt d'arestes dirigides, $r\in V$ és un vèrtiç distintiu cridat raïl, i un pes real $w(e)$$e\in E$. Açò torna una arborescencia $A$ arraïlada en $r$ com el pes mínim, a on el pes de arborescencia es definix com la suma dels seus pesos: $w(A)=\sum _{e\in A}w(e)$.

L'algoritme té una descripció recursiva. Permet denotar la funció $f(D,r,w)$ que torna la arborescencia arraïlada en $r$ de pes mínim. Primer retirem qualsevol aresta de $E$ que la seua destinación és $r$. També podem substituir qualsevol conjunt d'arestes paraleles (arestes entre el mateix parell de vèrtiços en la mateixa direcció) per una sola aresta en un pes igual al mínim dels pesos d'estes arestes paraleles.

Ara, per a cada nodo $v$ que no siga la raïl, trobe l'aresta entrante a $v$ d$\pi (v)$. Si el conjunt d'arestes $P=\{(\pi (v),v)\mid v\in V\setminus \{r\}\}$ no conté cap cicle, llavors $f(D,r,w)=P$.

Per una atra part, $P$ conté l'últim cicle. Trie arbitrariamente un d'estos cicles i cride-ho $C$. Ara definirem un nou grafo dirigit ponderat$D^{\prime }=⟨V^{\prime },E^{\prime }⟩$ en el qual el cicle $C$ es "contrau" en un nodo de la següent manera:

Els nodos de $V^{\prime }$ són els nodos de $V$ no en $C$ mes un nou nodo denotat $v_C$.

• Si $(u,v)$ és una aresta de $E$ en $u\notin C$ i $v\in C$ (una aresta que entra en un cicle), llavors inclourem en $E^{\prime }$ una nova aresta $e=(u,v_C)$, i definix $w^{\prime }(e)=w(u,v)-w(\pi (v),v)$.
• Si $(u,v)$$E$ en $u\in C$ i $v\notin C$ (una aresta que s'allunta del cicle), despuix incloga $E^{\prime }$ una nova aresta $e=(v_C,v)$, i definixca $w^{\prime }(e)=w(u,v)$.
• Si $(u,v)$ és una aresta de $E$ en $u\notin C$ i $v\notin C$ (una aresta no relacionada en el cicle), despuix incloga en $E^{\prime }$ una nova aresta $e=(u,v)$, i definixca $w^{\prime }(e)=w(u,v)$.

Per cada nodo en $E^{\prime }$, recordarem a quina aresta en $E$ correspon.

$f(D^{\prime },r,w^{\prime })$. ya que $A^{\prime }$ és una arborescencia que comprén, cada vèrtiç té exactament una aresta entrante. Siga $(u,v_C)$ l'únic aresta entrante en $v_C$ en $A^{\prime }$. Esta aresta correspon en una aresta $(u,v)\in E$ en $v\in C$. Elimina l'aresta $(\pi (v),v)$ de $C$, trencant el cicle. $C$. Per cada aresta en $A^{\prime }$, marque esta corresponent aresta en $E$. Ara definixca $f(D,r,w)$ com el conjunt d'arestes marcades que formen una arborescencia d'extensió mínima.

Observe que $f(D,r,w)$ $f(D^{\prime },r,w^{\prime })$, en $D^{\prime }$ $D$. Trobe $f(D,r,w)$ per a un gràfic d'un sol vèrtiç és trivial (és sol $D$ en sí mateixa), per lo que l'algoritme recursivo sempre termina.

Temps d'eixecució

El temps d'eixecució d'este algoritme és $O(EV)$. Una implementació més ràpida de l'algoritme és deguda a Robert Tarjan que eixecuta $O(E\log V)$ $O(V^2)$. Est és tan ràpit com l'Algoritme de Prim p$O(E+V\log V)$.