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

18.04.2021

Декомпозиция Далмейджа-Мендельсона в теории графов представляет собой разделение вершин двудольного графа на подмножества со свойством, что 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 являются единственными членами своего множества в декомпозиции. Такое ребро существует тогда и только тогда, когда соответствующий исключению граф равен единице.