Изменения
Нет описания правки
[[Лемма о единственном паросочетании в подграфе замен, индуцированном кратчайшим путем | ]]
Пусть <tex>P = z_0, y_1, z_1, ..., y_t, z_t</tex>, <tex>G = \{ z_1, ..., z_t \} \cup (J \setminus \{ y_1, ..., y_t \})</tex>. Тогда <tex>G \subseteq S</tex>, <tex>|G| = |J|</tex> и дуги из <tex>\{ y_1, ..., y_t \}</tex> в
<tex>\{ z_1, ..., z_t \}</tex> составляют единственное полное паросочетание в <tex>J \bigtriangleup G</tex>. То есть, согласно [[Лемма о единственном паросочетании в подграфе графе замен, индуцированном кратчайшим путем | лемме о единственном паросочетании в подграфе замен, индуцированным кратчайшим путем]], <tex>G \in I_1</tex>.
К тому же, <tex>\forall i \ge 1 z_i \notin X_1</tex>, иначе <tex>P</tex> - не кратчайший путь из <tex>X_1</tex> в <tex>X_2</tex>. Это означает, что <tex>z_i + J \notin I_1</tex>, то есть
<tex>r_1 (J \cup G) = r_1 (J) = r_1 (G) = |G| = |J|</tex>. Так как <tex>J + z_0 \in I_1</tex>, <tex>G + z_0 \in I_1</tex> (т.е. <tex>J' = \{ z_0, z_1, ..., z_t \} \cup (J \setminus \{ y_1, ..., y_t \}) \in I_1</tex>.
