53
правки
Изменения
Нет описания правки
|about=1
|statement = <tex>A</tex> — независимое множество в матроиде <tex>M=\langle X, I\rangle</tex>. <tex>B \subset X</tex>, <tex>|B|=|A|</tex> и в подграфе графа замен <tex>G_M</tex>, индуцированном <tex>A \oplus B</tex>, существует единственное полное паросочетание. Тогда <tex>B</tex> — независимое в матроиде <tex>M</tex>.
|proof= [[Файл:El_lemma2.png|thumb|right|Граф <tex>G</tex>]]Обозначим граф (неориентированный), индуцированный <tex>A \oplus B</tex> за <tex>G</tex>. Обозначим вершины из <tex>A \setminus B</tex> за <tex>y_i</tex>, из <tex>B \setminus A</tex> за <tex>z_i</tex>. Перенумеруем вершины так, чтобы рёбра из паросочетания соединяли вершины с одинаковыми индексами, и <tex>\forall i,j: i < j</tex> не существовало бы ребра между вершинами <tex>y_i</tex> и <tex>z_j</tex> (возможность первого следует из существования полного паросочетания, второго — из его единственности).
Пусть <tex>B</tex> — не независимо, значит, <tex>\exists</tex> цикл <tex>C \subset B</tex>. Обозначим <tex>i = \min k: z_k \in C</tex>.
