Algoritmo de Emparejamiento de Edmonds

Un vértice se dice saturado por un emparejamiento, cuando él es extremo de alguna arista del emparejamiento.

Un blossom ${\displaystyle B}$ sobre un emparejamiento ${\displaystyle M}$ en un grafo ${\displaystyle G=(V,E)}$, es un ciclo de longitud impar que cumple que ${\displaystyle M\cap E(B)}$ es un emparejamiento máximo en ${\displaystyle B}$. (Obsérvese ${\displaystyle M\cap E(B)}$ deja uno y sólo un vértice ${\displaystyle b}$ sin estar emparejado).

Un stem sobre un emparejamiento ${\displaystyle M}$ un grafo ${\displaystyle G=(V,E)}$ es un vértice no saturado por ${\displaystyle M}$ o un camino m-alternativo con un extremo no saturado y el otro sí.

Se define como flower a un blossom y un stem interceptados en solo uno de los extremos del stem (vértice ${\displaystyle b}$ no saturado del blossom).

Sea ${\displaystyle B}$ un blossom de una flower ${\displaystyle F}$ sobre un emparejamiento ${\displaystyle M}$ en un grafo ${\displaystyle G}$ se define como contracción de ${\displaystyle B}$ en el grafo ${\displaystyle G}$, al grafo ${\displaystyle G'}$ que resulta de sustituir a ${\displaystyle B}$ por un vértice ficticio ${\displaystyle b}$, el cual es adyacente a todos los vértices ${\displaystyle v_{i}}$ adyacentes a los vértices de ${\displaystyle B}$ y se denota como ${\displaystyle G/B}$.

Sea ${\displaystyle B}$ un blossom de una flower ${\displaystyle F}$ sobre un emparejamiento ${\displaystyle M}$ en un grafo ${\displaystyle G}$ se define como contracción de ${\displaystyle B}$ en el emparejamiento ${\displaystyle M}$, al emparejamiento ${\displaystyle M'=\{(a,b)\in M\vee (a,b)\not \in B\vee (v\in B\wedge b\not \in B)\}}$ (${\displaystyle v}$ sería el vértice ficticio del blossom). Se denote ${\displaystyle M/B}$.

La parte de la demostración más interesante del algoritmo es probar que si ${\displaystyle G/B(G')}$ tiene un camino m-incremento ${\displaystyle p'=(v_{0}\,\ldots \,v_{t})}$ entonces ${\displaystyle G}$ tiene un camino m-incremento ${\displaystyle p}$ semejante a ${\displaystyle p'}$.

Para la demostración se separan varios casos:

1. El camino m-incremento en ${\displaystyle G'}$ no contiene ningún vértice ficticio, entonces el grafo ${\displaystyle G}$ contiene el mismo camino m-incremento sin modificación.
2. El camino m-incremento en ${\displaystyle G'}$ contiene a un vértice ficticio (sin pérdida de generalidad), este a su vez se subdivide en dos casos:
   1. El vértice ficticio no se encuentra en un extremo del camino m-incremento ${\displaystyle p'}$, entonces en ${\displaystyle G}$ encontraremos el siguiente camino m-incremento ${\displaystyle (v_{0}\rightarrow \ldots \rightarrow w\rightarrow w'\rightarrow \ldots \rightarrow u'\rightarrow u\rightarrow \ldots \rightarrow v_{t})}$ , el camino m – alternativo ${\displaystyle (w'\rightarrow \ldots \rightarrow u')}$ existe como consecuencia de la definición de blossom. Supongamos que no exista, esto sería si en algún momento no se puede alternar entre emparejado-no emparejado, la única forma posible que ocurra esto en un emparejamiento correcto es emparejado – no emparejado – no emparejado, esto por la definición de blossom no puede ocurrir ya que el único vértice que puede no estar emparejado con uno dentro del blossom es ${\displaystyle u'}$, sino no se cumpliría que ${\displaystyle M\cap E(B)}$ sea un emparejamiento máximo en ${\displaystyle B}$. El otro problema que pudiera ocurrir es que al salir del blossom por la arista ${\displaystyle w'-w}$ hallamos escogido un camino que seleccionaba como arista anterior a ${\displaystyle w'-w}$ una que no pertenece al emparejamiento, cuestión que no crearía un camino m-incremento, esto se resuelve escogiendo el otro camino posible de ${\displaystyle u'-w'}$ del blossom (existen dos debido a que el blossom es un ciclo).

1. 1. El vértice ficticio se encuentra en un extremo del camino m-incremento ${\displaystyle p'}$, donde ${\displaystyle v_{t}=v}$, entonces en ${\displaystyle G}$ encontraremos el siguiente camino m-incremento ${\displaystyle v_{0}\rightarrow \ldots \rightarrow u\rightarrow u'\rightarrow \ldots \rightarrow v'}$, el camino m – alternativo ${\displaystyle (u'\rightarrow \ldots \rightarrow v')}$ existe como consecuencia de la definición de blossom (Ver el caso anterior). (Observación: este blossom no puede tener ningún vértice emparejado con uno exterior al blossom por lo tanto queda uno y solo uno no saturado por el emparejamiento).

El ciclo de la línea 04 agrega los vértices no saturados para un costo O(|V|), el ciclo de la línea 14 se ejecuta |E| veces y por cada iteración suponiendo que se encuentra un blossom este se contrae en O(|V|) y se llama recursivamente al mismo algoritmo, partiendo de que pueden haber a lo sumo ${\displaystyle O(|V|)}$ blossoms obtenemos un costo de ${\displaystyle O(|V|^{4})}$.