Декомпозиция Далмейджа-Мендельсона (:ytkbhk[nenx :glbyw;'g-Byu;yl,vkug)
Декомпозиция Далмейджа-Мендельсона в теории графов представляет собой разделение вершин двудольного графа на подмножества со свойством, что 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 являются единственными членами своего множества в декомпозиции. Такое ребро существует тогда и только тогда, когда соответствующий исключению граф равен единице.
Примечания
[править | править код]Эта декомпозиция используется для деления решеток, при анализе методом конечных элементов и для определения заданных, конкретных уравнений в системах нелинейных уравнений.
Литература
[править | править код]- 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.
- 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