Изменения

'''Граф замен''' (англ ''exchange graph'') {{---}} специальный [[Файл:Graph_DY.pngОсновные определения теории графов|400px|thumb|rightориентированный двудольный граф]], фигурирующий в [[Теорема Эдмондса-Лоулера|Граф замен <tex>D_{M_1, M_2}(I)</tex>теореме Эдмондса-Лоулера]].

Пусть даны матроиды <tex>M_1 = \langle S, \mathcal{I}_1 \rangle</tex>, <tex>M_2 = \langle S, \mathcal{I}_2 \rangle</tex>, множество <tex>(\mathcal{I}_1 \cap \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 \mathcal{I}_1</tex>, а также <tex>(z', y'): y' \in I, z' \in S \setminus I, I \setminus y' \cup z' \in \mathcal{I}_2</tex>}}

Пусть <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 \}, P</tex> — текущее независимое множество, построенное [[Алгоритм построения базы кратчайший путь в пересечении матроидов|алгоритмом]] для матроидов <tex>D_{M_1 = \langle S, I_1 \rangleM_2}(I)</tex>, из <tex>M_2 = \langle S, I_2 \rangleX_1</tex>. Введем граф замен в <tex>D_{M_1, M_2}(I)X_2</tex>, левой долей которого являются элементы множества . Тогда [[Алгоритм построения базы в пересечении матроидов|алгоритм]] с помощью этого пути либо определяет максимальность набора <tex>I</tex>, правой — все остальные элементы либо позволяет найти набор большей мощности.[[Файл:Graph_DY.png|400px|thumb|center|Граф замен <tex>SD_{M_1, M_2}(I)</tex>. Проведем все имеющиеся ребра ]]

|proof=Индукция по <tex>|A|</tex>.<br/>* '''База : При <tex>|A|=1</tex> утверждение очевидно. <br/>* '''Переход: Пусть верно для <tex>X_1 |A|= n-1</tex>.: Рассмотрим <tex>|A|=n>1</tex>. Возьмем произвольную вершину в левой доле. Будем строить из неё [[Теорема о максимальном паросочетании и дополняющих цепях#Паросочетание в двудольном графе|чередующуюся цепь]], добавляя по очереди ребро, входящее в <tex>M</tex>, и ребро, не входящее в <tex>M</tex>. Заметим, что такой путь не содержит циклов (циклы нечётной длины невозможны, так как граф двудольный, циклы чётной длины отсутствуют из-за единственности паросочетания). Если последнее добавленное ребро не принадлежит <tex>M</tex>, то присоединим к цепи ребро из <tex>M</tex>, инцидентное последней вершине. Значит, построение цепи прервется только при добавлении ребра из <tex>M</tex> при достижении вершины [[Основные определения теории графов#Степень вершины|степени]] <tex>1</tex>. <br/>:Таким образом, последнее ребро в цепи имеет вид <tex>\{z langle a, b \rangle \in S M</tex>, где <tex>a \setminus I \mid I \cup z in A, b \in I_1 B, \}deg b = 1</tex>. Положим <tex>a_n=a, X_2 b_n= \{z \in S b</tex>. Для <tex>G \setminus I \mid I {a_n \cup z \in I_2 b_n \}, P</tex> — кратчайший путь в утверждение верно по предположению индукции. С другой стороны, так как <tex>D_{M_1, M_2}(I)\deg b_n = 1</tex> из , то <tex>X_1\langle a_i, b_n \rangle \notin G</tex> в при <tex>X_2i<n</tex>. Тогда [[Алгоритм построения базы в пересечении матроидов|алгоритм]] с помощью этого пути либо определяет максимальность набора , поэтому для <tex>Ij = n</tex>, либо позволяет найти набор большей мощностиутверждение также верно.<br/>}}

|about=о единственном паросочетании в графе замен|statement =Дан [[Определение матроида|матроид]] <tex>M = \langle X,I \rangle </tex>. Пусть дан двудольный граф замен. В его правой доле можно выделить два подмножества вершин <tex>X_1 G_M(A) = \{z \in S \setminus I (x, y) \mid I \cup z x \in I_1 A, y \}notin A, X_2 = \{z \in S A \setminus I \mid I x \cup z y \in I_2 I \}</tex>. Пусть содержит единственное полное паросочетание на <tex>PA \bigtriangleup B</tex> — кратчайший путь из , где <tex>X_1A\in I</tex> в и <tex>X_2</tex>. Рассмотрим сужение <tex>G'</tex> графа <tex>G</tex> на множество вершин, лежащих в пути <tex>P|A| = |B|</tex>.<br>Тогда в <tex>G'B \in I</tex> существует единственное [[Паросочетания: основные определения, теорема о максимальном паросочетании и дополняющих цепях#Паросочетание в двудольном графе|полное паросочетание]].|proof =[[Файл:Граф_индуцированный_кратчайшим_путемGraph replacement.png | thumb | left | Рис. 1]][[Файл:Фрагмент_паросочетания.png‎ | thumb | right 160px| Рис. 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>(y_i \in A \setminus B)</tex> и правой <tex>(z_j \in B \setminus A)</tex> долей таким образом, что <tex>\forall j > i : \langle y_i, z_j \rangle \notin G_M(A)</tex>. При таком упорядочивании ребра паросочетания очевидно — это ребра имеют вид <tex> \langle y_i, z_i \rangle</tex>.:Требуется доказать, что <tex>B</tex> независимо. :Предположим обратное. Пусть <tex>B \notin I</tex>. Tогда существует [[Теорема о циклах|цикл]] <tex>C \subset B</tex>.<br/> Выберем минимальное <tex>i</tex> такое, что <tex>z_i \in C</tex>. Так как <tex>\forall j > i : \langle y_i, z_j \rangle \notin G_M(a_iA)</tex>,b_i)то <tex>A \setminus y_i \cup z_j \notin I</tex>. Cледовательно, <tex>C \setminus z_i \subset \langle A \setminus y_i \rangle </tex>.

Предположим, что существует другое паросочетание :По [[Оператор замыкания для матроидов#theorem|свойствам замыкания 1 и 3]] получаем:<tex>(a_i, b_{j_i})</tex>. Тогда пусть <tex>i_0 = C \setminus z_i \subset \langle A \setminus y_i \rangle \Rightarrow \langle C \setminus z_i \rangle \subset \langle \langle A \setminus y_i \rangle \rangle \Rightarrow \langle C \min setminus z_i \{ i rangle \: subset \mid langle A \: j_i < i setminus y_i \}rangle</tex>. Обозначим <tex>j_{i_0}<br/tex> Так как <tex>i_1z_i \in \langle C \setminus z_i \rangle \subset \langle A \setminus y_i \rangle</tex>. Заметим, что то <tex>i_1 < i_0</tex> и поэтому не может быть <tex>j_{i_1} < i_1A \setminus y_i \cup z_i \notin I</tex>, ведь то есть в <tex>i_0G_M(A)</tex> — минимальное из соответствующего множества. Так же невозможно не существует ребра <tex>j_{i_1} = i_1</tex>\langle y_i, поскольку тогда <tex>a_{i_0}z_i \rangle</tex> и <tex>a_{i_1}</tex> имели бы одинаковую пару. Следовательно:Но тогда, <tex>j_{i_1} > i_1</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>P</tex>полного паросочетания. ПротиворечиеПолучили противоречие.

[[Категория: Пересечение матроидов]]