Изменения
Нет описания правки
|about=1
|statement = <tex>A</tex> — независимое множество. <tex>B \subset A</tex>, в <tex>B</tex> существует единственное полное паросочетание. Тогда <tex>A \oplus B</tex> — независимое.
|proof= Добавим вершину <tex>u</tex>, не влияющую на независимость в матроиде — в неё будут вести рёбра из всех вершин множества <tex>T</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_M(A) \Rightarrow A \setminus y_i \cup z_j \notin I \Rightarrow C \setminus z_i \subset \langle A \setminus y_i \rangle</tex>.
<tex>z_i \in \langle C \setminus z_i \rangle \subset \langle A \setminus y_i \rangle \Rightarrow A \setminus y_i \cup z_i \notin I</tex>, что приводит к противоречию.
}}
