En teoría de grafos , el algoritmo de Edmonds o el 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 la dirigida analógica del árbol de expansión mínimo problema. 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 dónde es el conjunto de nodos y es el conjunto de aristas dirigidas, un vértice distinguido llamada raíz , y un peso con valor real para cada borde . Devuelve una arborescencia que se extiende arraigado en de peso mínimo, donde el peso de una arborescencia se define como la suma de sus pesos de borde, .
El algoritmo tiene una descripción recursiva. Dejar denotar la función que devuelve una arborescencia de expansión enraizada en de peso mínimo. Primero eliminamos cualquier borde de cuyo destino es . 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 un peso igual al mínimo de los pesos de estos bordes paralelos.
Ahora, para cada nodo que no sea la raíz, busque el borde entrante a de menor peso (con lazos rotos arbitrariamente). Denote la fuente de este borde por. Si el conjunto de bordes no contiene ningún ciclo, entonces .
De lo contrario, contiene al menos un ciclo. Elija arbitrariamente uno de estos ciclos y llámelo. Ahora definimos un nuevo gráfico dirigido ponderado en el que el ciclo se "contrae" en un nodo de la siguiente manera:
Los nodos de son los nodos de no en más un nuevo nodo denotado.
- Si es una ventaja en con y (una ventaja que entra en el ciclo), luego incluya en una nueva ventaja y definir .
- Si es una ventaja en con y (una ventaja que se aleja del ciclo), luego incluya en una nueva ventaja y definir .
- Si es una ventaja en con y (una ventaja no relacionada con el ciclo), luego incluir en una nueva ventaja y definir .
Por cada borde en , recordamos en qué borde corresponde a.
Ahora encuentre una arborescencia de expansión mínima de usando una llamada a . Desdees una arborescencia que se extiende, cada vértice tiene exactamente un borde entrante. Dejar ser la ventaja entrante única para en . Este borde corresponde a un borde con . Quitar el borde de , rompiendo el ciclo. Marque cada borde restante en. Por cada borde en, marque su borde correspondiente en . Ahora definimos ser el conjunto de aristas marcadas, que forman una arborescencia de mínima extensión.
Observa eso se define en términos de , con tener estrictamente menos vértices que . Hallazgo para un gráfico de un solo vértice es trivial (es solo sí mismo), por lo que se garantiza que el algoritmo recursivo terminará.
Tiempo de ejecución
El tiempo de ejecución de este algoritmo es . Una implementación más rápida del algoritmo debido a Robert Tarjan se ejecuta en el tiempopara gráficos dispersos ypara gráficos densos. Esto es tan rápido como el algoritmo de Prim para un árbol de expansión mínimo no dirigido. En 1986, Gabow, Galil, Spencer, Compton y Tarjan produjeron una implementación más rápida, con tiempo de ejecución.
Referencias
- Chu, YJ; Liu, TH (1965), "Sobre la arborescencia más corta de un gráfico dirigido", Science Sinica , 14 : 1396–1400
- Edmonds, J. (1967), "Optimum Branchings", 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), "Finding Optimum Branchings", Networks , 7 : 25–35, doi : 10.1002 / net.3230070103
- Camerini, PM; Fratta, L .; Maffioli, F. (1979), "Una nota sobre la búsqueda de 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 gráficos dirigidos y no dirigidos", Combinatorica , 6 (2): 109-122, doi : 10.1007 / bf02579168
enlaces externos
- Algoritmo de Edmonds (edmonds-alg) : una implementación del algoritmo de Edmonds escrito en C ++ y con licencia de MIT License . 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 .