Изменения
Нет описания правки
'''Граф замен''' — специальный [[Основные определения теории графов|ориентированный двудольный граф]], фигурирующий в [[Теорема Эдмондса-Лоулера|теореме Эдмондса-Лоулера]].
Пусть даны матроиды <tex>M_1 = \langle S, I_1 \mathcal{I}_1 \rangle</tex>, <tex>M_2 = \langle S, I_2 \mathcal{I}_2 \rangle</tex>, множество <tex>(\mathcal{I = (I_1 }_1 \cap I_2\mathcal{I}_2)</tex>. Введем граф замен.
{{Определение
|definition =
'''Граф замен для двух матроидов''' <tex>D_{M_1, M_2}(I)</tex> {{---}} граф, левой долей которого являются элементы множества <tex>I</tex>, правой — все остальные элементы <tex>S</tex> и в котором проведены ребра <tex>(y, z): y \in I, z \in S \setminus I, I \setminus y \cup z \in I_1\mathcal{I}_1</tex>, а также <tex>(z', y'): y' \in I, z' \in S \setminus I, I \setminus y' \cup z' \in I_2\mathcal{I}_2</tex>
}}
