108
правок
Изменения
Нет описания правки
Пусть множество <tex>J \in (I_1 \cap I_2)</tex>
<br>Определим [[Граф замен для двух матроидов|граф замен]] <tex>D_{M_1, M_2}(J) = (S, A(J))</tex>, где
<tex>A(J) = \{(y, z) | y \in SJ, z \in S\setminus J, J - y + z \in I_1 \} </tex>
<tex>\cup \{ (z', y') | z' \in S \setminus J, y' \in J, J - y' + z' \in I_2 \}</tex>
Пусть <tex>X_1 = \{ z \in S \setminus J | J + z \in I_1 \}</tex>, <tex>X_2 = \{ z \in S \setminus J | J + z \in I_2 \}</tex>, <tex>P</tex> - кратчайший путь из <tex>X_1</tex> в <tex>X_2</tex> в графе <tex>D_{M_1, M_2}(J)</tex>. <tex>P</tex> может и не существовать
