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.

Definición

Tres ejemplos de apareamientos maximales, representados por las aristas rojas

Dado un grafo 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. 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. 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.

Other Languages