Matching
De Wikipedia, la enciclopedia libre
En matemáticas, en el campo de la teoría de grafos un matching o conjunto independiente de arcos en un grafo es un conjunto de arcos sin vértices en común.
Tabla de contenidos |
[editar] Definición
Dado un grafo 
un matching M en G es un conjunto de arcos disjuntos no adyacentes.
Decimos que un vértice está matched (acoplado) si es incidido por un arco en el matching. Sino el vértice está unmatched (libre).
Un matching máximo es un matching que contiene el número máximo posible de arcos. Pueden haber muchos matchings máximos. El número de matching de un grafo es el tamaño del matching máximo.
Un matching maximal es un matching M de un grafo G con la propiedad de que si algún arco que no pertenece a M es añadido a M, no será ya un matching. Notese que todos los matching máximos deben ser maximales, pero no todos los matching maximales deben de ser máximos.
Un matching perfecto es un matching que cubre todos los vértices del grafo. Esto es, cada vértice del grafo es incidido por solo un arco del matching. Cada matching perfecto es máximo y maximal.
Dado un matching M
- un camino alternativo es un camino al cual sus arcos alternativamente pertenecen y no pertenecen al matching.
- un camino aumentante es un camino alternativo que comienza y termina en un vértice libre (unmatched).
Notese que un matching es máximo si, y sólo si no contiene ningún camino aumentante.
[editar] Matchings en grafos bipartidos
Los problemas de matching tienen relación muchas veces con grafos bipartidos. Encontrar un matching máximo bipartido (a menudo llamado cardinalidad máxima de un grafo bipartido) en un grafo bipartido 
es quizás el problema más simple. El algoritmo de los caminos aumentantes lo encuentra por búsqueda de caminos aumentantes por cada 
a 
y añadiéndolo al matching si existe. Como cada camino puede se encontrado en tiempo 
, el costo de tiempo es 
. Todos los arcos con flujo de 
a constituyen un matching máximo. Una mejora sobre esto es el algoritmo de Hopcroft-Karp, de costo de tiempo 
.
En un grafo bipartido ponderado, cada arco tiene asociado un valor. Un matching máximo bipartido ponderado está definido como un matching perfecto donde la suma de los valores de sus arcos en el matching tiene un valor maximal. Si el grafo no es completamente bipartido, los arcos ausentes son introducidos con valor cero. Encontrar tal matching 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 
. El más especializado es el algoritmo Húngaro que resuelve el problema de asignación con costo de tiempo 
.
[editar] Propiedades
- Para un grafo G con n vértices con un vértice aislado el número de matching + número de arcos de covering = n (Tibor Gallai 1959)
- Un grafo con n vértices y un matching perfecto tiene un número de matching igual a n/2
[editar] Véase también
[editar] Referencias
- 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 0262032937. Section 26.3: Maximum bipartite matching, pp.664–669.
- ↑ West, Douglas Brent [1996] (1999). “3”, Introduction to Graph Theory, 2nd edition, Prentice Hall. ISBN 0130144002.
