Разложение Дульмейджа–Мендельсона

В теории графов разложение Дульмейджа –Мендельсона представляет собой разбиение вершин двудольного графа на подмножества, обладающее свойством, что две смежные вершины принадлежат одному и тому же подмножеству тогда и только тогда, когда они соединены друг с другом в совершенном паросочетании графа. Оно названо в честь AL Dulmage и Nathan Mendelsohn , которые опубликовали его в 1958 году. ^[1] Обобщением для любого графа является разложение Эдмондса–Галлаи с использованием алгоритма Блоссома .

Разложение Дульмаге-Мендельшона можно построить следующим образом. ^[2] (оно приписывается ^[3], который, в свою очередь, приписывает его ^[4] ).

Пусть G — двудольный граф, M — паросочетание максимальной мощности в G , а V ₀ — множество вершин G , не сопоставленных с M («свободные вершины»). Тогда G можно разбить на три части:

• E - четные вершины - вершины, достижимые из V ₀ по M -чередующемуся пути четной длины.
• O - нечетные вершины - вершины, достижимые из V ₀ по M -чередующемуся пути нечетной длины.
• U - недостижимые вершины - вершины, недостижимые из V ₀ по M -чередующемуся пути.

Иллюстрация показана слева. Жирные линии — это ребра M . Слабые линии — это другие ребра G . Красные точки — это вершины V ₀ . Обратите внимание, что V ₀ содержится в E , поскольку до него можно добраться из V ₀ по пути длины 0.

На основе этого разложения ребра в G можно разделить на шесть частей в соответствии с их конечными точками: EU, EE, OO, OU, EO, UU . Это разложение имеет следующие свойства: ^[3]

1. Множества E , O , U попарно не пересекаются. Доказательство : U не пересекается с E и O по определению. Чтобы доказать, что E и O не пересекаются, предположим, что некоторая вершина v имеет как чередующийся путь четной длины к непарной вершине u ₁ , так и чередующийся путь нечетной длины к непарной вершине u ₂ . Тогда конкатенация этих двух путей дает увеличивающийся путь от u ₁ через v к u ₂ . Но это противоречит предположению, что M является паросочетанием максимальной мощности.
2. Множества E , O , U не зависят от паросочетания максимальной мощности M (т.е. любое паросочетание максимальной мощности определяет точно такое же разложение).
3. G содержит только ребра OO, OU, EO и UU .
4. Любое паросочетание максимальной мощности в G содержит только ребра EO и UU .
5. Любое паросочетание максимальной мощности в G насыщает все вершины в O и все вершины в U.
6. Размер паросочетания максимальной мощности в G равен | O | + | U | / 2.
7. Если G имеет совершенное паросочетание, то все вершины G лежат в U.

Пусть G  = ( X+Y , E ) — двудольный граф, а D — множество вершин в G , которые не совпадают хотя бы в одном максимальном сочетании G. Тогда D обязательно является независимым множеством . Поэтому G можно разбить на три части:

1. Вершины в D ∩ X и их соседи;
2. Вершины в D ∩ Y и их соседи;
3. Остальные вершины.

Каждое максимальное паросочетание в G состоит из паросочетаний в первой и второй части, которые соответствуют всем соседям D , вместе с совершенным паросочетанием оставшихся вершин. Если G имеет совершенное паросочетание, то третий набор содержит все вершины G.

Третий набор вершин в грубой декомпозиции (или все вершины в графе с идеальным паросочетанием) можно дополнительно разбить на подмножества с помощью следующих шагов:

• Найдите идеальное паросочетание G.
• Сформируйте ориентированный граф H, вершинами которого являются сопоставленные ребра в G. Для каждого не сопоставленного ребра ( x,y ) в G добавьте направленное ребро в H от сопоставленного ребра x к сопоставленному ребру y .
• Найдите сильносвязные компоненты полученного графа.
• Для каждого компонента H сформируйте подмножество разложения Дульмейджа–Мендельсона, состоящее из вершин в G, которые являются конечными точками ребер в компоненте.

Чтобы увидеть, что это подразделение на подмножества характеризует ребра, которые принадлежат к совершенным паросочетаниям, предположим, что две вершины x и y в G принадлежат к одному и тому же подмножеству разложения, но еще не сопоставлены исходным совершенным паросочетанием. Тогда существует сильно связный компонент в H, содержащий ребро x,y . Это ребро должно принадлежать простому циклу в H (по определению сильной связности), который обязательно соответствует чередующемуся циклу в G (циклу, ребра которого чередуются между сопоставленными и не сопоставленными ребрами). Этот чередующийся цикл может быть использован для изменения исходного совершенного паросочетания с целью создания нового паросочетания, содержащего ребро  x,y .

Ребро x,y графа G принадлежит всем совершенным паросочетаниям G , если и только если x и y являются единственными членами своего множества в разложении. Такое ребро существует тогда и только тогда, когда число исключения паросочетания графа равно единице.

В качестве еще одного компонента разложения Дульмейджа–Мендельсона Дульмейдж и Мендельсон определили ядро ​​графа как объединение его максимальных паросочетаний. ^[5] Однако это понятие следует отличать от ядра в смысле гомоморфизмов графа и от k -ядра , образованного удалением вершин низкой степени.

Это разложение использовалось для разбиения сеток в конечно-элементном анализе и для определения заданных, недоопределенных и переопределенных уравнений в системах нелинейных уравнений. Оно также использовалось для алгоритма для сопоставления максимального ранга .

В ^[6] есть другое разложение двудольного графа, которое является асимметричным - оно различает вершины на одной стороне графа и вершины на другой стороне. Его можно использовать для поиска паросочетания максимальной мощности без зависти в невзвешенном двудольном графе, а также паросочетания максимальной мощности с минимальной стоимостью во взвешенном двудольном графе. ^[6]

• Хорошее объяснение его применения к системам нелинейных уравнений можно найти в этой статье: [1]
• Реализация алгоритма с открытым исходным кодом доступна как часть библиотеки разреженных матриц: SPOOLES
• Графо-теоретические аспекты решения ограничений в проекте SST: [2]