89
правок
Изменения
Нет описания правки
==Структурная теорема Эдмондса-Галлаи==
{{Определение
|neat = 1
|definition=
# <tex>D(G) = \{v \in V \mid </tex> существует [[Теорема о максимальном паросочетании и дополняющих цепях|максимальное паросочетание]], не покрывающее <tex> v\}</tex>
# <tex>A(G) = N(D(G)) \setminus D(G)</tex>
# <tex> \alpha (G) </tex> {{---}} размер максимального паросочетания в <tex> G. </tex>
}}
[[Файл: EG_red.png|300px|thumb|right|Пример. Рёбра из паросочетания выделены красным]]
{{Определение
|definition=
|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 : 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> <tex>odd(G - (B'\cup x)) = odd(G' - B') = </tex><tex>|B'| + def(G') = |B'| + 1 + def(G) = |B'\cup x| + def(G) = |B| + def(G)</tex>
Отсюда следует, что <tex>B</tex> {{---}} барьер графа <tex>G</tex>.
}}
