Изменения
Нет описания правки
Пусть <tex>X_1 = \{z \in S \setminus I \mid I \cup z \in I_1 \}, X_2 = \{z \in S \setminus I \mid I \cup z \in I_2 \}, P</tex> — кратчайший путь в <tex>D_{M_1, M_2}(I)</tex> из <tex>X_1</tex> в <tex>X_2</tex>. Тогда [[Алгоритм построения базы в пересечении матроидов|алгоритм]] с помощью этого пути либо определяет максимальность набора <tex>I</tex>, либо позволяет найти набор большей мощности.
Также существует граф замен для одного матроида. Он определяется так: пусть {{Определение|definition =Пусть дан матроид <tex>M = (S, I)</tex> и независимый сет <tex>I \in I</tex>. Тогда '''граф замен ''' <tex>D_{M}(I)</tex> (или просто <tex>D(I)</tex>) {{---}} это двудольный граф с долями <tex>I</tex> и <tex>S \setminus I</tex> с рёбрами между <tex>y \in I</tex> и <tex>x \in S \setminus I</tex> если <tex> I - y + x \in I </tex>}}
{{Лемма
