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

editar

Descripción

editar

El algoritmo toma como entrada un grafo directo   donde   es el conjunto de nodos,   es el conjunto de aristas dirigidas,   es un vértice distintivo llamado raíz, y un peso real   . Esto devuelve una arborescencia   arraigada en   como el peso mínimo, donde el peso de arborescencia se define como la suma de sus pesos:  .

El algoritmo tiene una descripción recursiva. Permite denotar la función   que devuelve la arborescencia arraigada en   de peso mínimo. Primero retiramos cualquier arista de   cuya destinación es  . 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   que no sea la raíz, encuentre la arista entrante a   d . Si el conjunto de aristas   no contiene ningún ciclo, entonces  .

Por otra parte,   contiene el último ciclo. Escoja arbitrariamente uno de estos ciclos y llámelo  . Ahora definiremos un nuevo grafo dirigido ponderado  en el cual el ciclo   se "contrae" en un nodo de la siguiente manera:

Los nodos de   son los nodos de   no en   mas un nuevo nodo denotado  .

  • Si   es una arista de   con   y   (una arista que entra en un ciclo), entonces incluiremos en   una nueva arista  , y define  .
  • Si    con   y   (una arista que se aleja del ciclo), luego incluya   una nueva arista  , y defina  .
  • Si   es una arista de   con   y   (una arista no relacionada con el ciclo), luego incluya en   una nueva arista  , y defina  .

Por cada nodo en  , recordaremos a qué arista en   corresponde.

 . Puesto que   es una arborescencia que abarca, cada vértice tiene exactamente una arista entrante. Sea   el único arista entrante en   en  . Esta arista corresponde con una arista   con  . Elimina la arista   de  , rompiendo el ciclo.  . Por cada arista en  , marque esta correspondiente arista en  . Ahora defina   como el conjunto de aristas marcadas que forman una arborescencia de extensión mínima.

Observe que    , con    . Halle   para un gráfico de un solo vértice es trivial (es solo   en sí mismo), por lo que el algoritmo recursivo siempre termina.

Tiempo de ejecución

editar

El tiempo de ejecución de este algoritmo es  . Una implementación más rápida del algoritmo es debida a Robert Tarjan que ejecuta    . Este es tan rápido como el Algoritmo de Prim p .

Referencias

editar
  • 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

editar