89
правок
Изменения
Нет описания правки
Наконец, так как <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>
}}
|about = о связи барьера с <tex>D(G)</tex>
|statement= Для любого барьера <tex>B</tex> графа <tex>G</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>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>
