92
правки
Изменения
теорема о паросочетании
1. <tex>\forall S \supseteq L (|S| \neq 0)</tex> строго расширяется, то есть <tex>|r(S)| > |S|</tex>. <tex>\measuredangle \ \ \forall x \supset V(L) : (x, y) \in E</tex>. <tex>\measuredangle G^{*} : L^{*} = L \diagdown {x}</tex> и <tex>R^{*} = R \diagdown {y}</tex>. Так как <tex>\forall S \supset L</tex> строгому неравенству теоремы, каждое подмножество <tex>L^{*}</tex> удовлетворяет неравенству, так как только одна вершина <tex>y</tex> удалена из <tex>R</tex> следовательно по предположению индукции меньший граф <tex>G^{*}</tex> имеет паросочетание. К этому паросочетанию добавляем ребро {x, y} что дает совершенное паросочетание.
2. to be continueПусть <tex>\exists T \in L \ (|T| \neq 0)</tex> такое, что <tex>|r(T)| = |T|</tex>. <tex>\measuredangle</tex> порожденные графы <tex>G_{1} = T \bigcup r(T)</tex> и <tex>G_{2} = L \diagdown T \bigcup R \diagdown r(T)</tex>. По предположению индукции <tex>G_{1}</tex> имеет совершенное паросочетание (Заметим, что предположение индукции не может использоваться на <tex>G_{2}</tex>). Пусть <tex>S \supseteq L \diagdown T</tex>, тогда: <tex> r_{G_{2}}(S) = r_{G}(S \bigcup T) \diagdown r_{G}(T) \ \Rightarrow</tex> <tex>|r_{G_{2}}| \geqslant |S \bigcup T| - |T| = |S|</tex> Неравенство верно, поскольку <tex>S \bigcup T</tex> удовлетворяет <tex>|r_{G}(S \bigcup T)| \geqslant |S \bigcup T|</tex> и по предположению индукции <tex>|r_{G}(T)| = |T|</tex>. Следовательно, <tex>G_{2}</tex> также удовлетворяет неравенству и по предположению индукции имеет паросочетание. Объединение паросочетаний <tex>G_{1}</tex> и <tex>G_{2}</tex> {{---}} паросочетание для <tex>G</tex>.
}}
