Matching

En matemática discreta y en particular en la teoría de grafos, un apareamiento o conjunto independiente de aristas, también llamado emparejamiento o matching (en inglés), en un grafo es un conjunto de aristas independientes, es decir, sin vértices en común.

Dado un grafo ${displaystyle G=(V,E),}$ un apareamiento M en G es un conjunto de aristas no adyacentes entre sí.

Decimos que un vértice está apareado (acoplado saturado) si es incidente con una arista en el apareamiento. En otro caso, el vértice está libre.

Un apareamiento máximo es un apareamiento que contiene el número máximo posible de aristas. Puede haber muchos apareamientos máximos. El número de apareamiento de un grafo es el tamaño del apareamiento máximo.

Un apareamiento maximal es un apareamiento M de un grafo G con la propiedad de que si alguna arista que no pertenece a M es añadido a M, no será ya un apareamiento. Nótese que todos los apareamiento máximos deben ser maximales, pero no todos los apareamiento maximales deben de ser máximos.

Un apareamiento perfecto es un apareamiento que cubre todos los vértices del grafo. Esto es, cada vértice está saturado bajo el apareamiento. Cada apareamiento perfecto es máximo y maximal.

Dado un apareamiento M

Nótese que un apareamiento es máximo si y sólo si no contiene ningún camino M-incremento.

Los problemas de apareamiento tienen relación muchas veces con grafos bipartitos. Encontrar un apareamiento máximo bipartito (a menudo llamado cardinalidad máxima de un grafo bipartito) en un grafo bipartito ${displaystyle G=(V=(X,Y),E),}$ es quizás el problema más simple. El algoritmo de los caminos aumentantes lo encuentra por búsqueda de caminos aumentantes por cada ${displaystyle xin X}$ a ${displaystyle Y,}$ y añadiéndolo al apareamiento si existe. Como cada camino puede ser encontrado en tiempo ${displaystyle O(E),}$, el costo de tiempo es ${displaystyle O(VE),}$. Todas las aristas con flujo de ${displaystyle X,}$ a ${displaystyle Y,}$ constituyen un apareamiento máximo. Una mejora sobre esto es el algoritmo de Hopcroft-Karp, de costo de tiempo ${displaystyle O({sqrt {V}}E),}$.

En un grafo bipartito ponderado, cada arista tiene asociado un valor. Un apareamiento máximo bipartito ponderado está definido como un apareamiento perfecto donde la suma de los valores de sus arcos en el apareamiento tiene un valor maximal. Si el grafo no es completamente bipartito, los arcos ausentes son introducidos con valor cero. Encontrar tal apareamiento es conocido como problema del asignamiento. Para resolverlo se usa la búsqueda del camino mínimo modificado con el algoritmo del camino aumentante. Si usamos el algoritmo de Bellman-Ford, con costo de tiempo ${displaystyle O(V^{2}E),}$. El más especializado es el algoritmo Húngaro que resuelve el problema de asignación con costo de tiempo ${displaystyle O(V^{3}),}$.

Existe un algoritmo en tiempo polinomial que es capaz de encontrar un emparejamiento máximo en un grafo que no es bipartito. Este fue desarrollado por Jack Edmonds y fue publicado en un artículo llamado Paths, trees, and flowers en 1965.^[1]​ El algoritmo recibe el nombre de Algoritmo de Emparejamiento de Edmonds.

---