497
правок
Изменения
→Структурная теорема Эдмондса-Галлаи
2) Из формулы <tex> \alpha(G - A) = \alpha (G) - |A|</tex> следует, что <tex>U1,{...},Un</tex>- компоненты связности графа <tex>G - A</tex>. Для любой вершины <tex>u \in Ui </tex>существует максимальное паросочетание <tex>Mu</tex> графа <tex>G - A</tex>, не содержащее <tex>u</tex>. Так как <tex>Ui</tex> - компонента связности графа <tex>G - A</tex>, паросочетание <tex>Mu</tex> содержит максимальное паросочетание графа <tex>Di</tex> (разумеется, не покрывающее вершину <tex>u</tex>). Следовательно, <tex> \alpha (Di) = \alpha (Di - u) </tex> и по теореме Галлаи(выше) мы получаем, что граф <tex>Di</tex> - фактор-критический.
3) Пусть <tex>M</tex> - максимальное паросочетание графа <tex>G</tex>, а <tex>M'</tex> получено из <tex>M</tex> удалением всех рёбер, инцидентных вершинам множества <tex>A</tex>. Тогда <tex>|M'| \ge |M| - |A|</tex> и по формуле <tex> \alpha (G - A) = \alpha (G) - |A|</tex> понятно, что <tex>M'</tex> - максимальное паросочетание графа <tex>G - A</tex>. Более того, из <tex> \alpha (G - A) = \alpha (G) - |A|</tex> следует <tex>|M'| = |M| - |A|</tex>, а значит, все вершины множества <tex>A</tex> покрыты в <tex>M</tex> различными рёбрамию рёбрами. Так как <tex>M'</tex> - максимальное паросочетание графа <tex>G - A</tex>, то по пунктам 1) и 2) очевидно, что <tex>M'</tex> содержит совершенное паросочетание графа <tex>C</tex> и почти совершенные паросочетания фактор-критических графов <tex>D1,{...},Dn</tex>. Значит, рёбра паросочетания <tex>M</tex> соединяют вершины <tex>A</tex> с непокрытыми <tex>M'</tex> вершинами различных компонент связности из <tex>U1,{...},Un</tex>.
4) Из пункта 3) сразу же следуют оба равенства пункта 4).
