La descomposición de Dalmage-Mendelsohn en la teoría de grafos es la división de los vértices de un grafo bipartito en subconjuntos con la propiedad de que 2 vértices adyacentes pertenecen al mismo conjunto si y solo si están juntos en un grafo coincidente. La descomposición lleva el nombre de A. L. Dalmage y Nathan Mendelsohn , quienes la publicaron en 1958.
Sea G=(U, V, E) un bígrafo y sea D un conjunto no vacío de vértices o nodos en G que no corresponden al menos a una coincidencia mayor de G. Entonces D es necesariamente un conjunto independiente. G se puede dividir en 3 partes:
Cualquier combinación más grande en G consta de combinaciones en la primera y segunda partes que coinciden con todos los vecinos de D, junto con la coincidencia de los vértices restantes.
El tercer conjunto de vértices en la descomposición extendida (o todos los vértices en un gráfico con una coincidencia perfecta) se pueden dividir en subconjuntos de la siguiente manera:
Para ver que este subconjunto caracteriza las aristas que pertenecen a una coincidencia perfecta, suponga que dos vértices u y v en G pertenecen al mismo subconjunto de descomposición, pero aún no se han asignado a la coincidencia perfecta original. Entonces H tiene una componente fuertemente conexa que contiene la arista uv. Este borde debe pertenecer a un ciclo simple en H (por la definición de una conexión fuerte) que necesariamente corresponde a un ciclo variable en G (un ciclo cuyos bordes alternan entre bordes coincidentes y no coincidentes). Este bucle intercalado se puede utilizar para modificar la combinación perfecta inicial para producir una nueva combinación que contenga bordes uv.
Una arista uv de un grafo G pertenece a todos los emparejamientos perfectos de G si y solo si u y v son los únicos miembros de su conjunto en la descomposición. Tal borde existe si y solo si el gráfico correspondiente a la excepción es igual a uno.
Esta descomposición se utiliza para dividir redes, en análisis de elementos finitos y para determinar ecuaciones específicas dadas en sistemas de ecuaciones no lineales.