Изменения

=Структурная теорема Эдмондса-Галлаи=

{{Определение

|definition=

необходимые определения:

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

* <tex>A(G) = N(D(G)) \setminus D(G)</tex>

* <tex> \alpha (G) </tex> - размер максимального паросочетания в <tex>G</tex>

}}

{{Теорема

Предположим, что существует максимальное паросочетание <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 </tex>- максимальное паросочетание графа <tex> G </tex>, не покрывающее <tex> w </tex>. Так как <tex> v not \in D(G) </tex>, максимальное паросочетание <tex> Mw </tex> покрывает вершину <tex>v</tex>. Рассмотрим граф <tex> H = G(Mw \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' </tex>, причём начинается путь ребром из <tex>Mw </tex> . Так как <tex> dH(a) = 1 </tex>, то вершина a либо не принадлежит пути <tex>P</tex>, либо является её концом (в этом случае последнее ребро пути принадлежит паросочетанию <tex> Mw</tex>). Рассмотрим несколько случаев: <br>

'''a.''' Путь <tex>P</tex> кончается ребром из <tex> M'</tex> (см. рисунок)<br>

Рассмотрим паросочетание <tex>Mv = Mw \oplus E(P)</tex> (симметрическая разность

Очевидно, <tex>Mv</tex> - максимальное паросочетание графа <tex> G</tex>, не покрывающее <tex> v</tex>, поэтому <tex> v \in D(G)</tex>, противоречие. <br>

'''b.''' Путь <tex>P</tex> кончается ребром из <tex> Mw</tex>, вершина a - конец пути <tex>P</tex>. (см.рисунок)<br>

Рассмотрим паросочетание <tex>Mv∗ = (Mw \oplus E(P)) \bigcup \{aw\} </tex>. Тогда <tex> Mv∗ </tex> - максимальное паросочетание графа <tex> G </tex>, не покрывающее <tex> v </tex>, поэтому <tex> v \in D(G) </tex>, противоречие.

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

Рассмотрим паросочетание <tex> M'' = M \oplus E(P) </tex>. Тогда <tex> |M''| = |M'| + 1 </tex>, причём <tex>M'' \subset E(G - a)</tex>. Противоречие с максимальностью паросочетания <tex>M'</tex>.

Таким образом, наше предположение невозможно и <tex>D(G - a) \subset D(G)</tex>.

|statement=

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

1) Граф <tex>C</tex> имеет совершенное паросочетание.<br>

2) Графы <tex>D1,{...},Dn</tex> - фактор-критические. <br>