Apareamiento (teoría de grafos)

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.

un apareamiento M en G es un conjunto de aristas no adyacentes entre sí.

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.

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.

y añadiéndolo al apareamiento si existe.

En un grafo bipartito ponderado, cada arista tiene asociado un valor.

Si el grafo no es completamente bipartito, los arcos ausentes son introducidos con valor cero.

Encontrar tal apareamiento es conocido como problema del asignamiento.

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.