Изменения

Также существует граф замен для одного матроида. Он определяется так: пусть дан матроид <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>

|statement =

Пусть дан двудольный граф замен. В его правой доле можно выделить два подмножества вершин <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 \}</tex>. Пусть <tex>P</tex> — кратчайший путь из <tex>X_1</tex> в <tex>X_2</tex>. Рассмотрим сужение <tex>G'</tex> графа <tex>G</tex> на множество вершин, лежащих в пути <tex>P</tex>.