Разложение Дульмаджа – Мендельсона. - Dulmage–Mendelsohn decomposition

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

Грубое разложение

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

  • Вершины в D ∩ Икс и их соседи;
  • Вершины в D ∩ Y и их соседи;
  • Остальные вершины.

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

Альтернативное грубое разложение

Альтернативное определение грубого разложения представлено в [1] (приписывается [2] кто, в свою очередь, приписывает это [3]).

Позволять грамм - двудольный граф, M максимальное соответствие в грамм, и V0 множество вершин грамм непревзойденный M («свободные вершины»). потом грамм можно разделить на три части:

Разложение E-O-U
  • E - в четное вершины - вершины достижимые из V0 по M-опеременный путь одинаковой длины.
  • О - в странный вершины - вершины достижимые из V0 по M- чередующийся путь нечетной длины.
  • U - в недоступен vertices - вершины, недоступные из V0 по M- альтернативный путь.

Иллюстрация показана слева. Жирные линии - края M. Слабые линии - это другие края грамм. Красные точки - это вершины, которым нет равных. M.

На основе этого разложения ребра в G можно разделить на шесть частей в соответствии с их конечными точками: E-U, E-E, O-O, O-U, E-O, U-U. Это разложение обладает следующими свойствами: [2]

  1. Наборы E, О, U попарно не пересекаются.
  2. Наборы E, О, U не зависят от максимального соответствия M (т.е. любое сопоставление максимума определяет точно такое же разложение).
  3. G содержит только O-O, O-U, E-O и U-U края.
  4. Любое максимальное совпадение в грамм содержит только E-O и U-U края.
  5. Любое максимальное совпадение в грамм насыщает все вершины в О и все вершины в U.
  6. Размер максимального согласования в G равен |О| + |U| / 2.

Тонкое разложение

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

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

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

Край х, у графика грамм принадлежит ко всем идеальным сочетаниям грамм, если и только если Икс и у являются единственными членами своего множества в разложении. Такое ребро существует тогда и только тогда, когда соответствие преклюзии номер графа - один.

Основной

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

Приложения

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

Рекомендации

  1. ^ (PDF) http://www.cse.iitm.ac.in/~meghana/matchings/bip-decomp.pdf. Отсутствует или пусто | название = (помощь)
  2. ^ а б Ирвинг, Роберт В .; Кавита, Теликепалли; Мельхорн, Курт; Михаил, Димитриос; Палуч, Катажина Е. (01.10.2006). «Соответствия с максимальным рангом». ACM-транзакции на алгоритмах. 2 (4): 602–610. Дои:10.1145/1198513.1198520.
  3. ^ Pulleyblank, W.R. (1995). «Соответствия и расширения». Справочник по комбинаторике. Амстердам, Северная Голландия: Elsevier Science. С. 179–232.
  4. ^ Харари, Фрэнк; Пламмер, Майкл Д. (1967), «О сердцевине графа», Труды Лондонского математического общества, Третья серия, 17: 305–314, Дои:10.1112 / плмс / с3-17.2.305, МИСТЕР  0209184.

внешняя ссылка

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