Algoritmo de Edmond

En teoría de grafos, el algoritmo de Edmond es un algoritmo para encontrar una arborescencia de peso mínimo (a veces llamado de óptima derivación). Es el equivalente dirigido del árbol recubridor mínimo. El algoritmo estuvo propuesto independientemente primero por Yoeng-Jin Chu y Tseng-Hong Liu (1965) y posteriormente por Jack Edmonds (1967).

Algoritmo

Descripción

El algoritmo toma como entrada un grafo directo $D=\langle V,E\rangle$ donde $V$ es el conjunto de nodos, $E$ es el conjunto de aristas dirigidas, $r\in V$ es un vértice distintivo llamado raíz, y un peso real $w(e)$$e\in E$. Esto devuelve una arborescencia $A$ arraigada en $r$ como el peso mínimo, donde el peso de arborescencia se define como la suma de sus pesos: $w(A)=\sum _{e\in A}{w(e)}$.

El algoritmo tiene una descripción recursiva. Permite denotar la función $f(D,r,w)$ que devuelve la arborescencia arraigada en $r$ de peso mínimo. Primero retiramos cualquier arista de $E$ cuya destinación es $r$. También podemos sustituir cualquier conjunto de aristas paralelas (aristas entre el mismo par de vértices en la misma dirección) por una sola arista con un peso igual al mínimo de los pesos de estas aristas paralelas.

Ahora, para cada nodo $v$ que no sea la raíz, encuentre la arista entrante a $v$ d$\pi (v)$. Si el conjunto de aristas $P=\{(\pi (v),v)\mid v\in V\setminus \{r\}\}$ no contiene ningún ciclo, entonces $f(D,r,w)=P$.

Por otra parte, $P$ contiene el último ciclo. Escoja arbitrariamente uno de estos ciclos y llámelo $C$. Ahora definiremos un nuevo grafo dirigido ponderado$D^{\prime }=\langle V^{\prime },E^{\prime }\rangle$ en el cual el ciclo $C$ se "contrae" en un nodo de la siguiente manera:

Los nodos de $V^{\prime }$ son los nodos de $V$ no en $C$ mas un nuevo nodo denotado $v_{C}$.

• Si $(u,v)$ es una arista de $E$ con $u\notin C$ y $v\in C$ (una arista que entra en un ciclo), entonces incluiremos en $E^{\prime }$ una nueva arista $e=(u,v_{C})$, y define $w^{\prime }(e)=w(u,v)-w(\pi (v),v)$.
• Si $(u,v)$$E$ con $u\in C$ y $v\notin C$ (una arista que se aleja del ciclo), luego incluya $E^{\prime }$ una nueva arista $e=(v_{C},v)$, y defina $w^{\prime }(e)=w(u,v)$.
• Si $(u,v)$ es una arista de $E$ con $u\notin C$ y $v\notin C$ (una arista no relacionada con el ciclo), luego incluya en $E^{\prime }$ una nueva arista $e=(u,v)$, y defina $w^{\prime }(e)=w(u,v)$.

Por cada nodo en $E^{\prime }$, recordaremos a qué arista en $E$ corresponde.

$f(D^{\prime },r,w^{\prime })$. Puesto que $A^{\prime }$ es una arborescencia que abarca, cada vértice tiene exactamente una arista entrante. Sea $(u,v_{C})$ el único arista entrante en $v_{C}$ en $A^{\prime }$. Esta arista corresponde con una arista $(u,v)\in E$ con $v\in C$. Elimina la arista $(\pi (v),v)$ de $C$, rompiendo el ciclo. $C$. Por cada arista en $A^{\prime }$, marque esta correspondiente arista en $E$. Ahora defina $f(D,r,w)$ como el conjunto de aristas marcadas que forman una arborescencia de extensión mínima.

Observe que $f(D,r,w)$ $f(D^{\prime },r,w^{\prime })$, con $D^{\prime }$ $D$. Halle $f(D,r,w)$ para un gráfico de un solo vértice es trivial (es solo $D$ en sí mismo), por lo que el algoritmo recursivo siempre termina.

Tiempo de ejecución

El tiempo de ejecución de este algoritmo es $O(EV)$. Una implementación más rápida del algoritmo es debida a Robert Tarjan que ejecuta $O(E\log V)$ $O(V^{2})$. Este es tan rápido como el Algoritmo de Prim p$O(E+V\log V)$.

Referencias

• Chu, Y. J.; Liu, T. H. (1965), «On the Shortest Arborescence of a Directed Graph», Science Sinica 14: 1396-1400 .
• Edmonds, J. (1967), «Optimum Branchings», J. Res. Nat. Bur. Standards, 71B: 233-240, doi:10.6028/jres.071b.032 .
• Tarjan, R. E. (1977), «Finding Optimum Branchings», Networks 7: 25-35, doi:10.1002/net.3230070103 .
• Camerini, P.M.; Fratta, L.; Maffioli, F. (1979), «A note on finding optimum branchings», Networks 9: 309-312, doi:10.1002/net.3230090403 .
• Gibbons, Alan (1985), Algorithmic Graph Theory, Cambridge University press, ISBN 0-521-28881-9 .
• Gabow, H. N.; Galil, Z.; Spencer, T.; Tarjan, R. E. (1986), «Efficient algorithms for finding minimum spanning trees in undirected and directed graphs», Combinatorica 6: 109-122, doi:10.1007/bf02579168 .

Enlaces externos

• Edmonds's algorithm ( edmonds-alg ) – An open source implementation of Edmonds's algorithm written in C++ and licensed under the MIT License. This source is using Tarjan's implementation for the dense graph.

• Datos: Q1752324