Изменения
Нет описания правки
[[Файл:Graph_DY.png|250px400px|thumb|right|Граф замен <tex>D_{M_1, M_2}(I)</tex>]]
'''Граф замен''' — специальный ориентированный двудольный граф, фигурирующий в [[Теорема Эдмондса-Лоулера|теореме Эдмондса-Лоулера]].
Пусть <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): y \in I, z \in S \setminus I, I \setminus y \cup z \in I_1</tex>,
а также
<tex>(z', y'): y' \in I, z' \in S \setminus I, I \setminus y' \cup z' \in I_2</tex>.
Пусть <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>, либо позволяет найти набор большей мощности.
