Изменения
Нет описания правки
|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= Добавим вершину Обозначим граф (неориентированный), индуцированный <tex>uA \oplus B</tex>, не влияющую на независимость в матроиде — в неё будут вести рёбра за <tex>G</tex>. Обозначим вершины из всех вершин множества <tex>TA \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>.
<tex>\forall j > i \quad y_iz_j \notin G_MG(A) \Rightarrow A \setminus y_i \cup z_j \notin I \Rightarrow C \setminus z_i \subset subseteq \langle A \setminus y_i \rangle</tex>.
Так как <tex>z_i C</tex> — цикл, то <tex>C \in subseteq \langle C \setminus z_i \rangle \subset subseteq \langle A \setminus y_i \rangle </tex>. Это означает, что <tex>z_i \in \langle A \Rightarrow setminus y_i \rangle</tex>, и, следовательно, <tex> A \setminus y_i \cup z_i \notin I</tex>, что приводит к противоречиюс существованием ребра <tex>y_i z_i</tex>.
}}
