Apareamiento (teoría de grafos)

Tres ejemplos de apareamientos maximales, representados por las aristas rojas

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.

Tres ejemplos de apareamientos máximos

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 apareamientos 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

• un camino M-alterno es un camino en el cual sus aristas alternativamente pertenecen y no pertenecen al apareamiento.
• un camino M-incremento es un camino M-alternato que comienza y termina en un vértice libre.

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 x\in 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.

• Para un grafo G con n vértices sin vértices aislados el número de apareamiento + número de aristas de covering = n.[2]
• Un grafo con n vértices y un apareamiento perfecto tiene un número de apareamiento igual a n/2.

• Conjunto de vértices independientes
• Descomposición de Dulmage-Mendelsohn

• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Section 26.3: Maximum bipartite apareamiento, pp.664–669.
• West, Douglas Brent (1999) [1996]. «3». Introduction to Graph Theory (2nd edition edición). Prentice Hall. ISBN 0-13-014400-2.