=Декомпозиция Эдмондса-Галлаи=
{{Определение
|definition=
необходимые определения:
* <tex>D(G) = \{v \in V |</tex> существует максимальное паросочетание, не покрывающее <tex> v\}</tex>
* <tex>A(G) = N(D(G)) \setminus D(G)</tex>
* <tex>C(G) = V \setminus( D(G) \bigcup A(G) )</tex>
* <tex> \alpha (G) </tex> - размер максимального паросочетания в <tex>G</tex>
}}
{{Лемма
|about= (Галлаи, о стабильности)
|statement=
пусть <tex> a \in A(G).</tex> Тогда:
* <tex>D(G - a) = D(G)</tex>
* <tex>A(G - a) = A(G) \setminus \{a\}</tex>
* <tex>C(G - a) = C(G)</tex>
* <tex> \alpha (G - a) = \alpha (G) - 1.</tex>
|proof=
много-много и с картинками. :(
}}
{{Теорема
|statement=
пусть дан граф G = (V, E). пусть:* <tex>D(G) = {v из V| существуем максимальное паросочетание, не покрывающее v}</tex>* A(G) = N(D(G))\D(G)* C(G) = V\( D(G) or A(G) )
<br>
тогда:
<br>
* <tex> U = A(G) </tex> - множество свидетелей Татта-Бержа* <tex>С(G) </tex> - объединение всех четных компонент <tex>G-A(G)</tex>* <tex>D(G) </tex> - объединение всех нечетных компонент <tex>G-A(G)</tex>* каждая компонента в <tex> G-A(G) </tex> - фактор-критическая
|proof=
лол 1) A Последовательно удаляя вершины множества A = A(G)D по лемме о стабильности мы получимD(G − A) = D(G), A(G − A) = ∅, C(G − A) = C(G),α(G − A) = α(G) − |A|.Это означает, что не существует рјберD соединяющих вершины из C(G − A) и D(G − A). Каждое максимальное паросочетание M' графа G - A покрывает все вершины множества C(G), поэтому M' содержитсовершенное паросочетание графа C. Тем самым, мы доказали пункт 1). 2) Из формулы α(G − A) = α(G) − |A|. следуетD что U1,..,Un- компоненты связности графа G − A. Для любой вершины u \in Ui существует максимальное паросочетание Mu графа G - A, не содержащее u. Так как Ui - компонента связности графа G - A, паросочетание Mu содержит максимальное паросочетание графа Di (разумеетсяD не покрывающее вершину u). Следовательно, α(Di) = α(Di - u) и по теореме 2.12 мы получаем, что граф Di - фактор-критический. 3) Пусть M - максимальное паросочетание графа G, а M' полученоиз M удалением всех рёбер, инцидентных вершинам множества A. Тогда|M'| ≥ |M| − |A| и по формуле α(G − A) = α(G) − |A| понятно, что M' - максимальноепаросочетание графа G − A. Более того, из α(G − A) = α(G) − |A| следует |M'| = |M|−|A|, а значит, все вершины множества A покрыты в M различными рёбрамию Так как M' - максимальное паросочетание графа G - A, то по пунктам 1) и 2) очевидно, что M' содержит совершенное паросочетание графа C и почти совершенные паросочетания фактор-критических графов D1,...,Dn. Значит, рёбра паросочетания M соединяют вершины A с непокрытыми M' вершинами различных компонентсвязности из U1,...,Un. 4) Из пункта 3) сразу же следуют оба равенства пункта 4
}}
{{Утверждение
|about=следствие из теоремы
