37
правок
Изменения
м
<tex>\mathrm{odd}(G)</tex> - количество [[Отношение связности, компоненты связности#def2|компонент связности]] нечетного размера в <tex> G</tex>.}} {{Определение |definition='''Дефицитом''' графа <tex>G </tex> мы будем называть величину: <br>
[[Файл: Gallai-lema-a.png|150px|thumb|right|случай '''а''']]
[[Файл: Gallai-lema-b.png|150px|thumb|right|случай '''b''']]'''b.''' Путь <tex>P</tex> кончается ребром из <tex> M_w</tex>, вершина <tex>a </tex> {{--- }} конец пути <tex>P</tex>. (см.рисунок)<br>Рассмотрим паросочетание <tex>M_v∗ = (M_w \oplus E(P)) \bigcup \{aw\} </tex>. Тогда <tex> M_v∗ </tex> {{- --}} максимальное паросочетание графа <tex> G </tex>, не покрывающее <tex> v </tex>, поэтому <tex> v \in D(G) </tex>, противоречие.
[[Файл: Gallai-lema-с.png|150px|thumb|right|случай '''c''']]
правки
В этом направлении много усилий приложили Вильям Томас '''Татт''' (''William Thomas Tutte''), Клауд '''Берж'''(''Claude Brege''), Джек '''Эдмондс'''(''Jack Edmonds'') и Тибор '''Галлаи'''(''Tibor Gallai'').
{{Определение
|definition=
<tex>\mathrm{def}(G) = |V| - 2\alpha (G)</tex>, <br>
где <tex>\alpha (G)</tex> - размер [[Теорема о максимальном паросочетании и дополняющих цепях#theorem1|максимального паросочетания]] в <tex>G</tex>, а <br>
<tex>V(G)</tex> - множество вершин графа <tex>G</tex>
}}
{{Теорема
|about=Бержа
|statement=
Для любого графа <tex>G </tex> выполняется:<br>
<tex>\mathrm{def}(G) = \max\limits_{S \subset V(G)} \{\mathrm{odd}(G - S) - |S|\}.</tex>
}}
<tex>\mathrm{ \alpha} (G) = \min\limits_{U \in V} \{1/2(|V|-|U|-\mathrm{odd}(G-U)\} </tex>
}}
{{Определение
Множество <tex>S \subset V (G)</tex>, для которого <tex>\mathrm{odd}(G - S) - |S| = \mathrm{def}(G) </tex>, называется '''барьером'''.
}}
{{Определение
|definition=Пусть <tex>X \subset V </tex>. '''Множeство соседей''' (англ. ''neighbors'')<tex>X</tex> определим формулой: <tex>N(X)= \{ y \in V: (x,y) \in E \}</tex>
}}
==Структурная теорема Эдмондса-Галлаи==
{{Определение
|definition=
# <tex>D(G) = \{v \in V |</tex> существует [[Теорема о максимальном паросочетании и дополняющих цепях|максимальное паросочетание]], не покрывающее <tex> v\}</tex>
# <tex>A(G) = N(D(G)) \setminus D(G)</tex>
# <tex>C(G) = V \setminus( D(G) \bigcup A(G) )</tex># <tex> \alpha (G) </tex> {{- --}} размер максимального паросочетания в <tex>G</tex> (англ. ''maximum matching in G'')
}}
{{Определение
|definition=
Граф <tex>G</tex> называется '''фактор-критическим''' (англ. ''factor-critical graph''), если для любой вершины <tex>v \in G</tex> в графе <tex>G \setminus {v}</tex> существует [[Теорема Холла#def1|совершенное паросочетание]].
}}
{{Теорема
|about=Галлаи
|statement=
<tex>G</tex> {{- --}} фактор-критический граф <tex> \Leftrightarrow </tex> <br><tex>G</tex> {{--- }} связен и для любой вершины <tex>u \in V(G) </tex> выполняется равенство <tex> \alpha (G - u) = \alpha (G)</tex>.
}}
{{Лемма
|proof=
Достаточно доказать, что <tex>D(G - a) = D(G)</tex>. <br>
[[Файл: Gallai-lema-a.png|150px|thumb|right|Случай '''а''']]
[[Файл: Gallai-lema-b.png|150px|thumb|right|Случай '''b''']]
[[Файл: Gallai-lema-с.png|150px|thumb|right|Случай '''c''']]
# покажем, что <tex>D(G - a) \supset D(G)</tex> : <br>
#:Пусть <tex>u \in D(G)</tex>. Тогда существует [[Теорема о максимальном паросочетании и дополняющих цепях|максимальное паросочетание]] <tex>M_u</tex> графа <tex>G</tex>, не покрывающее <tex>u</tex>. Поскольку любое максимальное паросочетание графа <tex>G</tex> покрывает <tex>a</tex>, то <tex> \alpha (G - a) = \alpha (G) - 1 </tex> и более того, если, для некоторой вершины <tex>x \in D(G)</tex>, <tex>ax \in M_u</tex>, то <tex>M_u \setminus {ax} </tex> {{--- }} максимальное паросочетание графа <tex> G - a </tex>, не покрывающее <tex> u </tex>. Таким образом, <tex>D(G - a) \supset D(G) </tex>. <br>
#покажем, что <tex> D(G - a) \subset D(G)</tex>: <br>
Предположим, что существует максимальное паросочетание <tex>M'</tex> графа <tex> G - a</tex>, не покрывающее вершину <tex>v</tex> <tex> \notin D(G)</tex>. Пусть <tex> w \in D(G) </tex> {{- --}} смежная с <tex> a \in A(G)</tex> вершина, а <tex> M_w </tex>{{- --}} максимальное паросочетание графа <tex> G </tex>, не покрывающее <tex> w </tex>. Так как <tex>v</tex> <tex> \notin D(G) </tex>, максимальное паросочетание <tex> M_w </tex> покрывает вершину <tex>v</tex>. Рассмотрим граф <tex> H = G(M_w \bigcup M') </tex> {{--- }} очевидно, он является объединением нескольких путей и чётных циклов. Пусть <tex> U </tex> {{- --}} компонента связности графа <tex> H </tex>, содержащая <tex>v</tex>. Так как <tex> deg_H(v) = 1 </tex>(степень вершины), то <tex> P = H(U) </tex> {{--- }} путь с началом в вершине <tex>v</tex>. В пути <tex>P</tex> чередуются рёбра из <tex> M_w</tex> и <tex>M' </tex>, причём начинается путь ребром из <tex>M_w </tex>. Так как <tex> deg_H(a) = 1 </tex>, то вершина a либо не принадлежит пути <tex>P</tex>, либо является её концом (в этом случае последнее ребро пути принадлежит паросочетанию <tex> M_w</tex>). Рассмотрим несколько случаев: <br>
'''a.''' Путь <tex>P</tex> кончается ребром из <tex> M'</tex> (см. рисунок)<br>
Рассмотрим паросочетание <tex>M_v = M_w \oplus E(P)</tex> (симметрическая разность
<tex> M_w</tex> и <tex>E(P)</tex>. то есть, рёбра, входящие ровно в одно из двух множеств).
Очевидно, <tex>M_v</tex> {{- --}} максимальное паросочетание графа <tex>G</tex>, не покрывающее <tex>v</tex>, поэтому <tex> v \in D(G)</tex>, противоречие. <br>
'''c.''' Путь <tex> P </tex> кончается ребром из <tex> M_w, a \in V(P) </tex> (см. рисунок)
Рассмотрим паросочетание <tex> M'' = M \oplus E(P) </tex>. Тогда <tex> |M''| = |M'| + 1 </tex>, причём <tex>M'' \subset E(G - a)</tex>. Противоречие с максимальностью паросочетания <tex>M'</tex>.
Таким образом, наше предположение невозможно и <tex>D(G - a) \subset D(G)</tex>.
А значит, <tex>D(G - a) = D(G)</tex>.
}}
|about = Галлаи, Эдмондс
|statement=
Пусть G {{--- }} граф, <tex>U_1,{...},U_n</tex> {{--- }} компоненты связности графа <tex>G(D(G))</tex>, <tex>D_i = G(U_i), C = G(C(G))</tex>. тогда:
# Граф <tex>C</tex> имеет совершенное паросочетание.<br>
# Графы <tex>D_1,{...},D_n</tex> {{- --}} фактор-критические. <br>
# Любое максимальное паросочетание <tex>M</tex> графа <tex>G</tex> состоит из совершенного паросочетания графа <tex>C</tex>, почти совершенных паросочетаний графов <tex>D_1,{...},D_n</tex> и покрывает все вершины множества <tex>A(G)</tex> рёбрами с концами в различных компонентах связности <tex>U_1,{...},U_n</tex> <br>
# <tex>\mathrm{def}(G) = n - |A(G)|, 2\mathrm{\alpha}(G) = v(G) + |A(G)| - n</tex>.
|proof=
[[Файл: Edmonds-Gallai_2.png|300px|thumb|right|Пример]]
# Последовательно удаляя вершины множества<tex> A = A(G)</tex>, по лемме о стабильности мы получим:
#:* <tex>D(G - A) = D(G),</tex>
#:* <tex>A(G - A) = \O, </tex>
#:Это означает, что не существует рёбер, соединяющих вершины из <tex>C(G - A)</tex> и <tex>D(G - A)</tex>. Каждое максимальное паросочетание <tex>M'</tex> графа <tex>G - A</tex> покрывает все вершины множества <tex>C(G)</tex>, поэтому <tex>M'</tex> содержит совершенное паросочетание графа <tex>C</tex>. Тем самым, мы доказали пункт 1).
#:
# Из формулы <tex> \alpha(G - A) = \alpha (G) - |A|</tex> следует, что <tex>U_1,{...},U_n</tex>{{- --}} компоненты связности графа <tex>G - A</tex>. Для любой вершины <tex>u \in U_i</tex> существует максимальное паросочетание <tex>M_u</tex> графа <tex>G - A</tex>, не содержащее <tex>u</tex>. Так как <tex>U_i</tex> {{--- }} компонента связности графа <tex>G - A</tex>, паросочетание <tex>M_u</tex> содержит максимальное паросочетание графа <tex>D_i</tex> (разумеется, не покрывающее вершину <tex>u</tex>). Следовательно, <tex> \alpha (D_i) = \alpha (D_i - u) </tex> и по теореме Галлаи(выше) мы получаем, что граф <tex>D_i</tex> {{--- }} фактор-критический.
#:
# Пусть <tex>M</tex> {{- --}} максимальное паросочетание графа <tex>G</tex>, а <tex>M'</tex> получено из <tex>M</tex> удалением всех рёбер, инцидентных вершинам множества <tex>A</tex>. Тогда <tex>|M'| \ge |M| - |A|</tex> и по формуле <tex> \alpha (G - A) = \alpha (G) - |A|</tex> понятно, что <tex>M'</tex> {{--- }} максимальное паросочетание графа <tex>G - A</tex>. Более того, из <tex> \alpha (G - A) = \alpha (G) - |A|</tex> следует <tex>|M'| = |M| - |A|</tex>, а значит, все вершины множества <tex>A</tex> покрыты в <tex>M</tex> различными рёбрами. Так как <tex>M'</tex> {{--- }} максимальное паросочетание графа <tex>G - A</tex>, то по пунктам 1) и 2) очевидно, что <tex>M'</tex> содержит совершенное паросочетание графа <tex>C</tex> и почти совершенные паросочетания фактор-критических графов <tex>D_1,{...},D_n</tex>. Значит, рёбра паросочетания <tex>M</tex> соединяют вершины <tex>A</tex> с непокрытыми <tex>M'</tex> вершинами различных компонент связности из <tex>U_1,{...},U_n</tex>.
# Из пункта 3) сразу же следуют оба равенства пункта 4).
}}
|about=следствие из теоремы
|statement=
<tex>A(G)</tex> {{- --}} '''барьер''' графа <tex>G</tex>
}}
== Источники ==
