Algoritmo de Emparejamiento de Edmonds

El Algoritmo del Blossom o Algoritmo de Emparejamiento de Edmonds es un algoritmo de teoría de grafos para construir emparejamientos máximos en grafos. El algoritmo fue desarrollado por Jack Edmonds en 1961,^[1]​ y publicado en 1965.^[2]​ El emparejamiento máximo es construido iterativamente mejorando el emparejamiento actual a través de caminos m-incrementos mientras al menos exista uno. La idea esencial del algoritmo es que un ciclo de longitud impar (blossom) es contraído en un solo vértice para luego continuar la búsqueda de caminos m-incrementos en el grafo resultante. La idea de contraer los ciclos de longitud impar se debe a que si no se hiciera el mismo algoritmo de búsqueda de caminos m-incrementos al entrar en uno de estos ciclos y salir pudiera reportar falsos positivos.

La importancia del algoritmo radicó en que dio la primera prueba de que un emparejamiento máximo puede ser encontrado en tiempo polinomial.

Se mantienen los nombres de las definiciones en inglés para mayor entendimiento con la literatura. Si se hiciera una traducción literal entonces 'blossom' sería capullo, 'stem' sería tallo y 'flower' sería flor. Edmonds realiza una analogía entre la estructura de las flores y las estructuras utilizadas por el algoritmo.

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 Mcap E(B)}$ es un emparejamiento máximo en ${displaystyle B}$. (Obsérvese ${displaystyle Mcap 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 Mvee (a,b) ot in Bvee (vin Bwedge b ot in B)}}$ (${displaystyle v}$ sería el vértice ficticio del blossom). Se denote ${displaystyle M/B}$.

Sea ${displaystyle B}$ un blossom de una flower ${displaystyle F}$ sobre un emparejamiento ${displaystyle M}$ en un grafo ${displaystyle G}$ entonces: ${displaystyle M}$ es un emparejamiento máximo en ${displaystyle G}$ si y solo si ${displaystyle M/B}$ es un emparejamiento en ${displaystyle G/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:

El algoritmo para encontrar caminos m-incrementos utiliza una estructura de datos llamada bosque, cuyos árboles individuales corresponden a partes específicas del grafo. En cada iteración del algoritmo ocurre algunas de las siguientes opciones (1) encuentra un camino m-incremento, (2) encuentra un blossom, lo comprime y comienza la búsqueda en el grafo resultante o (3) concluye al no encontrar caminos m-incrementos.

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})}$.