Apareamiento (teoría de gráficas)

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.

Definición

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

Decimos que un vértice está apareado (acopladoo 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. Pueden 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. Ésto es, cada vértice está saturado bajo el apareamiento. Cada apareamiento perfecto es máximo y maximal.

Dado un apareamiento M

• una trayectoria M-alternante es una trayectoria en la cual sus aristas alternativamente pertenecen y no pertenecen al apareamiento.
• una trayectoria M-aumentante es una trayectoria M-alternante que comienza y termina en un vértice libre.

Nótese que un apareamiento es máximo si y sólo si no contiene ninguna trayectoria M-aumentante.

Apareamientos en grafos bipartitos

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 $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 $x \in X$ a $Y\,$ y añadiéndolo al apareamiento si existe. Como cada camino puede ser encontrado en tiempo $O(E)\,$, el costo de tiempo es $O(V E)\,$. Todas las aristas con flujo de $X\,$ a $Y\,$ constituyen un apareamiento máximo. Una mejora sobre esto es el algoritmo de Hopcroft-Karp, de costo de tiempo $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 $O(V^2 E)\,$. El más especializado es el algoritmo Húngaro que resuelve el problema de asignación con costo de tiempo $O(V^3)\,$.

Propiedades

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

Véase también

• Conjunto de vertices independientes
• Descomposición de Dulmage-Mendelsohn

Referencias

1. ↑ Gallai, Tibor. "Über extreme Punkt- und Kantenmengen." Ann. Univ. Sci. Budapest, Eotvos Sect. Math. 2, 133-138, 1959.

• 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.