92
правки
Изменения
м
<tex>\measuredangle</tex> Рассмотрим порожденные графы <tex>G_{1} = T \cup \Gamma(T)</tex> и <tex>G_{2} = L \diagdown T \cup R \diagdown \Gamma(T)</tex>.
→теорема о паросочетаниях
'''Замечание:''' константы в <tex>O</tex> зависят от <tex>\epsilon</tex>.
=== теорема о паросочетаниях Паросочетаниях ===
{{Теорема
|statement=
2. Пусть <tex>\exists\ T \in L, \ |T| \neq 0</tex> такое, что <tex>|\Gamma(T)| = |T|</tex>.
По предположению индукции <tex>G_{1}</tex> имеет совершенное паросочетание (Заметим, что предположение индукции не может использовано непосредственно на <tex>G_{2}</tex>).
Следовательно, <tex>G_{2}</tex> также удовлетворяет неравенству теоремы и по предположению индукции имеет паросочетание. Объединение совершенных паросочетаний <tex>G_{1}</tex> и <tex>G_{2}</tex> {{---}} паросочетание для <tex>G</tex>.
}}
== Определения расширений ==
===Реберное расширение===
