1
правка
Изменения
Нет описания правки
Также существует граф замен для одного матроида.
{{Определение
|id=def_2
|definition =
Пусть дан матроид <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>
|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>.<br>Тогда в <tex>G'</tex> существует единственное [[Паросочетания: основные определения, теорема о максимальном паросочетании и дополняющих цепях#Паросочетание в двудольном графе|полное паросочетание]].
|proof =
[[Файл:Граф_индуцированный_кратчайшим_путем.png | thumb | left | Рис. 1]]
[[Файл:Фрагмент_паросочетания.png | thumb | right | Рис. 2]]
}}
|about=
о паросочетании в графе замен
|statement= Пусть <tex>M = \langle X,\mathcal{I} \rangle </tex> — [[Определение матроида|матроид]]. Множества <tex>A, B \in \mathcal{I}</tex> {{---}} независимы, причем <tex>|A| = |B|</tex>. Тогда двудольный граф <tex>D_{M}(\mathcal{I}A)</tex> содержит полное паросочетание на <tex>A \bigtriangleup B</tex>.
|proof=
* '''База
* '''Переход
}}
|proof=Индукция по <tex>|A|</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>(ab) \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/>
}}
|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 bigtriangleup B</tex>, где <tex>A\in I</tex> и <tex>|A| = |B|</tex>. Тогда <tex>B \in I</tex>.
|proof=
[[Файл: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 : \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]] получаем:<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>(\langle y_i , z_i)\rangle</tex>. :Но тогда, как было отмечено ранее, не существует полного паросочетания. Получили противоречие.
}}
==См. также==
* [[Пересечение матроидов, определение, примеры]]