116
правок
Изменения
Нет описания правки
Значит по третьей аксиоме [[Определение матроида|определения матроида]] <tex>\exists b_2 \in B_2 </tex> такой, что <tex>(B_1 \setminus b_1) \cup b_2 \in I</tex>. <br>
А так как <tex>|(B_1 \setminus b_1) \cup b_2| = |B_1| \:</tex> и <tex>B_1</tex> — база, то <tex>(B_1 \setminus b_1) \cup b_2 \in \mathcal{B}</tex>, что и требовалось доказать.
}}
{{Лемма
|id=lemma_1
|statement=
Пусть <tex>M = \langle X, I \rangle</tex> — матроид, <tex>A \in I, a \notin A, A \cup a \notin I</tex>. Тогда: <br>
1) <tex>\exists ! \ C \in A \cup a</tex> — цикл <br>
2) <tex>\forall b \in C, (A \cup a) \setminus b \in I</tex>
|proof=TBD
}}
{{Теорема
|id=strong_base_theorem
|about=
Сильная теорема о базах
|statement= Пусть <tex>M</tex> — матроид и <tex>\mathcal{B}</tex> — семейство его баз. Тогда <tex>\forall B_1, B_2 \in \mathcal{B} : \forall x \in B_1 \setminus B_2 : \exists y \in B_2 \setminus B_1</tex>
такой, что <tex>(B_1 \setminus x) \cup y \in \mathcal{B}</tex> и <tex>(B_2 \setminus y) \cup x \in \mathcal{B}</tex>
|proof=TBD
}}
