497
правок
Изменения
→Структурная теорема Эдмондса-Галлаи
2) Из формулы <tex> \alpha(G - A) = \alpha (G) - |A|</tex> следует, что <tex>U_1,{...},U_n</tex>- компоненты связности графа <tex>G - A</tex>. Для любой вершины <tex>u \in U_i</tex> существует максимальное паросочетание <tex>M_u</tex> графа <tex>G - A</tex>, не содержащее <tex>u</tex>. Так как <tex>U_i</tex> - компонента связности графа <tex>G - A</tex>, паросочетание <tex>M_u</tex> содержит максимальное паросочетание графа <tex>D_i</tex> (разумеется, не покрывающее вершину <tex>u</tex>). Следовательно, <tex> \alpha (D_i) = \alpha (D_i - u) </tex> и по теореме Галлаи(выше) мы получаем, что граф <tex>D_i</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>D1D_1,{...},DnD_n</tex>. Значит, рёбра паросочетания <tex>M</tex> соединяют вершины <tex>A</tex> с непокрытыми <tex>M'</tex> вершинами различных компонент связности из <tex>U_1,{...},U_n</tex>.
4) Из пункта 3) сразу же следуют оба равенства пункта 4).
