Изменения

{{Теорема|id = minsum |statement = Пусть <tex>M_1 = \langle S'''Граф замен''' - специальный ориентированный двудольный граф, I_1 \rangle</tex> и <tex>M_2 = \langle S, I_2 \rangle</tex> — [[Определение матроида|матроиды]] с [[Ранговая функция, полумодулярность|ранговыми функциями]] <tex>r_1</tex> и <tex>r_2</tex>, соответственно. Тогда максимальная мощность множества из <tex>I_1 \cap I_2</tex> равна <tex>\min\limits_{U \subset S} (r_1(U) + r_2(S \setminus U))</tex>.|proof = Утверждение <tex>|I| \leq r_1(U) + r_2(S \setminus U)</tex> фигурирующий в [[Теорема Эдмондса-Лоулера|доказываетсятеореме Эдмондса-Лоулера]] легко.

В другую сторону докажем теорему алгоритмически. На каждом этапе алгоритм получает Пусть <tex>I \in I_1 \cap I_2</tex> и либо заключает- текущее независимое множество, что множества большей мощности из построенное [[Алгоритм построения базы в пересечении матроидов|алгоритмом]] для матроидов <tex>M_1 = \langle S, I_1 \cap I_2rangle</tex> получить невозможно, либо возвращает <tex>J M_2 = \in I_1 langle S, I_2 \cap I_2: |J| = |I| + 1rangle</tex>. Введем двудольный ориентированный '''граф замен''' для <tex>D_{M_1</tex> и <tex>, M_2}(I)</tex> — граф <tex>D</tex>. Левой , левой долей <tex>D</tex> которого являются элементы текущего множества <tex>I \in I_1 \cap I_2</tex>, правой — все остальные элементы <tex>S \setminus I</tex>. Проведем все имеющиеся ребра <tex>(y, z)</tex>: <tex>y \in I</tex>, <tex>z \in S \setminus I</tex>, <tex>I \setminus y \cup z \in I_1</tex>, а также <tex>(z', y')</tex>: <tex>y' \in I</tex>, <tex>z' \in S \setminus I</tex>, <tex>I \setminus y' \cup z' \in I_2</tex>.

Пусть <tex>X_1 = \{z \in S \setminus I | I \cup z \in I_1 \}, X_2 = \{z \in S \setminus I | I \cup z \in I_2 \}, P</tex> — кратчайший путь в <tex>DD_{M_1, M_2}(I)</tex> из <tex>X_1</tex> в <tex>X_2</tex>. Тогда [[Алгоритм построения базы в пересечении матроидов|алгоритм]] с помощью этого пути либо определяет максимальность набора <tex>I</tex>, либо позволяет найти набор большей мощности.}}