В теории графов разложение Дульмейджа –Мендельсона представляет собой разбиение вершин двудольного графа на подмножества, обладающее свойством, что две смежные вершины принадлежат одному и тому же подмножеству тогда и только тогда, когда они соединены друг с другом в совершенном паросочетании графа. Оно названо в честь AL Dulmage и Nathan Mendelsohn , которые опубликовали его в 1958 году. [1] Обобщением для любого графа является разложение Эдмондса–Галлаи с использованием алгоритма Блоссома .
Разложение Дульмаге-Мендельшона можно построить следующим образом. [2] (оно приписывается [3], который, в свою очередь, приписывает его [4] ).
Пусть G — двудольный граф, M — паросочетание максимальной мощности в G , а V 0 — множество вершин G , не сопоставленных с M («свободные вершины»). Тогда G можно разбить на три части:
Иллюстрация показана слева. Жирные линии — это ребра M . Слабые линии — это другие ребра G . Красные точки — это вершины V 0 . Обратите внимание, что V 0 содержится в E , поскольку до него можно добраться из V 0 по пути длины 0.
На основе этого разложения ребра в G можно разделить на шесть частей в соответствии с их конечными точками: EU, EE, OO, OU, EO, UU . Это разложение имеет следующие свойства: [3]
Пусть G = ( X+Y , E ) — двудольный граф, а D — множество вершин в G , которые не совпадают хотя бы в одном максимальном сочетании G. Тогда D обязательно является независимым множеством . Поэтому G можно разбить на три части:
Каждое максимальное паросочетание в G состоит из паросочетаний в первой и второй части, которые соответствуют всем соседям D , вместе с совершенным паросочетанием оставшихся вершин. Если G имеет совершенное паросочетание, то третий набор содержит все вершины G.
Третий набор вершин в грубой декомпозиции (или все вершины в графе с идеальным паросочетанием) можно дополнительно разбить на подмножества с помощью следующих шагов:
Чтобы увидеть, что это подразделение на подмножества характеризует ребра, которые принадлежат к совершенным паросочетаниям, предположим, что две вершины x и y в G принадлежат к одному и тому же подмножеству разложения, но еще не сопоставлены исходным совершенным паросочетанием. Тогда существует сильно связный компонент в H, содержащий ребро x,y . Это ребро должно принадлежать простому циклу в H (по определению сильной связности), который обязательно соответствует чередующемуся циклу в G (циклу, ребра которого чередуются между сопоставленными и не сопоставленными ребрами). Этот чередующийся цикл может быть использован для изменения исходного совершенного паросочетания с целью создания нового паросочетания, содержащего ребро x,y .
Ребро x,y графа G принадлежит всем совершенным паросочетаниям G , если и только если x и y являются единственными членами своего множества в разложении. Такое ребро существует тогда и только тогда, когда число исключения паросочетания графа равно единице.
В качестве еще одного компонента разложения Дульмейджа–Мендельсона Дульмейдж и Мендельсон определили ядро графа как объединение его максимальных паросочетаний. [5] Однако это понятие следует отличать от ядра в смысле гомоморфизмов графа и от k -ядра , образованного путем удаления вершин низкой степени.
Это разложение использовалось для разбиения сеток в конечно-элементном анализе и для определения заданных, недоопределенных и переопределенных уравнений в системах нелинейных уравнений. Оно также использовалось для алгоритма для сопоставления максимального ранга .
В [6] есть другое разложение двудольного графа, которое является асимметричным - оно различает вершины на одной стороне графа и вершины на другой стороне. Его можно использовать для поиска паросочетания максимальной мощности без зависти в невзвешенном двудольном графе, а также паросочетания максимальной мощности с минимальной стоимостью во взвешенном двудольном графе. [6]