En teoría de grafos , la descomposición de Dulmage-Mendelsohn es una partición de los vértices de un grafo bipartito en subconjuntos, con la propiedad de que dos vértices adyacentes pertenecen al mismo subconjunto si y solo si están emparejados entre sí en una correspondencia perfecta del grafo. Recibe su nombre en honor a AL Dulmage y Nathan Mendelsohn , quienes la publicaron en 1958. [1] Una generalización para cualquier grafo es la descomposición de Edmonds-Gallai , que utiliza el algoritmo Blossom .
La descomposición de Dulmage-Mendelshon se puede construir de la siguiente manera. [2] (se atribuye a [3] quien a su vez la atribuye a [4] ).
Sea G un grafo bipartito, M un grafo de máxima cardinalidad coincidente en G y V 0 el conjunto de vértices de G que no coinciden con M (los "vértices libres"). Entonces G puede dividirse en tres partes:
A la izquierda se muestra una ilustración. Las líneas en negrita son los bordes de M. Las líneas débiles son otros bordes de G. Los puntos rojos son los vértices de V 0. Nótese que V 0 está contenido en E , ya que se puede llegar a él desde V 0 por un camino de longitud 0.
Con base en esta descomposición, las aristas en G pueden dividirse en seis partes según sus puntos finales: EU, EE, OO, OU, EO, UU . Esta descomposición tiene las siguientes propiedades: [3]
Sea G = ( X+Y , E ) un grafo bipartito y sea D el conjunto de vértices en G que no coinciden en al menos una coincidencia máxima de G . Entonces D es necesariamente un conjunto independiente . Por lo tanto, G se puede dividir en tres partes:
Cada coincidencia máxima en G consiste en coincidencias en la primera y segunda parte que coinciden con todos los vecinos de D , junto con una coincidencia perfecta de los vértices restantes. Si G tiene una coincidencia perfecta, entonces el tercer conjunto contiene todos los vértices de G.
El tercer conjunto de vértices en la descomposición gruesa (o todos los vértices en un gráfico con una coincidencia perfecta) se puede dividir adicionalmente en subconjuntos mediante los siguientes pasos:
Para ver que esta subdivisión en subconjuntos caracteriza las aristas que pertenecen a emparejamientos perfectos, supongamos que dos vértices x e y en G pertenecen al mismo subconjunto de la descomposición, pero que no están emparejados por el emparejamiento perfecto inicial. Entonces existe un componente fuertemente conectado en H que contiene la arista x,y . Esta arista debe pertenecer a un ciclo simple en H (por la definición de conectividad fuerte) que necesariamente corresponde a un ciclo alternante en G (un ciclo cuyas aristas alternan entre aristas emparejadas y no emparejadas). Este ciclo alternante puede usarse para modificar el emparejamiento perfecto inicial para producir un nuevo emparejamiento que contenga la arista x,y .
Una arista x,y del grafo G pertenece a todos los emparejamientos perfectos de G , si y solo si x e y son los únicos miembros de su conjunto en la descomposición. Tal arista existe si y solo si el número de exclusión de emparejamiento del grafo es uno.
Como otro componente de la descomposición de Dulmage-Mendelsohn, Dulmage y Mendelsohn definieron el núcleo de un gráfico como la unión de sus coincidencias máximas. [5] Sin embargo, este concepto debe distinguirse del núcleo en el sentido de homomorfismos de gráficos y del k -núcleo formado por la eliminación de vértices de bajo grado.
Esta descomposición se ha utilizado para dividir mallas en análisis de elementos finitos y para determinar ecuaciones especificadas, subespecificadas y sobreespecificadas en sistemas de ecuaciones no lineales. También se utilizó para un algoritmo de correspondencia de rango máximo .
En [6] se presenta una descomposición diferente de un grafo bipartito, que es asimétrica: distingue entre los vértices de un lado del grafo y los vértices del otro lado. Se puede utilizar para encontrar una correspondencia sin envidia de máxima cardinalidad en un grafo bipartito no ponderado, así como una correspondencia de máxima cardinalidad con costo mínimo en un grafo bipartito ponderado. [6]