El algoritmo de Edmonds

El algoritmo toma como entrada un grafo dirigido.${\displaystyle D=\langle V,E\rangle }$dónde${\displaystyle V}$es el conjunto de nodos y${\displaystyle E}$es el conjunto de aristas dirigidas, un vértice distinguido${\displaystyle r\in V}$llamada raíz y un peso de valor real${\displaystyle w(e)}$para cada borde${\displaystyle e\in E}$Devuelve una arborescencia que se extiende${\displaystyle A}$enraizado en${\displaystyle r}$de peso mínimo, donde el peso de una arborescencia se define como la suma de los pesos de sus bordes,${\displaystyle w(A)=\sum _{e\in A}{w(e)}}$.

El algoritmo tiene una descripción recursiva.${\displaystyle f(D,r,w)}$denota la función que devuelve una arborescencia de expansión enraizada en${\displaystyle r}$de peso mínimo. Primero eliminamos cualquier borde de${\displaystyle E}$cuyo destino es${\displaystyle r}$También podemos reemplazar 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${\displaystyle v}$aparte de la raíz, encuentra la arista entrante a${\displaystyle v}$de menor peso (los empates se resuelven arbitrariamente). Denotemos el origen de esta arista por${\displaystyle \pi (v)}$. Si el conjunto de aristas${\displaystyle P=\{(\pi (v),v)\mid v\in V\setminus \{r\}\}}$no contiene ningún ciclo, entonces${\displaystyle f(D,r,w)=P}$.

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

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

• Si${\displaystyle (u,v)}$es una ventaja en${\displaystyle E}$con${\displaystyle u\notin C}$ y${\displaystyle v\in C}$(un borde que entra en el ciclo), luego incluir en${\displaystyle E^{\prime }}$un nuevo borde${\displaystyle e=(u,v_{C})}$y definir${\displaystyle w^{\prime }(e)=w(u,v)-w(\pi (v),v)}$.
• Si${\displaystyle (u,v)}$es una ventaja en${\displaystyle E}$con${\displaystyle u\in C}$y${\displaystyle v\notin C}$(un borde que se aleja del ciclo), luego incluir en${\displaystyle E^{\prime }}$un nuevo borde${\displaystyle e=(v_{C},v)}$y definir${\displaystyle w^{\prime }(e)=w(u,v)}$.
• Si${\displaystyle (u,v)}$es una ventaja en${\displaystyle E}$con${\displaystyle u\notin C}$y${\displaystyle v\notin C}$(un borde no relacionado con el ciclo), luego incluir en${\displaystyle E^{\prime }}$un nuevo borde${\displaystyle e=(u,v)}$y definir${\displaystyle w^{\prime }(e)=w(u,v)}$.

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

Ahora encuentra una arborescencia de mínima extensión.${\displaystyle A^{\prime }}$de${\displaystyle D^{\prime }}$utilizando una llamada a${\displaystyle f(D^{\prime },r,w^{\prime })}$. Desde${\displaystyle A^{\prime }}$es una arborescencia de expansión, cada vértice tiene exactamente una arista entrante.${\displaystyle (u,v_{C})}$ser la ventaja entrante única para${\displaystyle v_{C}}$en${\displaystyle A^{\prime }}$Este borde corresponde a un borde${\displaystyle (u,v)\in E}$con${\displaystyle v\in C}$. Quitar el borde${\displaystyle (\pi (v),v)}$de${\displaystyle C}$, rompiendo el ciclo. Marque cada borde restante en${\displaystyle C}$. Para cada arista en${\displaystyle A^{\prime }}$, marca su borde correspondiente en${\displaystyle E}$Ahora definimos.${\displaystyle f(D,r,w)}$ser el conjunto de aristas marcadas, que forman una arborescencia de extensión mínima.

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