497
правок
Изменения
Нет описания правки
{{Определение
|definition=
<tex>\mathrm{odd}(G-U)</tex> - количество [[Отношение связности, компоненты связности|компонент связности]] нечетного размера в <tex> G[V - U]</tex>.}}
{{Определение
|statement=
Для любого графа G выполняется:<br>
<tex>\mathrm{def}(G) = \max_{S \subset V(G)} \{\mathrm{odd}(G - S) - |S|\}.</tex>
}}
|statement=
Дан граф <tex>G</tex>, размер максимального паросочетания в нем равен:<br>
<tex>\mathrm{ \alpha } (G) = \min_{U \in V} \{1/2(|V|-|U|-\mathrm{odd}(G-U)\} </tex>
}}
{{Определение
|definition=
Множество <tex>S \subset V (G)</tex>, для которого <tex>\mathrm{odd}(G - S) - |S| = \mathrm{def}(G) </tex>, называется '''барьером'''.
}}
# Графы <tex>D_1,{...},D_n</tex> - фактор-критические. <br>
# Любое максимальное паросочетание <tex>M</tex> графа <tex>G</tex> состоит из совершенного паросочетания графа <tex>C</tex>, почти совершенных паросочетаний графов <tex>D_1,{...},D_n</tex> и покрывает все вершины множества <tex>A(G)</tex> рёбрами с концами в различных компонентах связности <tex>U_1,{...},U_n</tex> <br>
# <tex>\mathrm{def}(G) = n - |A(G)|, 2\mathrm{\alpha }(G) = v(G) + |A(G)| - n</tex>.
|proof=
