Граф замен — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м (rollbackEdits.php mass rollback)
 
(не показано 11 промежуточных версий 4 участников)
Строка 12: Строка 12:
 
Также существует граф замен для одного матроида.   
 
Также существует граф замен для одного матроида.   
 
{{Определение
 
{{Определение
 +
|id=def_2
 
|definition =
 
|definition =
Пусть дан матроид (англ ''matroid'') <tex>M = (S, \mathcal{I})</tex> и независимый сет <tex>I \in \mathcal{I}</tex>. Тогда '''граф замен''' <tex>D_{M}(I)</tex> (или просто <tex>D(I)</tex>) {{---}} это двудольный граф с долями <tex>I</tex> и <tex>S \setminus I</tex> с рёбрами между <tex>y \in I</tex> и <tex>x \in S \setminus I</tex> если <tex> I - y + x \in \mathcal{I} </tex>
+
Пусть дан матроид <tex>M = (S, \mathcal{I})</tex> и независимый сет <tex>I \in \mathcal{I}</tex>. Тогда '''граф замен''' <tex>D_{M}(I)</tex> (или просто <tex>D(I)</tex>) {{---}} это двудольный граф с долями <tex>I</tex> и <tex>S \setminus I</tex> с рёбрами между <tex>y \in I</tex> и <tex>x \in S \setminus I</tex> если <tex> I - y + x \in \mathcal{I} </tex>
 
}}
 
}}
  
Строка 20: Строка 21:
 
|about=о единственном паросочетании в подграфе замен, индуцированном кратчайшим путем
 
|about=о единственном паросочетании в подграфе замен, индуцированном кратчайшим путем
 
|statement =
 
|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>. Рассмотрим сужение <tex>G'</tex> графа <tex>G</tex> на множество вершин, лежащих в пути <tex>P</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 \}</tex>. <tex>P</tex> {{---}} кратчайший путь из <tex>X_1</tex> в <tex>X_2</tex>.  
<br>Тогда в <tex>G'</tex> существует единственное [[Паросочетания: основные определения, теорема о максимальном паросочетании и дополняющих цепях#Паросочетание в двудольном графе|полное паросочетание]].
+
<br><tex>G'</tex> {{---}} подграф <tex>G</tex>, включающий множество вершин, лежащих на пути <tex>P</tex>. Тогда в <tex>G'</tex> существует единственное [[Паросочетания: основные определения, теорема о максимальном паросочетании и дополняющих цепях#Паросочетание в двудольном графе|полное паросочетание]].
 
|proof =
 
|proof =
 
[[Файл:Граф_индуцированный_кратчайшим_путем.png | thumb | left | Рис. 1]]
 
[[Файл:Граф_индуцированный_кратчайшим_путем.png | thumb | left | Рис. 1]]
 
[[Файл:Фрагмент_паросочетания.png‎ | thumb | right | Рис. 2]]
 
[[Файл:Фрагмент_паросочетания.png‎ | 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>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>(a_i,b_i)</tex>.
+
Докажем единственность.
 
+
:Пусть существует другое паросочетание <tex>\langle a_i, b_{j_i} \rangle</tex>. Тогда пусть <tex>i_0 = \min \{ i \: \mid \: j_i < i \}</tex>.  
Предположим, что существует другое паросочетание <tex>(a_i, b_{j_i})</tex>. Тогда пусть <tex>i_0 = \min \{ i \: \mid \: j_i < i \}</tex>. Обозначим <tex>j_{i_0}</tex> как <tex>i_1</tex>. Заметим, что <tex>i_1 < i_0</tex> и поэтому не может быть <tex>j_{i_1} < i_1</tex>, ведь <tex>i_0</tex> — минимальное из соответствующего множества. Так же невозможно <tex>j_{i_1} = i_1</tex>, поскольку тогда <tex>a_{i_0}</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>.
+
:Обозначим <tex>j_{i_0}</tex> как <tex>i_1</tex>. Заметим, что <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>i_0</tex> — минимальное из соответствующего множества. Так же невозможно <tex>j_{i_1} = j_{i_0}</tex>, поскольку тогда <tex>a_{i_0}</tex> и <tex>a_{i_1}</tex> имели бы одинаковую пару.  
Противоречие.
+
:Следовательно, <tex>j_{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>P</tex>, что противоречит тому, что <tex>P</tex> {{---}} кратчайший путь.
 
}}
 
}}
  
Строка 37: Строка 40:
 
|about=
 
|about=
 
о паросочетании в графе замен
 
о паросочетании в графе замен
|statement= Пусть <tex>M = \langle X,\mathcal{I} \rangle </tex> &mdash;  матроид. Множества <tex>A, B \in \mathcal{I}</tex> {{---}} независимы, причем <tex>|A| = |B|</tex>. Тогда двудольный граф <tex>D_{M}(\mathcal{I})</tex>  содержит полное паросочетание на <tex>A \bigtriangleup B</tex>.
+
|statement= Пусть <tex>M = \langle X,\mathcal{I} \rangle </tex> &mdash;  [[Определение матроида|матроид]]. Множества <tex>A, B \in \mathcal{I}</tex> {{---}} независимы, причем <tex>|A| = |B|</tex>. Тогда двудольный граф <tex>D_{M}(A)</tex>  содержит полное паросочетание на <tex>A \bigtriangleup B</tex>.
 
|proof=  
 
|proof=  
  
Докажем по индукции для <tex>|A \bigtriangleup B|</tex>.
+
Индукция по <tex>|A \bigtriangleup B|</tex>.
 
   
 
   
 
* '''База  
 
* '''База  
: В случае, когда <tex>|A \bigtriangleup B| = 0 </tex>, имеем пустое паросочетание.  
+
:При <tex>|A \bigtriangleup B| = 0 </tex> имеем пустое паросочетание.  
  
 
* '''Переход
 
* '''Переход
:Пусть <tex>|A \bigtriangleup B| = N</tex> — верно.
+
:Пусть верно для <tex>|A \bigtriangleup B| = N</tex>.
 
:Пусть <tex>k = |A| = |B|</tex> и <tex>|A \bigtriangleup B| \geqslant 1</tex>.   
 
:Пусть <tex>k = |A| = |B|</tex> и <tex>|A \bigtriangleup B| \geqslant 1</tex>.   
 
+
:Рассмотрим матроид <tex>M_1 = \langle X, \{ A \mid A \in \mathcal{I}, |A| \leqslant k \} \rangle</tex>. Множества <tex>A, B \in \mathcal{I}</tex>, <tex>|A| = |B|</tex> и матроид <tex>M_1</tex> не содержит множеств больших, чем <tex>A</tex>, а значит они являются базами для матроида <tex>M_1</tex>.  
:Рассмотрим матроид <tex>M_1 = \langle X, \{ A \mid A \in \mathcal{I}, A \leqslant k \} \rangle</tex>. Множества <tex>A, B \in \mathcal{I}</tex>, <tex>|A| = |B|</tex> и матроид <tex>M_1</tex> не содержит множеств больших, чем <tex>A</tex>, а значит они являются базами для матроида <tex>M_1</tex>. По [[Теорема о базах|сильной теореме о базах]]  
+
:По [[Теорема о базах|сильной теореме о базах]]: <tex>\forall x \in A \setminus B: \exists y \in B \setminus A : (A \setminus x) \cup y \in \mathcal{I}</tex> и <tex>(B \setminus y) \cup x \in \mathcal{I}</tex>  
:<tex>\forall x \in A \setminus B: \exists y \in B \setminus A : (A \setminus x) \cup y \in \mathcal{I}</tex> и <tex>(B \setminus y) \cup x \in \mathcal{I}</tex> из этого следует, что множество <tex>A' = (A \setminus x) \cup y </tex> и <tex>B' = (B \cup x) \setminus y</tex> являются независимыми, а также базами <tex>M_1</tex>. И их <tex>|A' \bigtriangleup B'| < |A \bigtriangleup B|</tex>. Значит мы умеем переходить от <tex>|A' \bigtriangleup B'| = N</tex> к <tex>|A \bigtriangleup B| = N+1</tex>. По предположению индукции у <tex> |A' \bigtriangleup B'|</tex> есть полное паросочетание.  
+
:Из этого следует, что множества <tex>A' = (A \setminus x) \cup y </tex> и <tex>B' = (B \cup x) \setminus y</tex> являются независимыми, а также базами <tex>M_1</tex>. Заметим, что  <tex>|A' \bigtriangleup B'| < |A \bigtriangleup B|</tex>, <tex>|A' \bigtriangleup B'| = N</tex>, <tex>|A \bigtriangleup B| = N+1 </tex>. По предположению индукции у <tex> |A' \bigtriangleup B'|</tex> есть полное паросочетание.  
 
:По [[Теорема о базах|теореме о базах]] <tex>\forall x \in A \setminus B: \exists y \in B \setminus A : (A \setminus x) \cup y  
 
:По [[Теорема о базах|теореме о базах]] <tex>\forall x \in A \setminus B: \exists y \in B \setminus A : (A \setminus x) \cup y  
\in \mathcal{I}</tex>, следовательно по определению графа <tex>D_M(A) \Rightarrow (x, y) \in D_M(A)</tex>.  Тогда <tex>N \cup {(x, y)}</tex> составляет полное паросочетание на <tex>|A \bigtriangleup B|</tex>, а значит индукционный переход справедлив.
+
\in \mathcal{I}</tex>, следовательно по определению графа <tex>D_M(A), (x, y) \in D_M(A)</tex>.  Тогда <tex>N \cup {(x, y)}</tex> составляет полное паросочетание на <tex>|A \bigtriangleup B|</tex>. Индукционный переход доказан.
  
 
}}
 
}}
Строка 61: Строка 64:
  
 
|proof=Индукция по <tex>|A|</tex>.<br/>
 
|proof=Индукция по <tex>|A|</tex>.<br/>
* База
+
* '''База  
*: При <tex>|A|=1</tex> утверждение очевидно. <br/>
+
: При <tex>|A|=1</tex> утверждение очевидно. <br/>
* Переход
+
* '''Переход
*: Пусть <tex>|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>|A|=n-1</tex>.
Таким образом, последнее ребро в цепи имеет вид <tex>(ab) \in M</tex>, где <tex>a \in A, b \in B, \deg b = 1</tex>. Положим <tex>a_n=a, b_n=b</tex>. Для <tex>G \setminus \{a_n \cup b_n \}</tex> утверждение верно по предположению индукции. С другой стороны, так как <tex>\deg b_n = 1</tex>, то <tex>(a_i b_n) \notin G</tex> при <tex>i<n</tex>, поэтому для <tex>j = n</tex> утверждение также верно.<br/>
+
: Рассмотрим <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>\langle a, b \rangle \in M</tex>, где <tex>a \in A, b \in B, \deg b = 1</tex>. Положим <tex>a_n=a, b_n=b</tex>. Для <tex>G \setminus \{a_n \cup b_n \}</tex> утверждение верно по предположению индукции. С другой стороны, так как <tex>\deg b_n = 1</tex>, то <tex> \langle a_i, b_n \rangle \notin G</tex> при <tex>i<n</tex>, поэтому для <tex>j = n</tex> утверждение также верно.<br/>
 
}}
 
}}
  
Строка 72: Строка 76:
 
|about=
 
|about=
 
о единственном паросочетании в графе замен
 
о единственном паросочетании в графе замен
|statement= Дан [[Определение матроида|матроид]] <tex>M = \langle X,I \rangle </tex>. Пусть двудольный граф <tex>G_M(A) = \{ (x, y) \mid x \in A, y \notin A, A \setminus x \cup y \in I \}</tex> содержит единственное полное паросочетание на <tex>A \oplus B</tex>, где <tex>A\in I</tex> и <tex>|A| = |B|</tex>. Тогда <tex>B \in I</tex>.
+
|statement= Дан [[Определение матроида|матроид]] <tex>M = \langle X,I \rangle </tex>. Пусть двудольный граф <tex>G_M(A) = \{ (x, y) \mid x \in A, y \notin A, A \setminus x \cup y \in I \}</tex> содержит единственное полное паросочетание на <tex>A \bigtriangleup B</tex>, где <tex>A\in I</tex> и <tex>|A| = |B|</tex>. Тогда <tex>B \in I</tex>.
 
|proof=  
 
|proof=  
 
[[Файл:Graph replacement.png|thumb|left|160px|]]
 
[[Файл:Graph replacement.png|thumb|left|160px|]]
Упорядочим вершины левой <tex>(y_i \in A \setminus B)</tex> и правой <tex>(z_j \in B \setminus A)</tex> долей таким образом, что <tex>\forall j > i : (y_i z_j) \notin G_M(A)</tex>. При таком упорядочивании ребра паросочетания имеют вид <tex>(y_i z_i)</tex>.
 
  
Требуется доказать, что <tex>B</tex> независимо. Предположим обратное. Пусть <tex>B \notin I</tex>, тогда существует [[Теорема о циклах|цикл]] <tex>C \subset B</tex>.<br/> Выберем минимальное <tex>i</tex> такое, что <tex>z_i \in C</tex>. Так как <tex>\forall j > i : (y_i z_j) \notin G_M(A)</tex>, то <tex>A \setminus y_i \cup z_j \notin I</tex>, следовательно, <tex>C \setminus z_i \subset \langle A \setminus y_i \rangle </tex>. По [[Оператор замыкания для матроидов#theorem|свойствам замыкания 1 и 3]] получаем:<br/>
+
Упорядочим вершины левой <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)</tex>, то <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>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 \setminus z_i \rangle \subset \langle A \setminus y_i \rangle</tex> <br/>
 
<tex>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 \setminus z_i \rangle \subset \langle A \setminus y_i \rangle</tex> <br/>
Так как <tex>z_i \in \langle C \setminus z_i \rangle \subset \langle A \setminus y_i \rangle</tex>, то <tex>A \setminus y_i \cup z_i \notin I</tex>, то есть в <tex>G_M(A)</tex> не существует ребра <tex>(y_i z_i)</tex>. Но тогда, как было отмечено ранее, не существует полного паросочетания. Получили противоречие.
+
Так как <tex>z_i \in \langle C \setminus z_i \rangle \subset \langle A \setminus y_i \rangle</tex>, то <tex>A \setminus y_i \cup z_i \notin I</tex>, то есть в <tex>G_M(A)</tex> не существует ребра <tex>\langle y_i, z_i \rangle</tex>.  
 +
:Но тогда, как было отмечено ранее, не существует полного паросочетания. Получили противоречие.
 
}}
 
}}
 +
 
==См. также==
 
==См. также==
 
* [[Пересечение матроидов, определение, примеры]]
 
* [[Пересечение матроидов, определение, примеры]]

Текущая версия на 19:33, 4 сентября 2022

Граф замен (англ exchange graph) — специальный ориентированный двудольный граф, фигурирующий в теореме Эдмондса-Лоулера.

Пусть даны матроиды [math]M_1 = \langle S, \mathcal{I}_1 \rangle[/math], [math]M_2 = \langle S, \mathcal{I}_2 \rangle[/math], множество [math](\mathcal{I}_1 \cap \mathcal{I}_2)[/math]. Введем граф замен.

Определение:
Граф замен для двух матроидов [math]D_{M_1, M_2}(I)[/math] — граф, левой долей которого являются элементы множества [math]I[/math], правой — все остальные элементы [math]S[/math] и в котором проведены ребра [math](y, z): y \in I, z \in S \setminus I, I \setminus y \cup z \in \mathcal{I}_1[/math], а также [math](z', y'): y' \in I, z' \in S \setminus I, I \setminus y' \cup z' \in \mathcal{I}_2[/math]


Пусть [math]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[/math] — кратчайший путь в [math]D_{M_1, M_2}(I)[/math] из [math]X_1[/math] в [math]X_2[/math]. Тогда алгоритм с помощью этого пути либо определяет максимальность набора [math]I[/math], либо позволяет найти набор большей мощности.

Граф замен [math]D_{M_1, M_2}(I)[/math]

Также существует граф замен для одного матроида.

Определение:
Пусть дан матроид [math]M = (S, \mathcal{I})[/math] и независимый сет [math]I \in \mathcal{I}[/math]. Тогда граф замен [math]D_{M}(I)[/math] (или просто [math]D(I)[/math]) — это двудольный граф с долями [math]I[/math] и [math]S \setminus I[/math] с рёбрами между [math]y \in I[/math] и [math]x \in S \setminus I[/math] если [math] I - y + x \in \mathcal{I} [/math]


Лемма (о единственном паросочетании в подграфе замен, индуцированном кратчайшим путем):
Пусть дан двудольный граф замен. В его правой доле выделено два подмножества вершин [math]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 \}[/math]. [math]P[/math] — кратчайший путь из [math]X_1[/math] в [math]X_2[/math].
[math]G'[/math] — подграф [math]G[/math], включающий множество вершин, лежащих на пути [math]P[/math]. Тогда в [math]G'[/math] существует единственное полное паросочетание.
Доказательство:
[math]\triangleright[/math]
Рис. 1
Рис. 2
Так как в правой доле полученного графа [math]G'[/math] вершин на одну больше, чем в левой, добавим в [math]G'[/math] фиктивную вершину и отнесем ее к левой доле.
Рассмотрим [math]P = (a_1, b_1, a_2, b_2, \ldots , a_k, b_k)[/math] — кратчайший путь из условия, где [math]a_1[/math] — фиктивная вершина (рис. 1).
В таком случае, полное паросочетание — это набор ребер [math]\langle a_i,b_i \rangle[/math].

Докажем единственность.

Пусть существует другое паросочетание [math]\langle a_i, b_{j_i} \rangle[/math]. Тогда пусть [math]i_0 = \min \{ i \: \mid \: j_i \lt i \}[/math].
Обозначим [math]j_{i_0}[/math] как [math]i_1[/math]. Заметим, что [math]i_1 \lt i_0[/math] (так как [math]j_{i_0} \lt i_0 [/math] по определению [math]i_0[/math]) и поэтому не может быть [math]j_{i_1} \lt j_{i_0}[/math], ведь [math]i_0[/math] — минимальное из соответствующего множества. Так же невозможно [math]j_{i_1} = j_{i_0}[/math], поскольку тогда [math]a_{i_0}[/math] и [math]a_{i_1}[/math] имели бы одинаковую пару.
Следовательно, [math]j_{i_1} \gt j_{i_0}[/math] (рис. 2). Это значит, что существует путь [math]P_1 = (a_1, b_1, \ldots, a_{i_1}, b_{j_{i_1}}, a_{j_{i_1} + 1}, \ldots, a_k, b_k )[/math] короче, чем [math]P[/math], что противоречит тому, что [math]P[/math] — кратчайший путь.
[math]\triangleleft[/math]


Лемма (о паросочетании в графе замен):
Пусть [math]M = \langle X,\mathcal{I} \rangle [/math]матроид. Множества [math]A, B \in \mathcal{I}[/math] — независимы, причем [math]|A| = |B|[/math]. Тогда двудольный граф [math]D_{M}(A)[/math] содержит полное паросочетание на [math]A \bigtriangleup B[/math].
Доказательство:
[math]\triangleright[/math]

Индукция по [math]|A \bigtriangleup B|[/math].

  • База
При [math]|A \bigtriangleup B| = 0 [/math] имеем пустое паросочетание.
  • Переход
Пусть верно для [math]|A \bigtriangleup B| = N[/math].
Пусть [math]k = |A| = |B|[/math] и [math]|A \bigtriangleup B| \geqslant 1[/math].
Рассмотрим матроид [math]M_1 = \langle X, \{ A \mid A \in \mathcal{I}, |A| \leqslant k \} \rangle[/math]. Множества [math]A, B \in \mathcal{I}[/math], [math]|A| = |B|[/math] и матроид [math]M_1[/math] не содержит множеств больших, чем [math]A[/math], а значит они являются базами для матроида [math]M_1[/math].
По сильной теореме о базах: [math]\forall x \in A \setminus B: \exists y \in B \setminus A : (A \setminus x) \cup y \in \mathcal{I}[/math] и [math](B \setminus y) \cup x \in \mathcal{I}[/math]
Из этого следует, что множества [math]A' = (A \setminus x) \cup y [/math] и [math]B' = (B \cup x) \setminus y[/math] являются независимыми, а также базами [math]M_1[/math]. Заметим, что [math]|A' \bigtriangleup B'| \lt |A \bigtriangleup B|[/math], [math]|A' \bigtriangleup B'| = N[/math], [math]|A \bigtriangleup B| = N+1 [/math]. По предположению индукции у [math] |A' \bigtriangleup B'|[/math] есть полное паросочетание.
По теореме о базах [math]\forall x \in A \setminus B: \exists y \in B \setminus A : (A \setminus x) \cup y \in \mathcal{I}[/math], следовательно по определению графа [math]D_M(A), (x, y) \in D_M(A)[/math]. Тогда [math]N \cup {(x, y)}[/math] составляет полное паросочетание на [math]|A \bigtriangleup B|[/math]. Индукционный переход доказан.
[math]\triangleleft[/math]

Лемма о единственном паросочетании в графе замен

Утверждение:
Пусть двудольный граф [math]G[/math] содержит единственное полное паросочетание [math]M[/math]. Тогда можно упорядочить вершины левой [math](a_i \in A)[/math] и правой [math](b_i \in B)[/math] долей таким образом, что [math]\forall j \gt i : (a_i b_j) \notin G[/math]. При этом рёбра паросочетания будут иметь вид [math](a_i b_i)[/math].
[math]\triangleright[/math]

Индукция по [math]|A|[/math].

  • База
При [math]|A|=1[/math] утверждение очевидно.
  • Переход
Пусть верно для [math]|A|=n-1[/math].
Рассмотрим [math]|A|=n\gt 1[/math]. Возьмем произвольную вершину в левой доле. Будем строить из неё чередующуюся цепь, добавляя по очереди ребро, входящее в [math]M[/math], и ребро, не входящее в [math]M[/math]. Заметим, что такой путь не содержит циклов (циклы нечётной длины невозможны, так как граф двудольный, циклы чётной длины отсутствуют из-за единственности паросочетания). Если последнее добавленное ребро не принадлежит [math]M[/math], то присоединим к цепи ребро из [math]M[/math], инцидентное последней вершине. Значит, построение цепи прервется только при добавлении ребра из [math]M[/math] при достижении вершины степени [math]1[/math].
Таким образом, последнее ребро в цепи имеет вид [math]\langle a, b \rangle \in M[/math], где [math]a \in A, b \in B, \deg b = 1[/math]. Положим [math]a_n=a, b_n=b[/math]. Для [math]G \setminus \{a_n \cup b_n \}[/math] утверждение верно по предположению индукции. С другой стороны, так как [math]\deg b_n = 1[/math], то [math] \langle a_i, b_n \rangle \notin G[/math] при [math]i\lt n[/math], поэтому для [math]j = n[/math] утверждение также верно.
[math]\triangleleft[/math]


Лемма (о единственном паросочетании в графе замен):
Дан матроид [math]M = \langle X,I \rangle [/math]. Пусть двудольный граф [math]G_M(A) = \{ (x, y) \mid x \in A, y \notin A, A \setminus x \cup y \in I \}[/math] содержит единственное полное паросочетание на [math]A \bigtriangleup B[/math], где [math]A\in I[/math] и [math]|A| = |B|[/math]. Тогда [math]B \in I[/math].
Доказательство:
[math]\triangleright[/math]
Graph replacement.png

Упорядочим вершины левой [math](y_i \in A \setminus B)[/math] и правой [math](z_j \in B \setminus A)[/math] долей таким образом, что [math]\forall j \gt i : \langle y_i, z_j \rangle \notin G_M(A)[/math]. При таком упорядочивании ребра паросочетания имеют вид [math] \langle y_i, z_i \rangle[/math].

Требуется доказать, что [math]B[/math] независимо.
Предположим обратное. Пусть [math]B \notin I[/math]. Tогда существует цикл [math]C \subset B[/math].
Выберем минимальное [math]i[/math] такое, что [math]z_i \in C[/math]. Так как [math]\forall j \gt i : \langle y_i, z_j \rangle \notin G_M(A)[/math], то [math]A \setminus y_i \cup z_j \notin I[/math]. Cледовательно, [math]C \setminus z_i \subset \langle A \setminus y_i \rangle [/math].
По свойствам замыкания 1 и 3 получаем:

[math]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 \setminus z_i \rangle \subset \langle A \setminus y_i \rangle[/math]
Так как [math]z_i \in \langle C \setminus z_i \rangle \subset \langle A \setminus y_i \rangle[/math], то [math]A \setminus y_i \cup z_i \notin I[/math], то есть в [math]G_M(A)[/math] не существует ребра [math]\langle y_i, z_i \rangle[/math].

Но тогда, как было отмечено ранее, не существует полного паросочетания. Получили противоречие.
[math]\triangleleft[/math]

См. также

Источники информации