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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Позволять

G

быть графиком,

M

совпадение в

G

, и пусть

Z

быть циклом длины

2k+1

который содержит

k

края

M

и вершинно не пересекается с остальной частью

M

. Построить новый график

G'

от

G

путем сокращения

Z

в одну вершину. Затем

M'=M-E(Z)

является максимальным совпадением в

G'

тогда и только тогда, когда

M

является максимальным совпадением в

G

.

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

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

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

Обобщения

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

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

Ссылки

^ Галлай, Тибор (1963), «Критище графена II», Magyar Tud. Есть. Мэтт. Исследования Int. , 8 : 373–395
^ Галлай, Тибор (1964), «Максимальные системы независимых ребер», Magyar Tud. Академический мат. Козл. , 9 : 401–413
^ Эдмондс, Джек (1965), «Пути, деревья и цветы», Canadian Journal of Mathematics , 17 : 449–467, doi : 10.4153/CJM-1965-045-4 , S2CID 18909734
^ Ловас, Ласло ; Пламмер, Майкл Д. (1986), Теория соответствия (1-е изд.), Северная Голландия, раздел 3.2, ISBN 978-0-8218-4759-6
^ Теорема 3.2.1 в книге Ловаса и Пламмера, с. 94
^ Лемма 9.1.1 в книге Ловаса и Пламмера, с. 358
^ Упражнение 9.1.2 в книге Ловаса и Пламмера, стр. 360
^ Сабо, Хасинт; Лебл, Мартин; Джаната, Марек (14 февраля 2005 г.), «Разложение Эдмондса – Галлаи для задачи упаковки k -частей», Электронный журнал комбинаторики , 12 , doi : 10.37236/1905 , S2CID 11992200
^ Палух, Катаржина (22 мая 2013 г.), «Сопоставления с максимальным рангом и емкостью», Алгоритмы и сложность , Конспекты лекций по информатике, том. 7878, Springer, Берлин, Гейдельберг, стр. 324–335, doi : 10.1007/978-3-642-38233-8_27 , ISBN 978-3-642-38232-1

[1] Галлай, Тибор (1963), «Критище графена II», Magyar Tud. Есть. Мэтт. Исследования Int. , 8 : 373–395

[2] Галлай, Тибор (1964), «Максимальные системы независимых ребер», Magyar Tud. Академический мат. Козл. , 9 : 401–413

[3] Эдмондс, Джек (1965), «Пути, деревья и цветы», Canadian Journal of Mathematics , 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 -частей», Электронный журнал комбинаторики , 12 , doi : 10.37236/1905 , S2CID 11992200

[9] Палух, Катаржина (22 мая 2013 г.), «Сопоставления с максимальным рангом и емкостью», Алгоритмы и сложность , Конспекты лекций по информатике, том. 7878, Springer, Берлин, Гейдельберг, стр. 324–335, doi : 10.1007/978-3-642-38233-8_27 , ISBN 978-3-642-38232-1

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]

[ 8 ]

[ 9 ]