Изменения
Нет описания правки
|definition=
множество U, на котором достигается минимум в формуле Татта-Баржа назовем множеством свидетелей.}}
{{Утверждение
|statement=
выполняется следующее:
* все вершины из U покрыты любим максимальным паросочетанием в G
* если K - множество вершин компоненты G-U, тогда любое максимальное паросочетание в G покрывает как минимум половину вершин в K. В частности, каждая вершина в четной компоненте покрыта любым максимальным паросочетанием.
}}
{{Утверждение
|statement=
если U - не пустое множество свидетелей Татта-Бержа для графа G, тогда в G есть вершины, которые входят в любое максимальное паросочетание.
}}
{{Определение
|definition=
граф G = (V, E) называется фактор-критическим, если в нем нем полного паросочетания, но для каждой вершины v из V граф G-v имеет полное.}}
{{Теорема
|statement=
граф G факторо-критический тогда и только тогда, когда для каждой вершины v из V существует максимальное паросочетание в G, которое не покрывает вершину v.
}}
{{Утверждение
|statement=
пусть C - цикл нечетной длины в G. Если граф G/С, полученный сжатием C в одну вершину, фактор-критический, то и G - фактор-критический.
}}
=Декомпозиция Эдмондса-Галлаи=
{{Теорема
|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>
* U = A(G) - множество свидетелей Татта-Бержа
* С(G) - объединение всех четных компонент G-A(G)
* D(G) - объединение всех нечетных компонент G-A(G)
* каждая компонента в G-A(G) - фактор-критическая
|proof=
лол.
}}
{{Утверждение
|about=следствие из теоремы
|statement=
граф G фактор-критический тогда и только тогда, когда U не пусто и U - единственное множество свидетелей Татта-Бержа для G
}}
