Изменения
Нет описания правки
Также существует граф замен для одного матроида.
{{Определение
|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>. Тогда в <tex>G'</tex> существует единственное [[Паросочетания: основные определения, теорема о максимальном паросочетании и дополняющих цепях#Паросочетание в двудольном графе|полное паросочетание]].
|proof =
[[Файл:Граф_индуцированный_кратчайшим_путем.png | thumb | left | Рис. 1]]
Докажем единственность.
:Пусть существует другое паросочетание <tex>\langle a_i, b_{j_i} \rangle</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_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> {{---}} кратчайший путь.
}}
|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})</tex> содержит полное паросочетание на <tex>A \bigtriangleup B</tex>.
|proof=
:Пусть верно для <tex>|A \bigtriangleup B| = N</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>\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>\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) , (x, y) \in D_M(A)</tex>. Тогда <tex>N \cup {(x, y)}</tex> составляет полное паросочетание на <tex>|A \bigtriangleup B|</tex>. Индукционный переход доказан.
}}
