17
правок
Изменения
Нет описания правки
Предположим, что существует другое паросочетание <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>.
Противоречие.
}}
{{Лемма
|about=
о паросочетании в графе замен
|statement= Пусть <tex>M = \langle X,I \rangle </tex> — матроид. Множества <tex>A, B \in I</tex> {{---}} независимы, причем <tex>|A| = |B|</tex>. Тогда двудольный граф <tex>D_{M}(I)</tex> содержит полное паросочетание на <tex>A \bigtriangleup B</tex>.
|proof=
Индукция по <tex>|A \bigtriangleup B|</tex>.
* База
*: В случае, когда <tex>|A \bigtriangleup B| = 0 </tex>, это тривиальный случай,имеем пустое паросочетание.
* Переход
*: Пусть <tex>k = |A| = |B|</tex>.
*:Рассмотрим <tex>|A \bigtriangleup B| \geq 1</tex>.
*:Рассмотрим матроид <tex>M_1 = \langle X, \{ A \mid A \in I, A \leq k \} \rangle</tex>. Множества <tex>A, B \in I</tex> и <tex>|A| = |B|</tex>, а значит они являются базами для матроида <tex>M_1</tex>. Тогда по [[Теорема о базах|теореме о базах]] <tex>\forall x \in A \setminus B: \exists y \in B \setminus A : (A \setminus x) \cup y
\in I</tex>, поэтому <tex>(x, y) \in G_M(A)</tex>. Множества <tex>A' = A - x + y </tex> и <tex>B' = B + x - y</tex> являются независимыми как подмножества независимых и их <tex>|A' \bigtriangleup B'| < |A \bigtriangleup B|</tex> Тогда по предположению индукции на их <tex>| A' \bigtriangleup B'|</tex> есть полное паросочетание <tex>N</tex>. Тогда <tex>N \cup {(x, y)}</tex> составляет полное паросочетание на <tex>|A \bigtriangleup B|</tex>, а значит индукционный переход справедлив.
}}
[[Категория:Алгоритмы и структуры данных]]
[[Категория:Матроиды]]
[[Категория: Пересечение матроидов]]
