Изменения
Нет описания правки
В этом направлении много усилий приложили Вильям Томас '''Татт''' (''William Thomas Tutte''), Клод '''Берж''' (''Claude Berge''), Джек '''Эдмондс''' (''Jack Edmonds'') и Тибор '''Галлаи''' (''Tibor Gallai'').
{{Определение
|id = deficit
|definition=
'''Дефицитом''' (англ. ''deficit'') графа <tex>G</tex> мы будем называть величину: <br><tex>o\mathrm{def}(G) = |V| -U2\alpha (G)</tex> , <br>где <tex>\alpha (G)</tex> {{- количество компонент связности нечетного размера --}} размер [[Теорема о максимальном паросочетании и дополняющих цепях#theorem1|максимального паросочетания]] в <tex> G[</tex>, а <br><tex>V(G)</tex> {{--U]-}} множество вершин графа <tex>G. </tex>.}}
{{Теорема
|id = Th_Berge|about=Татта-Бержа
|statement=
}}
{{Теорема
|id = theorem_Tatt_Berge
|about=Татта-Бержа
|statement=
Дан граф <tex>G</tex>, размер максимального паросочетания в нем равен:<br>
<tex>\mathrm{\alpha}(G) = \min\limits_{U \in V} \{\dfrac{1}{2}(|V|+|U|-\mathrm{odd}(G - U)\}. </tex>
|proof=
Предположим <tex>G</tex> {{---}} связный, иначе мы можем применить индукцию к компонентам <tex>G</tex>. Приведем доказательство по индукции по числу вершин в графе. <br>
<u> ''База индукции:''</u> <br>
Очевидно, для <tex> n = 1 </tex> утверждение верно. <br>
<u> ''Индукционный переход:''</u> <br>
Рассмотрим два случая:
# <tex>G</tex> {{---}} содержит вершину <tex>v</tex> покрытую всеми максимальными паросочетаниями (например средняя вершина)
#: Тогда <tex> \mathrm{\alpha}(G - v) = \mathrm{\alpha}(G) - 1 </tex>.
#: По индукции, формула Татта-Берджа содержит <tex>G - v</tex> для некоторого множества <tex>U'</tex>. Пусть <tex>U = U' \bigcup v</tex>. Тогда:
#: <tex> \mathrm{\alpha}(G) = \mathrm{\alpha}(G - v) + 1 = \dfrac{1}{2}(|V - v|+|U - v| - \mathrm{odd}(G - v - (U - v))) + 1 = </tex>
#: <tex> = \dfrac{1}{2}(|V| - 1 + |U|- 1 - \mathrm{odd}(G - U)) + 1 = \dfrac{1}{2}(|V|+|U| - \mathrm{odd}(G - U)). </tex>
#:
# Для каждой вершины <tex>v</tex> есть максимальное паросочетание <tex>M</tex> которое не покрывает <tex>v</tex> (например <tex>C_3</tex>)
#:
#: Покажем, что существует паросочетание размера <tex> \dfrac{1}{2}(|V| - 1) </tex>, из которого следует теорема (при <tex> U = \emptyset </tex>).
#: <u> ''От противного:''</u>
#: Предположим что любое максимальная паросочетание <tex> M </tex> не покрывает, по крайней мере, две различные вершины <tex> u </tex> и <tex> v </tex>. Среди всех таких <tex> (M, u, v) </tex> выберем их так, что <tex> \mathrm{d}(u, u) </tex> в <tex> G </tex> {{---}} минимально.
#: Если <tex> \mathrm{d}(u, u) = 1 </tex>, то <tex> u </tex> и <tex> v </tex> являются смежными, и, следовательно, мы можем увеличить <tex> M </tex>, что противоречит его максимальности.
#: Значит <tex> \mathrm{d}(u, u) \geqslant 2 </tex>, и, следовательно, мы можем выбрать промежуточную вершину <tex> t </tex> на пути <tex> u-v </tex> и <tex> N </tex> максимальное паросочетание, такое что симметрическая разность с <tex> M </tex> минимальна. Так как <tex> (M, u, v) </tex> минимально, то <tex> N </tex> должно охватывать <tex> u </tex> и <tex> v </tex> так, что есть другая вершина <tex> x </tex>, покрытая только в <tex> M </tex>.
#: Пусть <tex> y </tex> будет вершиной покрытой с <tex> x </tex> в <tex> M </tex> и заметим <tex> y \neq t </tex> (иначе можно было бы добавить к <tex> N </tex>). Пусть <tex> z </tex> будет вершиной покрытой с <tex> y </tex> в <tex> N </tex> и заметим <tex> z \neq x </tex> (так как <tex> x </tex> не покрыто в <tex> N </tex>). Тогда <tex> N - yz + xy </tex> {{---}} паросочетание, которое имеет с <tex> M </tex> меньшую симметрическую разность, что противоречит выбору <tex> N </tex>.
}}
{{Определение
|id=barrier
|definition=
}}
==Структурная теорема Эдмондса-Галлаи==
{{Определение
|neat = 1
|definition=
}}
{{Определение
|definition=
}}
{{Теорема
|id = theorem_Gallai
|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>.
}}
{{Лемма
|id = stability_lemma|about= Галлаи, о стабильности (англ. ''stability lemma'')
|statement=
|proof=
'''a.''' Путь <tex>P</tex> кончается ребром из <tex> M'</tex> (см. рисунок)<br>
Рассмотрим паросочетание <tex>Mv M_v = Mw M_w \oplus E(P)</tex> (симметрическая разность<tex> Mw M_w</tex> и <tex>E(P)</tex>. то есть, рёбра, входящие ровно в одно из двух множеств).Очевидно, <tex>MvM_v</tex> {{--- }} максимальное паросочетание графа <tex> G</tex>, не покрывающее <tex> v</tex>, поэтому <tex> v \in D(G)</tex>, противоречие. <br>
'''b.''' Путь <tex>P</tex> кончается ребром из <tex> MwM_w</tex>, вершина <tex>a </tex> {{- --}} конец пути <tex>P</tex>. (см.рисунок)<br>Рассмотрим паросочетание <tex>Mv∗ M_v∗ = (Mw M_w \oplus E(P)) \bigcup \{aw\} </tex>. Тогда <tex> Mv∗ M_v∗ </tex> {{- --}} максимальное паросочетание графа <tex> G </tex>, не покрывающее <tex> v </tex>, поэтому <tex> v \in D(G) </tex>, противоречие.
'''c.''' Путь <tex> P </tex> кончается ребром из <tex> MwM_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>.
}}
{{Теорема
|id = theorem_Gallai_Edmonds
|about = Галлаи, Эдмондс
|statement=
Пусть <tex>G</tex> {{---}} граф, <tex>U_1\ldots 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\ldots D_n</tex> {{---}} фактор-критические. <br># Любое максимальное паросочетание <tex>M</tex> графа <tex> G </tex> состоит из совершенного паросочетания графа <tex> C </tex>, почти совершенных паросочетаний графов <tex> D_1\ldots D_n </tex> и покрывает все вершины множества <tex> A(G) </tex> рёбрами с концами в различных компонентах связности <tex> U_1\ldots U_n. </tex> <br># <tex>\mathrm{def}(G) = n - |A(G)|.</tex> <br># <tex>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) = C(G),</tex>#:* <tex>\alpha (G - A) = \alpha (G) - |A|.</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>. Тем самым, мы доказали пункт <tex>1)</tex>.#:# Из формулы <tex> \alpha(G - A) = \alpha (G) - |A|</tex> следует, что <tex>U_1\ldots 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'| \geqslant |M| - |A|</tex> и по формуле <tex> \alpha (G - A) = \alpha (G) - |A|</tex> понятно, что <tex>M'</tex> {{---}} максимальное паросочетание графа <tex> G - A</tex>. Более того, из <tex> \alpha (G - A) = \alpha (VG) - |A|</tex> следует <tex>|M'| = |M| - |A|</tex>, Eа значит, все вершины множества <tex>A</tex> покрыты в <tex>M</tex> различными рёбрами. Так как <tex>M'</tex> {{---}} максимальное паросочетание графа <tex>G - A</tex>, то по пунктам <tex>1)</tex> выполняется:и <tex>2)</tex> очевидно, что <tex>M'</tex> содержит совершенное паросочетание графа <tex>C</tex> и почти совершенные паросочетания фактор-критических графов <tex>D_1\ldots D_n</tex>. Значит, рёбра паросочетания <tex>M</tex> соединяют вершины <tex>A</tex> с непокрытыми <tex>M'</tex> вершинами различных компонент связности из <tex>U_1\ldots U_n</tex>. # Из пункта <tex>3)</tex> сразу же следуют равенства пункта <tex>4)</tex> и <tex>5)</tex>.}}
{{Утверждение|about=следствие из теоремы|statement=<tex>1) U = A(G) </tex> {{-- множество свидетелей Татта-Бержа }} '''барьер''' графа <brtex>G</tex>}} {{Лемма|id = barier_struct1|about = о связи барьера с <tex>2) СD(G) </tex> - объединение всех четных компонент |statement= Для любого барьера <tex>G - A(G)B</tex> графа <tex>G<br/tex>верно, что <tex>3) B\cap D(G) = \varnothing</tex> |proof= Рассмотрим <tex>U_{1}, U_{2}, \ldots U_{n}</tex> {{--- объединение всех нечетных компонент }} нечётные компоненты связанности <tex>G - A(G)\setminus B</tex> <br>, <tex>4)\ M</tex> каждая компонента {{---}} максимальное паросочетание в <tex> G - A(G)</tex> - фактор-критическая |proof= 1) Последовательно удаляя вершины множества. <tex> A = A(G)\forall\ U_{i}\ \exists x \in U_{i}: x</tex>, по лемме о стабильности мы получим:* не покрыта <tex>D(G - A) = D(G),\ M</tex> * или <tex>A(G - A) = xv \in M \land v \O, in B</tex>* . Всего графе не покрыто хотя бы <tex>Codd(G \setminus B) - A) = C(G)|B|</tex> вершин. Однако,так как <tex>B</tex>* {{---}} барьер, непокрыто '''ровно''' столько вершин. Следовательно, любое максимальное паросочетание не покрывает только вершины из <tex>\alpha (G - A) = \alpha setminus B</tex>, а значит каждая вершина барьера покрыта в любом максимальном паросочетании. Отсюда получаем, что ни одна вершина из <tex>D(G) - |A|.</tex>не могла оказаться в барьере.}}
<tex>odd(G - (B'\cup x)) = odd(G' - B') = </tex><tex>|B'| + def(G') = |B'| + 1 + def(G) = |B'\cup x| + def(G)</tex>
Отсюда следует, что <tex>B</tex> {{---}} барьер графа <tex>G</tex>.
}}
{{Теорема
|id=barier_struct3
|about=о структуре барьера
|statement=Любой барьер графа состоит только из вершин <tex>A(G)\cup C(G)</tex>, причём каждая вершина из этого множества входит в какой-то барьер
|proof=По лемме о связи барьера с <tex>D(G)</tex> мы знаем, что в барьере нет вершин вершин из <tex>D(G)</tex>. По лемме о дополнение барьера мы можем взять любую вершину из <tex>A(G)\cup C(G)</tex>, удалить из графа, и с помощью барьера нового графа получить барьер исходного, включающий данную вершину.
}}