Изменения
Нет описания правки
В этом направлении много усилий приложили Вильям Томас '''Татт''' (''William Thomas Tutte''), Клауд Клод '''Берж''' (''Claude BregeBerge''), Джек '''Эдмондс''' (''Jack Edmonds'') и Тибор '''Галлаи''' (''Tibor Gallai'').
{{Определение
|id = deficit
|definition=
'''Дефицитом''' (англ. ''deficit'') графа <tex>G</tex> мы будем называть величину: <br>
{{Теорема
|id = theorem_Tatt_Berge
|about=Татта-Бержа
|statement=
|neat = 1
|definition=
# <tex>D(G) = \{v \in V \mid </tex> существует [[Теорема о максимальном паросочетании и дополняющих цепях|максимальное паросочетание]], не покрывающее <tex> v\}</tex>
# <tex>A(G) = N(D(G)) \setminus D(G)</tex>
{{Теорема
|id = theorem_Gallai
|about=Галлаи
|statement=
{{Лемма
|id = stability_lemma
|about= Галлаи, о стабильности (англ. ''stability lemma'')
|statement=
# <tex> \alpha (G - a) = \alpha (G) - 1.</tex>
|proof=
[[Файл: Gallai-lema-a.png|150px|thumb|right|Случай '''а''']]
[[Файл: Gallai-lema-b.png|150px|thumb|right|Случай '''b''']]
Таким образом, наше предположение невозможно и <tex>D(G - a) \subset D(G)</tex>.
А значит, <tex>D(G - a) = D(G)</tex>.
Так как <tex>D(G - a) = D(G)</tex>, то все вершины, которые были соседями <tex>D(G)</tex>, таковыми и остались. Однако, по условию <tex> a \in A(G)</tex>, значит <tex>A(G - a) = A(G) \setminus \{a\}</tex>.
Так же заметим, что <tex>C(G - a) = V(G - a) \setminus (D(G - a) \cup A(G - a)) = V(G - a) \setminus (D(G) \cup (A(G) \setminus \{a\}))</tex><tex> = V(G) \setminus (D(G) \cup A(G)) = C(G)</tex>
Наконец, так как <tex> a \in A(G)</tex>, то все максимальные паросочетания в <tex>G</tex> включали <tex>a</tex>. Следовательно, <tex>\alpha (G - a) < \alpha (G)</tex>. Заметим, что, взяв любое максимальное паросочетания в <tex>G</tex> и удалив ребро инцидентное <tex>a</tex>, мы получим паросочетание <tex>M'</tex>, которое на 1 меньше исходного, при этом <tex>M' \in E(G - a)</tex>. В свою очередь, это самое большое паросочетание, которое мы могли теоретически получить в <tex>G - a</tex>. Следовательно, <tex> \alpha (G - a) = \alpha (G) - 1.</tex>
}}
{{Теорема
|id = theorem_Gallai_Edmonds
|about = Галлаи, Эдмондс
|statement=
|id = barier_struct1
|about = о связи барьера с <tex>D(G)</tex>
|statement= Для любого барьера <tex>B</tex> графа <tex>BG</tex> верно, что <tex>B\cap D(G) = \varnothing</tex>|proof= Рассмотрим <tex>U_{1}, U_{2}, \ldots U_{n}</tex> {{---}} нечётные компоненты связанности <tex>G \setminus B</tex>, <tex>\ M</tex> {{---}} максимальное паросочетание в <tex>G</tex>. <tex>\forall\ U_{i}\ \exists x \in U_{i}: x</tex> не покрыта <tex>\ M</tex> или <tex>xv \in M \land v \in B</tex>. Всего графе не покрыто хотя бы <tex>odd(G\setminus B) - |B|</tex> вершин. Однако , так как <tex>B</tex> {{---}} барьер, непокрыто '''ровно''' столько вершин. Следовательно , любое максимальное паросочетание не покрывает только вершины из <tex>G \setminus B</tex>, а значит каждая вершина барьера покрыта в любом максимальном паросочетании. Отсюда получаем, что ни одна вершина из <tex>D(G)</tex> не могла оказаться в барьере.
}}
|about=Следствие из леммы
|statement=В любом максимальном паросочетании все вершины барьера соединены соединены с вершинами <tex>G \setminus B</tex>
|proof=Так как в барьере для барьера <tex>B</tex> верно, что <tex>odd(G\setminus B) - |B|=def(G) \geqslant 0</tex>, то ровно <tex>|B|</tex> вершин из нечётных компонент <tex>G \setminus B</tex> покрыты рёбрами <tex>xv \in M \land v \in B</tex>
}}
|about = о дополнении барьера
|statement= Пусть <tex>x\in A(G)\cup C(G),\ G'=G\setminus x,\ B'</tex> {{---}} барьер графа <tex>G'</tex>. Тогда <tex>B=B'\cup x</tex> {{---}} барьер графа <tex>G</tex>
|proof= Так как <tex>x \notin D(G)</tex>, то <tex>\forall\ M</tex> {{---}} для любого максимального паросочетания в <tex>G M: x \in M</tex>. Следовательно , <tex>|M'| = |M| - 1</tex>, где <tex>M'</tex> {{---}} максимальное паросочетание в <tex>G'</tex>.
<tex>def(G') = (|V| - 1)- 2 \cdot |M'| = |V| - 2 \cdot |M| + 1 = def(G) + 1</tex>
== См. также ==
* [[Теорема Татта о существовании полного паросочетания]]
* [[Лапы и минимальные по включению барьеры в графе]]
* [[Пересечение всех максимальных по включению барьеров]]
== Источники информации==
