49
правок
Изменения
Нет описания правки
|statement= <tex>def G = \max\limits_{S \in V} (odd(G \setminus S) - |S|)</tex>
|proof=
<tex> \forall S \in V \; (odd(G \setminus S) + |S|) \; mod \; 2 = n \; mod \; 2 \\</tex>.
Рассмотрим несколько случаев:
1) Если <tex> \max\limits_{S \in V}(odd(G \setminus S) - |S|) = 0 </tex>, тогда <tex>\forall \; S \in \; V: \; odd(G \setminus S) \leq |S| \; </tex> и выполнен критерий Татта, значит, в графе есть совершенное паросочетание, т.е. его дефицит равен нулю.
