89
правок
Изменения
Нет описания правки
|about = о связи барьера с <tex>D(G)</tex>
|statement= Для любого барьера графа <tex>B</tex> верно, что <tex>B\cap D(G) = \empty</tex>
|proof= Рассмотрим <tex>U_{1}, U_{2}, \ldots U_{n}</tex> {{---}} нечётные компоненты связанности <tex>G \backslash 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>M</tex> хотя бы <tex>odd(G\backslash setminus B) - |B|</tex> вершин. Однако так как <tex>B</tex> {{---}} барьер, непокрыто '''ровно''' столько вершин. Следовательно любое максимальное паросочетание не покрывает только вершины из <tex>G \backslash setminus B</tex>, а значит каждая вершина барьера покрыта в любом максимальном паросочетании. Отсюда получаем, что ни одна вершина из <tex>D(G)</tex> не могла оказаться в барьере.
}}
{{Утверждение
|about=Следствие из леммы
|statement=В любом максимальном паросочетании все вершины барьера соединены соединены с вершинами <tex>G \backslash setminus B</tex>|proof=Так в барьере <tex>odd(G\backslash setminus B) - |B|=def(G) \geqslant 0</tex>, то ровно <tex>|B|</tex> вершин из нечётных компонент <tex>G \backslash setminus B</tex> покрыты рёбрами <tex>xv \in M \land v \in B</tex>
}}
{{Лемма
|id = barier_struct2
|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'.\ 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') = |B'| + def(G') = |B'| + 1 + def(G) = |B'\cup x| + def(G) = |B| + def(G)</tex>
Отсюда следует, что <tex>B</tex> {{---}} барьер графа <tex>G</tex>.
}}
== См. также ==
