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.
deja uno y sólo un vértice
es un vértice no saturado por
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
no saturado del blossom).
un blossom de una flower
se define como contracción de
que resulta de sustituir a
, el cual es adyacente a todos los vértices
adyacentes a los vértices de
y se denota como
un blossom de una flower
se define como contracción de
sería el vértice ficticio del blossom).
La parte de la demostración más interesante del algoritmo es probar que si
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
blossoms obtenemos un costo de