Декомпозиция Далмейджа-Мендельсона

Декомпозиция Далмейджа-Мендельсона в теории графов представляет собой разделение вершин двудольного графа на подмножества со свойством, что 2 смежные вершины принадлежат к одному и тому же множеству тогда и только тогда, когда они вместе друг с другом в паросочетании графов. Декомпозиция была названа в честь А. Л. Далмейджа и Натана Мендельсона, которые опубликовали ее в 1958 году.

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

• Вершины в D ∩ U и его соседними вершинами.
• Вершины в D ∩ V и его соседними вершинами.
• Остальные вершины.

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

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

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

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

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

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

1. Frank Harary; Michael D.Plummer (1967), "On the core of a graph", Proceedings of the London Mathematical Society, Third Series, 17: 305–314, doi:10.1112/plms/s3-17.2.305, MR 0209184.
2. Dulmage, A. L. & Mendelsohn, N.S (1958). "Coverings of bipartite graphs". Can. J. Math. 10: 517–534. doi:10.4153/cjm-1958-052-0. The original Dulmage–Mendelsohn paper

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