Изменения

'''Граф замен''' — (англ ''exchange graph'') {{---}} специальный [[Основные определения теории графов|ориентированный двудольный граф]], фигурирующий в [[Теорема Эдмондса-Лоулера|теореме Эдмондса-Лоулера]].

Пусть дан двудольный граф замен. В его правой доле можно выделить выделено два подмножества вершин <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> существует единственное [[Паросочетания: основные определения, теорема о максимальном паросочетании и дополняющих цепях#Паросочетание в двудольном графе|полное паросочетание]].

Строго говоря, утверждение теоремы не совсем корректно, так :Так как в правой доле полученного графа <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>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} < i_1j_{i_0}</tex>, ведь <tex>i_0</tex> — минимальное из соответствующего множества. Так же невозможно <tex>j_{i_1} = i_1j_{i_0}</tex>, поскольку тогда <tex>a_{i_0}</tex> и <tex>a_{i_1}</tex> имели бы одинаковую пару. :Следовательно, <tex>j_{i_1} > i_1j_{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> {{---}} кратчайший путь.

|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>.

* '''База *: В случае, когда При <tex>|A \bigtriangleup B| = 0 </tex>, это тривиальный случай,имеем пустое паросочетание.  * '''Переход*:Пусть верно для <tex>|A \bigtriangleup B| = N</tex>.: Пусть <tex>k = |A| = |B|</tex>.*:Рассмотрим и <tex>|A \bigtriangleup B| \geq geqslant 1</tex>. *:Рассмотрим матроид <tex>M_1 = \langle X, \{ A \mid A \in \mathcal{I}, |A | \leq 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>(x, B \setminus y) \cup x \in G_M(A)\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>N\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>. Индукционный переход доказан. }} ==Лемма о единственном паросочетании в графе замен=={{Утверждение|statement=Пусть [[Двудольные_графы_и_раскраска_в_2_цвета|двудольный граф]] <tex>G</tex> содержит единственное [[Связь_максимального_паросочетания_и_минимального_вершинного_покрытия_в_двудольных_графах#Связь_максимального_паросочетания_и_минимального_вершинного_покрытия_в_двудольном_графе|полное паросочетание]] <tex>M</tex>. Тогда можно упорядочить вершины левой <tex>(a_i \in A)</tex> и правой <tex>(b_i \in B)</tex> долей таким образом, что <tex>\forall j > i : (a_i b_j) \notin G</tex>. При этом рёбра паросочетания будут иметь вид <tex>(a_i b_i)</tex>. |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>\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/>}}