108
правок
Изменения
Нет описания правки
<tex>J' = J \bigtriangleup V(P) \in I_1 \cap I_2</tex>
|proof =
[[Лемма о единственном паросочетании Файл:Intersection1.jpg|thumb|right|Путь <tex>P</tex> в подграфе замен<tex>D_{M_1, индуцированном кратчайшим путем | M_2}(J)</tex>]]
Пусть <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>.
