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 sólo si están emparejados entre sí en una coincidencia perfecta del grafico. Lleva el nombre de AL Dulmage y Nathan Mendelsohn , quienes lo publicaron en 1958. [1] Una generalización a cualquier gráfico es la descomposición de Edmonds-Gallai , utilizando 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 se lo atribuye a [4] ).
Sea G un gráfico bipartito, M una coincidencia de cardinalidad máxima en G y V 0 el conjunto de vértices de G no coincidentes con M (los "vértices libres"). Entonces G se puede dividir 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 otras aristas de G . Los puntos rojos son los vértices de V 0 . Tenga en cuenta que V 0 está contenido en E , ya que es accesible desde V 0 por un camino de longitud 0.
Según esta descomposición, las aristas en G se pueden dividir 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 gráfico 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 . Entonces 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 de un gráfico con una coincidencia perfecta) también se puede dividir en subconjuntos mediante los siguientes pasos:
Para ver que esta subdivisión en subconjuntos caracteriza las aristas que pertenecen a coincidencias perfectas, supongamos que dos vértices x e y en G pertenecen al mismo subconjunto de la descomposición, pero aún no están emparejados por la coincidencia perfecta inicial. Entonces existe un componente fuertemente conectado en H que contiene el borde x,y . Esta arista debe pertenecer a un ciclo simple en H (según la definición de conectividad fuerte) que necesariamente corresponde a un ciclo alterno en G (un ciclo cuyas aristas alternan entre aristas coincidentes y no coincidentes). Este ciclo alterno se puede utilizar para modificar la coincidencia perfecta inicial para producir una nueva coincidencia que contenga el borde x,y .
Una arista x,y del gráfico G pertenece a todos los emparejamientos perfectos de G , si y sólo si xey son los únicos miembros de su conjunto en la descomposición. Tal borde existe si y sólo si el número de exclusión coincidente del gráfico 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 grafos, 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, infraespecificadas y sobreespecificadas en sistemas de ecuaciones no lineales. También se utilizó para un algoritmo de coincidencia de rango máximo .
En [6] hay una descomposición diferente de un gráfico bipartito, que es asimétrica: distingue entre los vértices en un lado del gráfico y los vértices en el otro lado. Se puede utilizar para encontrar una coincidencia sin envidia de cardinalidad máxima en un gráfico bipartito no ponderado, así como una coincidencia de cardinalidad máxima de costo mínimo en un gráfico bipartito ponderado. [6]