Декомпозиция Далмейджа-МендельсонаДекомпозиция Далмейджа-Мендельсона в теории графов представляет собой разделение вершин двудольного графа на подмножества со свойством, что 2 смежные вершины принадлежат к одному и тому же множеству тогда и только тогда, когда они вместе друг с другом в паросочетании графов. Декомпозиция была названа в честь А. Л. Далмейджа и Натана Мендельсона, которые опубликовали ее в 1958 году. Расширенная декомпозицияПусть G=(U, V, E) — это биграф и пусть D — непустое множество вершин или узлов в G, которые не соответствуют по меньшей мере одному наибольшему паросочетанию G.Тогда D непременно является независимым множеством Так что G может быть разделен на 3 части:
Любое наибольшее сочетание в G состоит из сочетаний в первой и второй части, которые совпадают со всеми соседями D вместе с паросочетанием остальных вершин. Достоверная декомпозицияТретье множество вершин в расширенной декомпозиции (или всех вершин в графе с совершенным паросочетанием) помимо этого может разбито на подмножества следующим образом:
Чтобы увидеть, что это деление на подмножества характеризует ребра, принадлежащие к совершенному паросочетанию, предположим, что две вершины u и v в G принадлежат одному и тому же подмножеству декомпозиции, но еще не сопоставлены с исходным совершенным паросочетанием. Тогда в H существует компонента сильной связности, содержащая ребро uv. Это ребро должно принадлежать простому циклу в H (по определению сильной связности), который обязательно соответствует переменному циклу в G (цикл, ребра которого чередуются между соответствующими и несоответствующими ребрами). Этот чередующийся цикл может быть использован для изменения начального совершенного паросочетания для получения нового паросочетания, содержащего ребра uv. Ребро uv графа G принадлежит всем совершенным паросочетаниям G тогда и только тогда, когда u и v являются единственными членами своего множества в декомпозиции. Такое ребро существует тогда и только тогда, когда соответствующий исключению граф равен единице. ПримечанияЭта декомпозиция используется для деления решеток, при анализе методом конечных элементов и для определения заданных, конкретных уравнений в системах нелинейных уравнений. Литература
Ссылки |
Portal di Ensiklopedia Dunia