53
правки
Изменения
Нет описания правки
Будем таким образом увеличивать <tex>I</tex>, пока существует путь <tex>p</tex>. Рассмотрим момент, когда такого пути не нашлось.
Введём обозначение: <tex>A = \{u|u \rightsquigarrow T\}</tex>. Докажем, что <tex>r_1(A) = |I \cap A|</tex> от противного.
Пусть <tex>r_1(A) > |I \cap A|</tex>. Обозначим , тогда существует <tex>z \in A \setminus (I \cap A) \cup \{u\}</tex> как <tex>A'</tex>. Заметим, такое, что <tex>(I \cap A' ) \cup \{z\} \in I_1</tex>.Возможны 2 случая:# Если <tex>A' I \cup \{z\cap I = } \varnothingin I_1</tex>, тогда то <tex>u z \in S</tex>, что приводит к противоречию.# Можно добавлять и из <tex>I \setminus A'S</tex> есть путь в <tex>A'</tex>. Значит, пока <tex>|I| > |A'|\cup \{z\} \notin I_1</tex> (по аксиоме замены в <tex>M_1</tex>). Теперь Отсюда следует, что существует <tex>A' = y \in I \setminus \{z\}A</tex>. , такое что <tex>I \setminus \{zy\} \cup \{uz\} \in I_1</tex>, следовательно, . Но тогда ребро <tex>zu \in G_Iyz</tex>имеется в графе, что приводит к противоречиюпротиворечит отсутствию пути из <tex>S</tex> в <tex>T</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> достигается равенство.
Построен пример равенства, значит, теорема доказана.
}}
