Разложение Галлаи-Эдмондса

Разбиение вершин графа, дающее информацию о структуре максимальных паросочетаний

Иллюстрация трех множеств в разложении Галлаи–Эдмондса примера графа.

В теории графов разложение Галлаи –Эдмондса представляет собой разбиение вершин графа на три подмножества, которое предоставляет информацию о структуре максимальных паросочетаний в графе. Тибор Галлаи ^{[1] [2]} и Джек Эдмондс ^[3] независимо друг от друга открыли его и доказали его ключевые свойства.

Разложение графа Галлаи–Эдмондса можно найти с помощью алгоритма Blow .

Характеристики

Для данного графа его разложение Галлаи–Эдмондса состоит из трех непересекающихся множеств вершин, , и , объединение которых равно : множество всех вершин . Во-первых, вершины из делятся на существенные вершины (вершины, которые покрыты каждым максимальным паросочетанием в ) и несущественные вершины (вершины, которые остались непокрытыми хотя бы одним максимальным паросочетанием в ). Множество определяется как содержащее все несущественные вершины. Существенные вершины делятся на и : множество определяется как содержащее все существенные вершины, смежные хотя бы с одной вершиной из , и определяется как содержащее все существенные вершины, не смежные ни с одной вершиной из . ^[4] ${\displaystyle G}$ ${\displaystyle A(G)}$ ${\displaystyle C(G)}$ ${\displaystyle D(G)}$ ${\displaystyle V(G)}$ ${\displaystyle G}$ ${\displaystyle G}$ ${\displaystyle G}$ ${\displaystyle G}$ ${\displaystyle D(G)}$ ${\displaystyle A(G)}$ ${\displaystyle C(G)}$ ${\displaystyle A(G)}$ ${\displaystyle D(G)}$ ${\displaystyle C(G)}$ ${\displaystyle D(G)}$

Обычно множества , и с подграфами, индуцированными этими множествами, отождествляют. Например, мы говорим «компоненты », имея в виду связные компоненты подграфа, индуцированного . ${\displaystyle A(G)}$ ${\displaystyle C(G)}$ ${\displaystyle D(G)}$ ${\displaystyle D(G)}$ ${\displaystyle D(G)}$

Разложение Галлаи–Эдмондса имеет следующие свойства: ^[5]

1. Компоненты являются факторно-критическими графами : каждый компонент имеет нечетное число вершин, и когда любая из этих вершин исключена, то существует идеальное соответствие оставшихся вершин. В частности, каждый компонент имеет почти идеальное соответствие: соответствие, которое охватывает все вершины, кроме одной. ${\displaystyle D(G)}$
2. Подграф, индуцированный , имеет идеальное паросочетание. ${\displaystyle C(G)}$
3. Каждое непустое подмножество имеет соседей по крайней мере в компонентах . ${\displaystyle X\subseteq A(G)}$ ${\displaystyle |X|+1}$ ${\displaystyle D(G)}$
4. Каждое максимальное паросочетание в имеет следующую структуру: оно состоит из почти идеального паросочетания каждого компонента из , идеального паросочетания из , и ребер из всех вершин из в различные компоненты из . ${\displaystyle G}$ ${\displaystyle D(G)}$ ${\displaystyle C(G)}$ ${\displaystyle A(G)}$ ${\displaystyle D(G)}$
5. Если имеет компоненты, то число ребер в любом максимальном паросочетании равно . ${\displaystyle D(G)}$ ${\displaystyle k}$ ${\displaystyle G}$ ${\displaystyle {\frac {1}{2}}(|V(G)|-k+|A(G)|)}$

Строительство

Разложение Галлаи–Эдмондса графа можно найти, несколько неэффективно, начав с любого алгоритма поиска максимального паросочетания. Из определения вершина находится в тогда и только тогда, когда (граф, полученный из удалением ) имеет максимальное паросочетание того же размера, что и . Поэтому мы можем идентифицировать, вычислив максимальное паросочетание в и в для каждой вершины . Дополнение к можно разбить на и непосредственно из определения. ${\displaystyle G}$ ${\displaystyle v}$ ${\displaystyle D(G)}$ ${\displaystyle G-v}$ ${\displaystyle G}$ ${\displaystyle v}$ ${\displaystyle G}$ ${\displaystyle D(G)}$ ${\displaystyle G}$ ${\displaystyle G-v}$ ${\displaystyle v}$ ${\displaystyle D(G)}$ ${\displaystyle A(G)}$ ${\displaystyle C(G)}$

Одним из частных методов поиска максимального паросочетания в графе является алгоритм цветения Эдмондса , и обработка, выполняемая этим алгоритмом, позволяет нам напрямую находить разложение Галлаи–Эдмондса.

Чтобы найти максимальное соответствие в графе , алгоритм цветения начинает с небольшого соответствия и проходит через несколько итераций, в которых он увеличивает размер соответствия на одно ребро. Мы можем найти разложение Галлаи–Эдмондса из работы алгоритма цветения в последней итерации: работа, выполненная, когда у него есть максимальное соответствие , которое он не может сделать больше. ${\displaystyle G}$ ${\displaystyle M}$

В каждой итерации алгоритм цветения переходит от к меньшим графам, сжимая подграфы, называемые «цветениями», до отдельных вершин. Когда это делается в последней итерации, цветения имеют особое свойство: ${\displaystyle G}$

1. Все вершины цветка являются несущественными вершинами большего графа.
2. Вершина, образованная сжатием цветка, является несущественной вершиной меньшего графа.

Первое свойство следует из алгоритма: каждая вершина цветка является конечной точкой чередующегося пути , который начинается в вершине, не покрытой сопоставлением. Второе свойство следует из первого с помощью леммы ниже: ^[6]

Пусть будет графом, паросочетанием в , и пусть будет циклом длины , который содержит ребра и является вершинно-непересекающимся с остальной частью . Построим новый граф из , сжимая его до одной вершины. Тогда является максимальным паросочетанием в , если и только если является максимальным паросочетанием в . ${\displaystyle G}$ ${\displaystyle M}$ ${\displaystyle G}$ ${\displaystyle Z}$ ${\displaystyle 2k+1}$ ${\displaystyle k}$ ${\displaystyle M}$ ${\displaystyle M}$ ${\displaystyle G'}$ ${\displaystyle G}$ ${\displaystyle Z}$ ${\displaystyle M'=M-E(Z)}$ ${\displaystyle G'}$ ${\displaystyle M}$ ${\displaystyle G}$

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

После того, как каждый цветок был сжат алгоритмом, результатом является меньший граф , максимальное соответствие в того же размера, что и , и чередующийся лес в относительно . В разложение Галлаи–Эдмондса имеет краткое описание. Вершины в классифицируются на внутренние вершины (вершины на нечетном расстоянии в от корня) и внешние вершины (вершины на четном расстоянии в от корня); — это в точности множество внутренних вершин, а — это в точности множество внешних вершин. Вершины , которые не находятся в форме . ^[7] ${\displaystyle G'}$ ${\displaystyle M'}$ ${\displaystyle G'}$ ${\displaystyle M}$ ${\displaystyle F'}$ ${\displaystyle G'}$ ${\displaystyle M'}$ ${\displaystyle G'}$ ${\displaystyle F'}$ ${\displaystyle F'}$ ${\displaystyle F'}$ ${\displaystyle A(G')}$ ${\displaystyle D(G')}$ ${\displaystyle G'}$ ${\displaystyle F'}$ ${\displaystyle C(G')}$

Стягивание цветков сохраняет множество несущественных вершин; поэтому может быть найдено из , взяв все вершины , которые были стянуты как часть цветка, а также все вершины в . Вершины в и никогда не стягиваются; и . ${\displaystyle D(G)}$ ${\displaystyle D(G')}$ ${\displaystyle G}$ ${\displaystyle D(G')}$ ${\displaystyle A(G)}$ ${\displaystyle C(G)}$ ${\displaystyle A(G)=A(G')}$ ${\displaystyle C(G)=C(G')}$

Обобщения

Разложение Галлаи–Эдмондса является обобщением разложения Дульмейджа–Мендельсона с двудольных графов на общие графы. ^[8]

Расширение теоремы разложения Галлаи–Эдмондса на паросочетания с несколькими ребрами приведено в работе Катажины Палух «Capacitated Rank-Maximal Matchings» ^{[9] .}

Ссылки

1. Галлай, Тибор (1963), «Критище графен II», Венгерский Туд. Акад. Мат. Кутато Международный. Козл. , 8 : 373–395
2. Галлай, Тибор (1964), «Максимальная система unabhängiger Kanten», Magyar Tud. Акад. Мат. Кутато Международный. Козл. , 9 : 401–413
3. Эдмондс, Джек (1965), «Пути, деревья и цветы», Канадский журнал математики , 17 : 449–467, doi : 10.4153/CJM-1965-045-4 , S2CID  18909734
4. Ловас, Ласло ; Пламмер, Майкл Д. (1986), Теория соответствия (1-е изд.), Северная Голландия, раздел 3.2, ISBN 978-0-8218-4759-6
5. Теорема 3.2.1 в книге Ловаса и Пламмера, с. 94
6. Лемма 9.1.1 в книге Ловаса и Пламмера, с. 358
7. Упражнение 9.1.2 в книге Ловаса и Пламмера, стр. 360
8. Сабо, Ясинт; Лёбль, Мартин; Яната, Марек (14 февраля 2005 г.), «Разложение Эдмондса–Галлаи для задачи упаковки k -кусков», The Electronic Journal of Combinatorics , 12 , doi : 10.37236/1905 , S2CID  11992200
9. Палух, Катажина (22 мая 2013 г.), «Capacitated Rank-Maximal Matchings», Алгоритмы и сложность , Lecture Notes in Computer Science, т. 7878, Springer, Берлин, Гейдельберг, стр. 324–335, doi :10.1007/978-3-642-38233-8_27, ISBN 978-3-642-38232-1