322
правки
Изменения
→Условие теоремы
Докажем, что <tex>r_1(A) = |I \cap A|</tex> от противного.
Пусть <tex>r_1(A) > |I \cap A|</tex>, тогда существует <tex>z w \in A \setminus (I \cap A)</tex>, такое, что <tex>(I \cap A) \cup \{zw\} \in I_1</tex>. Если <tex>I \cup \{zw\} \in I_1</tex>, то <tex>z w \in S</tex> и из <tex>S</tex> есть путь в <tex>A</tex>. Значит, <tex>I \cup \{zw\} \notin I_1</tex>. Отсюда следует, что существует <tex>y \in I \setminus A</tex>, такое что <tex>I \setminus \{y\} \cup \{zw\} \in I_1</tex>. Но тогда ребро <tex>yzyw</tex> имеется в графе, то есть из <tex>y</tex> существует путь в <tex>T</tex>, что противоречит условию <tex>y \in I \setminus A</tex>.
Следовательно, <tex>r_1(A) = |I \cap A|</tex>. Аналогично, <tex>r_2(\overline A) = |I \cap \overline A|</tex>. Отсюда <tex>r_1(A) + r_2(\overline A) = |I|</tex>, то есть при найденных <tex>I</tex> и <tex>A</tex> достигается равенство.
Построен пример равенства, значит, теорема доказана.
}}
== Источник ==
''Chandra Chekuri'' — [http://www.cs.illinois.edu/class/sp10/cs598csc/Lectures/Lecture17.pdf '''Combinatorial Optimization'''], c. 2-4
