171
правка
Изменения
Новая страница: «{{Теорема |id = minsum |statement = Пусть <tex>M_1 = <X, I_1></tex> и <tex>M_2 = <X, I_2></tex> - [[Определение матроида|матро…»
{{Теорема
|id = minsum
|statement = Пусть <tex>M_1 = <X, I_1></tex> и <tex>M_2 = <X, I_2></tex> - [[Определение матроида|матроиды]] с [[Ранговая функция, полумодулярность|ранговыми функциями]] <tex>r_1</tex> и <tex>r_2</tex>, соответственно. Тогда максимальная мощность множества из <tex>I_1 \cap I_2</tex> равна <tex>\min_{U \subset X} (r_1(U) + r_2(X \setminus U))</tex>.
|proof =
Пусть <tex>I \in I_1 \cap I_2</tex>. Следовательно, <tex>\forall U \subset X</tex> верно <tex>I \cap U \in I_1, I \setminus U \in I_2</tex>. Тогда, из определения ранга, <tex>|I| = |I \cap U| + |I \setminus U| \leq r_1(U) + r_2(X \setminus U)</tex>.
В другую сторону докажем теорему алгоритмически. На каждом этапе алгоритм получает <tex>I \in I_1 \cap I_2</tex> и либо заключает, что множества большей мощности из <tex>I_1 \cap I_2</tex> получить нельзя, либо возвращает <tex>J \in I_1 \cap I_2: |J| = |I| + 1</tex>.
Введем двудольный ориентированный '''граф замен''' для <tex>M_1</tex> и <tex>M_2</tex> - граф <tex>D</tex>. Левой долей <tex>D</tex> являются элементы текущего множества <tex>I \in I_1 \cap I_2</tex>, правой - все остальные элементы <tex>X \setminus I</tex>. Проведем ребра <tex>(y, z): y \in I, z \in X \setminus I, I \setminus y \cup z \in I_1</tex>, а также <tex>(z', y'): y' \in I, z' \in X \setminus I, I \setminus y' \cup z' \in I_2</tex>.
[[Файл:ExchangeGraph.JPG]]
Пусть <tex>X_1 = \{z \in X \setminus I | I \cup z \in I_1 \}, X_2 = \{z \in X \setminus I | I \cup z \in I_2 \}, P</tex> - кратчайший путь в <tex>D</tex> из <tex>X_1</tex> в <tex>X_2</tex>. Тогда [[Алгоритм построения базы в пересечении матроидов|алгоритм]] с помощью этого пути либо определяет максимальность набора <tex>I</tex>, либо позволяет найти набор большей мощности.
}}
|id = minsum
|statement = Пусть <tex>M_1 = <X, I_1></tex> и <tex>M_2 = <X, I_2></tex> - [[Определение матроида|матроиды]] с [[Ранговая функция, полумодулярность|ранговыми функциями]] <tex>r_1</tex> и <tex>r_2</tex>, соответственно. Тогда максимальная мощность множества из <tex>I_1 \cap I_2</tex> равна <tex>\min_{U \subset X} (r_1(U) + r_2(X \setminus U))</tex>.
|proof =
Пусть <tex>I \in I_1 \cap I_2</tex>. Следовательно, <tex>\forall U \subset X</tex> верно <tex>I \cap U \in I_1, I \setminus U \in I_2</tex>. Тогда, из определения ранга, <tex>|I| = |I \cap U| + |I \setminus U| \leq r_1(U) + r_2(X \setminus U)</tex>.
В другую сторону докажем теорему алгоритмически. На каждом этапе алгоритм получает <tex>I \in I_1 \cap I_2</tex> и либо заключает, что множества большей мощности из <tex>I_1 \cap I_2</tex> получить нельзя, либо возвращает <tex>J \in I_1 \cap I_2: |J| = |I| + 1</tex>.
Введем двудольный ориентированный '''граф замен''' для <tex>M_1</tex> и <tex>M_2</tex> - граф <tex>D</tex>. Левой долей <tex>D</tex> являются элементы текущего множества <tex>I \in I_1 \cap I_2</tex>, правой - все остальные элементы <tex>X \setminus I</tex>. Проведем ребра <tex>(y, z): y \in I, z \in X \setminus I, I \setminus y \cup z \in I_1</tex>, а также <tex>(z', y'): y' \in I, z' \in X \setminus I, I \setminus y' \cup z' \in I_2</tex>.
[[Файл:ExchangeGraph.JPG]]
Пусть <tex>X_1 = \{z \in X \setminus I | I \cup z \in I_1 \}, X_2 = \{z \in X \setminus I | I \cup z \in I_2 \}, P</tex> - кратчайший путь в <tex>D</tex> из <tex>X_1</tex> в <tex>X_2</tex>. Тогда [[Алгоритм построения базы в пересечении матроидов|алгоритм]] с помощью этого пути либо определяет максимальность набора <tex>I</tex>, либо позволяет найти набор большей мощности.
}}
