322
правки
Изменения
→Алгоритм решения
<tex>r_1 (U) \le |J \cap U|</tex>
|proof =
От противного. Пусть <tex>r_1 (U) > |J \cap U|</tex>, тогда <tex>\exists z \in U \setminus (J \cap U)</tex> : <tex>(J \cap U) + z \in I_1</tex> при том, что <tex>J + z \notin I_1</tex>. В противном случае (<tex>J + z \in I_1</tex>), <tex>z \in X_1</tex>, то есть <tex>X_1 \cap U \ne \emptyset</tex>, что противоречит отсутствию пути из <tex>X_1</tex> в <tex>X_2</tex>. Так как <tex>(J \cap U) + z \in I_1</tex>, а <tex>J + z \notin I_1</tex>,
<tex>\exists y \in J \setminus U</tex> : <tex>J - y + z \in I_1</tex>. Однако, тогда <tex>(y, z) \in A(J)</tex>, что противоречит тому факту, что <tex>\delta^- (U) = \emptyset</tex>.
}}
