Algoritmo de Edmonds

Algoritmo para la versión dirigida del problema del árbol de expansión mínimo

En teoría de grafos , el algoritmo de Edmonds o algoritmo de Chu–Liu/Edmonds es un algoritmo para encontrar una arborescencia de expansión de peso mínimo (a veces llamada ramificación óptima ). Es el análogo dirigido del problema del árbol de expansión mínimo . El algoritmo fue propuesto de forma independiente primero por Yoeng-Jin Chu y Tseng-Hong Liu (1965) y luego por Jack Edmonds (1967).

Algoritmo

Descripción

El algoritmo toma como entrada un gráfico dirigido donde es el conjunto de nodos y es el conjunto de aristas dirigidas, un vértice distinguido llamado raíz y un peso de valor real para cada arista . Devuelve una arborescencia en expansión con raíz en de peso mínimo, donde el peso de una arborescencia se define como la suma de los pesos de sus aristas, . ${\displaystyle D=\langle V,E\rangle }$ ${\displaystyle V}$ ${\displaystyle E}$ ${\displaystyle r\in V}$ ${\displaystyle w(e)}$ ${\displaystyle e\in E}$ ${\displaystyle A}$ ${\displaystyle r}$ ${\displaystyle w(A)=\sum _{e\in A}{w(e)}}$

El algoritmo tiene una descripción recursiva. Sea la función que retorna una arborescencia de expansión con raíz en de peso mínimo. Primero eliminamos cualquier borde cuyo destino sea . También podemos reemplazar cualquier conjunto de bordes paralelos (bordes entre el mismo par de vértices en la misma dirección) por un solo borde con peso igual al mínimo de los pesos de estos bordes paralelos. ${\displaystyle f(D,r,w)}$ ${\displaystyle r}$ ${\displaystyle E}$ ${\displaystyle r}$

Ahora, para cada nodo que no sea la raíz, encuentre la arista que ingresa a con el peso más bajo (con los lazos rotos arbitrariamente). Denote la fuente de esta arista por . Si el conjunto de aristas no contiene ningún ciclo, entonces . ${\displaystyle v}$ ${\displaystyle v}$ ${\displaystyle \pi (v)}$ ${\displaystyle P=\{(\pi (v),v)\mid v\in V\setminus \{r\}\}}$ ${\displaystyle f(D,r,w)=P}$

De lo contrario, contiene al menos un ciclo. Elija arbitrariamente uno de estos ciclos y llámelo . Ahora definimos un nuevo grafo dirigido ponderado en el que el ciclo se "contrae" en un nodo de la siguiente manera: ${\displaystyle P}$ ${\displaystyle C}$ ${\displaystyle D^{\prime }=\langle V^{\prime },E^{\prime }\rangle }$ ${\displaystyle C}$

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

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

Para cada borde en , recordamos a qué borde corresponde. ${\displaystyle E^{\prime }}$ ${\displaystyle E}$

Ahora, encuentre una arborescencia de expansión mínima de usando una llamada a . Como es una arborescencia de expansión, cada vértice tiene exactamente una arista entrante. Sea la única arista entrante a en . Esta arista corresponde a una arista con . Elimine la arista de , rompiendo el ciclo. Marque cada arista restante en . Para cada arista en , marque su arista correspondiente en . Ahora definimos como el conjunto de aristas marcadas, que forman una arborescencia de expansión mínima. ${\displaystyle A^{\prime }}$ ${\displaystyle D^{\prime }}$ ${\displaystyle f(D^{\prime },r,w^{\prime })}$ ${\displaystyle A^{\prime }}$ ${\displaystyle (u,v_{C})}$ ${\displaystyle v_{C}}$ ${\displaystyle A^{\prime }}$ ${\displaystyle (u,v)\in E}$ ${\displaystyle v\in C}$ ${\displaystyle (\pi (v),v)}$ ${\displaystyle C}$ ${\displaystyle C}$ ${\displaystyle A^{\prime }}$ ${\displaystyle E}$ ${\displaystyle f(D,r,w)}$

Observe que se define en términos de , con estrictamente menos vértices que . Encontrar un gráfico de un solo vértice es trivial (es simplemente él mismo), por lo que se garantiza que el algoritmo recursivo terminará. ${\displaystyle f(D,r,w)}$ ${\displaystyle f(D^{\prime },r,w^{\prime })}$ ${\displaystyle D^{\prime }}$ ${\displaystyle D}$ ${\displaystyle f(D,r,w)}$ ${\displaystyle D}$

Duración del programa

El tiempo de ejecución de este algoritmo es . Una implementación más rápida del algoritmo debido a Robert Tarjan se ejecuta a tiempo para gráficos dispersos y para gráficos densos. Esto es tan rápido como el algoritmo de Prim para un árbol de expansión mínima no dirigido. En 1986, Gabow , Galil , Spencer y Tarjan produjeron una implementación más rápida, con un tiempo de ejecución . ${\displaystyle O(EV)}$ ${\displaystyle O(E\log V)}$ ${\displaystyle O(V^{2})}$ ${\displaystyle O(E+V\log V)}$

Referencias

• Chu, Yeong-Jin; Liu, Tseng-Hong (1965), "Sobre la arborescencia más corta de un grafo dirigido" (PDF) , Scientia Sinica , XIV (10): 1396–1400
• Edmonds, J. (1967), "Ramificaciones óptimas", Revista de investigación de la Oficina Nacional de Normas, Sección B , 71B (4): 233–240, doi : 10.6028/jres.071b.032
• Tarjan, RE (1977), "Encontrar ramificaciones óptimas", Networks , 7 : 25–35, doi :10.1002/net.3230070103
• Camerini, PM; Fratta, L.; Maffioli, F. (1979), "Una nota sobre cómo encontrar ramificaciones óptimas", Networks , 9 (4): 309–312, doi :10.1002/net.3230090403
• Gibbons, Alan (1985), Teoría de grafos algorítmicos , Cambridge University Press, ISBN 0-521-28881-9
• Gabow, HN ; Galil, Z. ; Spencer, T.; Tarjan, RE (1986), "Algoritmos eficientes para encontrar árboles de expansión mínimos en grafos dirigidos y no dirigidos", Combinatorica , 6 (2): 109–122, doi :10.1007/bf02579168, S2CID  35618095

Enlaces externos

• Algoritmo de Edmonds (edmonds-alg): una implementación del algoritmo de Edmonds escrita en C++ y con licencia MIT . Esta fuente utiliza la implementación de Tarjan para el gráfico denso.
• NetworkX, una biblioteca de Python distribuida bajo BSD , tiene una implementación del algoritmo de Edmonds.