92
правки
Изменения
теорема о паросочетании
Таким образом, для выбранных значений параметров сумм не превосходят 1. Это означает, что с положительной вероятностью случайный двудольный граф является <tex>(n, \ m, \ k, \ d, \ \epsilon)</tex> - экспандером. Теорема доказана.
}}
{{Теорема
|statement=
Пусть <tex>G</tex> - двудольный граф.
Тогда <tex>G</tex> имеет совершенное паросочетание тогда и только тогда, когда <tex>\forall S \supseteq L : |S| \leq r(S)</tex>.
|proof=
Будем доказывать по индукции
1. Для <tex>|L| = 1</tex> очевидно
2. Предположим, что верно для <tex>L: |L| < m</tex>
Рассмотрим два случая:
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...
}}
