Изменения

'''Граф замен''' (англ ''exchange graph'') {{Теорема|id = minsum |statement = Пусть <tex>M_1 = <S, I_1></tex> и <tex>M_2 = <S, I_2></tex> - --}} специальный [[Определение матроидаОсновные определения теории графов|матроидыориентированный двудольный граф]] с , фигурирующий в [[Ранговая функция, полумодулярностьТеорема Эдмондса-Лоулера|ранговыми функциямитеореме Эдмондса-Лоулера]] <tex>r_1</tex> и <tex>r_2</tex>, соответственно. Тогда максимальная мощность множества из <tex>I_1 \cap I_2</tex> равна <tex>\min_{U \subset S} (r_1(U) + r_2(S \setminus U))</tex>.|proof = Пусть <tex>I \in I_1 \cap I_2</tex>. Следовательно, <tex>\forall U \subset S</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(S \setminus U)</tex>.

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

Введем двудольный ориентированный '''граф замен''' для Пусть <tex>M_1X_1 = \{z \in S \setminus I \mid I \cup z \in \mathcal{I}_1 \}, X_2 = \{z \in S \setminus I \mid I \cup z \in \mathcal{I}_2 \}, P</tex> и — кратчайший путь в <tex>D_{M_1, M_2}(I)</tex> - граф из <tex>DX_1</tex>. Левой долей в <tex>DX_2</tex> являются элементы текущего множества . Тогда [[Алгоритм построения базы в пересечении матроидов|алгоритм]] с помощью этого пути либо определяет максимальность набора <tex>I \in I_1 \cap I_2</tex>, правой - все остальные элементы либо позволяет найти набор большей мощности.[[Файл:Graph_DY.png|400px|thumb|center|Граф замен <tex>S \setminus D_{M_1, M_2}(I)</tex>]] Также существует граф замен для одного матроида. Проведем ребра {{Определение|id=def_2|definition =Пусть дан матроид <tex>M = (yS, z\mathcal{I}): y \in </tex> и независимый сет <tex>I, z \in S \setminus mathcal{I}</tex>. Тогда '''граф замен''' <tex>D_{M}(I)</tex> (или просто <tex>D(I, )</tex>) {{---}} это двудольный граф с долями <tex>I </tex> и <tex>S \setminus y \cup z \in I_1I</tex>, а также с рёбрами между <tex>(z', y'): y' \in I, z' </tex> и <tex>x \in S \setminus I, </tex> если <tex> I \setminus - y' + x \cup z' in \in I_2mathcal{I} </tex>.}}

{{Лемма |id= ==lemma==|about=о единственном паросочетании в подграфе замен, индуцированном кратчайшим путем|statement =Пусть дан двудольный граф замен. В его правой доле выделено два подмножества вершин <tex>X_1 = \{z \in S \setminus I \mid I \cup z \in \mathcal{I}_1 \}, X_2 = \{z \in S \setminus I \mid I \cup z \in \mathcal{I}_2 \}</tex>. <tex>P</tex> {{---}} кратчайший путь из <tex>X_1</tex> в <tex>X_2</tex>. <br><tex>G'</tex> {{---}} подграф <tex>G</tex>, включающий множество вершин, лежащих на пути <tex>P</tex>. Тогда в <tex>G'</tex> существует единственное [[Паросочетания: основные определения, теорема о максимальном паросочетании и дополняющих цепях#Паросочетание в двудольном графе|полное паросочетание]].|proof =[[Файл:Граф_индуцированный_кратчайшим_путем.png | thumb | left | Рис. 1]][[Файл:ExchangeGraphФрагмент_паросочетания.JPGpng‎ | thumb | right | Рис. 2]]:Так как в правой доле полученного графа <tex>G'</tex> вершин на одну больше, чем в левой, добавим в <tex>G'</tex> фиктивную вершину и отнесем ее к левой доле. :Рассмотрим <tex>P = (a_1, b_1, a_2, b_2, \ldots , a_k, b_k)</tex> {{---}} кратчайший путь из условия, где <tex>a_1</tex> {{---}} фиктивная вершина (рис. 1). :В таком случае, полное паросочетание {{---}} это набор ребер <tex>\langle a_i,b_i \rangle</tex>.

Докажем единственность.:Пусть существует другое паросочетание <tex>X_1 = \langle a_i, b_{z j_i} \in S \setminus I | I \cup z rangle</tex>. Тогда пусть <tex>i_0 = \in I_1 \}, X_2 = min \{z i \in S : \setminus I | I mid \cup z \in I_2 : j_i < i \}</tex>. :Обозначим <tex>j_{i_0}</tex> как <tex>i_1</tex>. Заметим, Pчто <tex>i_1 < i_0</tex> (так как <tex>j_{i_0} < i_0 </tex> по определению <tex>i_0</tex>) и поэтому не может быть <tex>j_{i_1} < j_{i_0}</tex> - кратчайший путь в , ведь <tex>Di_0</tex> — минимальное из соответствующего множества. Так же невозможно <tex>j_{i_1} = j_{i_0}</tex>, поскольку тогда <tex>a_{i_0}</tex> и <tex>X_1a_{i_1}</tex> в имели бы одинаковую пару. :Следовательно, <tex>X_2j_{i_1} > j_{i_0}</tex>(рис. Тогда [[Алгоритм построения базы в пересечении матроидов|алгоритм]] с помощью этого пути либо определяет максимальность набора 2). Это значит, что существует путь <tex>P_1 = (a_1, b_1, \ldots, a_{i_1}, b_{j_{i_1}}, a_{j_{i_1} + 1}, \ldots, a_k, b_k )</tex> короче, чем <tex>IP</tex>, либо позволяет найти набор большей мощностичто противоречит тому, что <tex>P</tex> {{---}} кратчайший путь.