Введение

В теории графов, разложение Дюльмажа — Мендельсона — это разбиение вершин двудольного графа на подмножества, обладающее следующим свойством: две смежные вершины принадлежат одному и тому же подмножеству тогда и только тогда, когда они соединены друг с другом в совершенном паросочетании графа. Оно названо в честь А. Л. Дюльмажа и Натана Мендельсона, которые опубликовали его в 1958 году. Обобщением для произвольного графа является разложение Эдмондса — Галлая, использующее алгоритм поиска цветов (Blossom algorithm).

Строительство

Разложение Дулмажа — Мендельсона может быть построено следующим образом. (Оно приписывается [имя], который, в свою очередь, приписывает его [имя]). Пусть G — двудольный граф, M — максимальное по кардинальности паросочетание в G, а V0 — множество вершин графа G, не входящих в паросочетание M (так называемые "свободные вершины"). Тогда граф G можно разбить на три части:

E — чётные вершины — вершины, достижимые из V0 по M-чередующемуся пути чётной длины. O — нечётные вершины — вершины, достижимые из V0 по M-чередующемуся пути нечётной длины. U — недостижимые вершины — вершины, недостижимые из V0 по M-чередующемуся пути. Иллюстрация представлена слева. Жирные линии — рёбра паросочетания M. Тонкие линии — остальные рёбра графа G. Красные точки — вершины множества V0. Обратите внимание, что V0 содержится в E, поскольку оно достижимо из V0 по пути длиной 0. На основе этого разложения рёбра графа G можно разбить на шесть частей в соответствии с их конечными точками: E U, E E, O O, O U, E O, U U. Это разложение обладает следующими свойствами: Однако это понятие следует отличать от ядра в смысле гомоморфизмов графов и от k-ядра, формируемого удалением вершин малой степени.

Приложения

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

Асимметричный вариант

В этом случае существует иное разложение двудольного графа, которое является асимметричным, поскольку оно различает вершины с одной стороны графа и вершины с другой стороны. Его можно использовать для нахождения максимального по размеру совпадения без зависти в невзвешенном двудольном графе, а также минимальной стоимости максимального по размеру совпадения во взвешенном двудольном графе.