Изменения
Нет описания правки
{{Определение
|definition=
<tex>oodd(G-U)</tex> - количество компонент связности нечетного размера в <tex> G[V - U]</tex>.}}
{{Определение
|statement=
Для любого графа G выполняется:<br>
<tex>def(G) = max_{S \subset V(G)} \{oodd(G - S) - |S|\}.</tex>
}}
|statement=
Дан граф <tex>G</tex>, размер максимального паросочетания в нем равен:<br>
<tex>\alpha (G) = min_{U \in V} \{1/2(|V|-|U|-oodd(G-U)\} </tex>
}}
{{Определение
|definition=
Множество <tex>S \subset V (G)</tex>, для которого <tex>oodd(G - S) - |S| = def(G) </tex>, называется '''барьером'''.
}}
