1632
правки
Изменения
м
rollbackEdits.php mass rollback
Также существует граф замен для одного матроида.
{{Определение
|id=def_2
|definition =
Пусть дан матроид <tex>M = (S, \mathcal{I})</tex> и независимый сет <tex>I \in \mathcal{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 \mathcal{I} </tex>
|about=
о паросочетании в графе замен
|statement= Пусть <tex>M = \langle X,\mathcal{I} \rangle </tex> — [[Определение матроида|матроид]]. Множества <tex>A, B \in \mathcal{I}</tex> {{---}} независимы, причем <tex>|A| = |B|</tex>. Тогда двудольный граф <tex>D_{M}(\mathcal{I}A)</tex> содержит полное паросочетание на <tex>A \bigtriangleup B</tex>.
|proof=
