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,​ y publicado en 1965.​ 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.