Изменения

Пусть <tex>I</tex> - текущее независимое множество, построенное [[Алгоритм построения базы в пересечении матроидов|алгоритмом]] для матроидов <tex>M_1 = \langle S, I_1 \rangle</tex>, <tex>M_2 = \langle S, I_2 \rangle</tex>. Введем граф замен <tex>D_{M_1, M_2}(I)</tex>, левой долей которого являются элементы множества <tex>I</tex>, правой — все остальные элементы <tex>S</tex>. Проведем все имеющиеся ребра  <tex>(y, z)</tex>: <tex>y \in I</tex>, <tex>z \in S \setminus I</tex>, <tex>I \setminus y \cup z \in I_1</tex>,  а также  <tex>(z', y')</tex>: <tex>y' \in I</tex>, <tex>z' \in S \setminus I</tex>, <tex>I \setminus y' \cup z' \in I_2</tex>.