Изменения

<tex>odd(G-U)</tex> - количество [[Отношение связности, компоненты связности|компонент связности ]] нечетного размера в <tex> G[V - U]</tex>.}}

где <tex>\alpha (G)</tex> - размер [[Теорема о максимальном паросочетании и дополняющих цепях|максимального поросочетания ]] в <tex>G</tex>, а <br>

* <tex>D(G) = \{v \in V |</tex> существует [[максимальное паросочетание|Теорема о максимальном паросочетании и дополняющих цепях]], не покрывающее <tex> v\}</tex>

Достаточно доказать, что <tex>D(G-a) = D(G)</tex>. <br>

Пусть <tex>u \in D(G)</tex>. Тогда существует [[Теорема о максимальном паросочетании и дополняющих цепях|максимальное паросочетание ]] <tex> Mu M_u</tex> графа <tex>G</tex>, не покрывающее <tex>u</tex>. Поскольку любое максимальное паросочетание графа <tex>G</tex> покрывает a, то <tex> \alpha (G - a) = \alpha (G) - 1 </tex> и более того, если <tex> ax \in Mu M_u </tex>, то <tex>Mu _Mu \setminus {ax} </tex> - максимальное паросочетание графа <tex> G - a </tex>, не покрывающее <tex> u </tex>. Таким образом, <tex>D(G - a) \supset D(G) </tex>. <br>

Предположим, что существует максимальное паросочетание <tex>M'</tex> графа<tex> G - a</tex>, не покрывающее вершину <tex>v not \in D(G)</tex>. Пусть <tex> w \in D(G) </tex>- смежная с<tex> a \in A(G)</tex> вершина, а <tex> Mw M_w </tex>- максимальное паросочетание графа <tex> G </tex>, не покрывающее <tex> w </tex>. Так как <tex> v not \in D(G) </tex>, максимальное паросочетание <tex> Mw M_w </tex> покрывает вершину <tex>v</tex>. Рассмотрим граф <tex> H = G(Mw M_w \bigcup M') </tex> - очевидно, он является объединением нескольких путей и чётных циклов. Пусть <tex> U </tex> - компонента связности графа <tex> H </tex>, содержащая <tex>v</tex>. Так как <tex> dH(v) = 1 </tex>, то <tex> P = H(U) </tex> - путь с началом в вершине <tex>v</tex>. В пути <tex>P</tex> чередуются рёбра из <tex> Mw M_w и M' </tex>, причём начинается путь ребром из <tex>Mw M_w </tex> . Так как <tex> dH(a) = 1 </tex>, то вершина a либо не принадлежит пути <tex>P</tex>, либо является её концом (в этом случае последнее ребро пути принадлежит паросочетанию <tex> MwM_w</tex>). Рассмотрим несколько случаев: <br>

Рассмотрим паросочетание <tex>Mv M_v = Mw M_w \oplus E(P)</tex> (симметрическая разность<tex> Mw M_w и E(P)</tex>. то есть, рёбра, входящие ровно в одно из двух множеств).Очевидно, <tex>MvM_v</tex> - максимальное паросочетание графа <tex> G</tex>, не покрывающее <tex> v</tex>, поэтому <tex> v \in D(G)</tex>, противоречие. <br>

'''b.''' Путь <tex>P</tex> кончается ребром из <tex> MwM_w</tex>, вершина a - конец пути <tex>P</tex>. (см.рисунок)<br>Рассмотрим паросочетание <tex>Mv∗ M_v∗ = (Mw M_w \oplus E(P)) \bigcup \{aw\} </tex>. Тогда <tex> Mv∗ M_v∗ </tex> - максимальное паросочетание графа <tex> G </tex>, не покрывающее <tex> v </tex>, поэтому <tex> v \in D(G) </tex>, противоречие.

'''c.''' Путь <tex> P </tex> кончается ребром из <tex> MwM_w, a \in V(P) </tex> (см. рисунок)

Пусть G - граф, <tex>U1U_1,{...},UnU_n</tex> - компоненты связности графа <tex>G(D(G))</tex> , <tex>Di D_i = G(UiU_i), C = G(C(G))</tex>. тогда:

2) Графы <tex>D1D_1,{...},DnD_n</tex> - фактор-критические. <br>3) Любое максимальное паросочетание <tex>M</tex> графа <tex>G</tex> состоит из совершенного паросочетания графа <tex>C</tex>, почти совершенных паросочетаний графов <tex>D1D_1,{...},DnD_n</tex> и покрывает все вершины множества <tex>A(G)</tex> рёбрами с концами в различных компонентах связности <tex>U1U_1,{...},UnU_n</tex> <br>

2) Из формулы <tex> \alpha(G - A) = \alpha (G) - |A|</tex> следует, что <tex>U1U_1,{...},UnU_n</tex>- компоненты связности графа <tex>G - A</tex>. Для любой вершины <tex>u \in Ui U_i </tex>существует максимальное паросочетание <tex>MuM_u</tex> графа <tex>G - A</tex>, не содержащее <tex>u</tex>. Так как <tex>UiU_i</tex> - компонента связности графа <tex>G - A</tex>, паросочетание <tex>MuM_u</tex> содержит максимальное паросочетание графа <tex>DiD_i</tex> (разумеется, не покрывающее вершину <tex>u</tex>). Следовательно, <tex> \alpha (DiD_i) = \alpha (Di D_i - 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>U1U_1,{...},UnU_n</tex>.