Изменения

Перейти к: навигация, поиск

Декомпозиция Эдмондса-Галлаи

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

Навигация