Материал из Викиконспекты
| Определение: |
| База (англ. base) — максимальное по включению независимое множество. То есть
[math]B \in I[/math] — база, если [math] \forall A \in I : B \subseteq A \Rightarrow A = B [/math]. |
| Теорема (о равномощности баз): |
Пусть [math]B_1[/math] и [math]B_2[/math] — базы матроида [math]M[/math]. Тогда [math]|B_1| = |B_2|[/math]. |
| Доказательство: |
| [math]\triangleright[/math] |
|
Доказательство от противного.
Пусть [math]|B_1| \gt |B_2|[/math]. Тогда по третьей аксиоме определения матроида [math]\exists x \in B_1 \setminus B_2[/math] такой, что [math]B_2 \cup {x} \in I[/math]. То есть [math]B_2[/math] — не максимальное по включению независимое множество, что противоречит определению базы.
Случай [math]|B_2| \gt |B_1|[/math] разбирается аналогично. |
| [math]\triangleleft[/math] |
| Теорема (о базах): |
Пусть [math]M[/math] — матроид и [math]\mathcal{B}[/math] — семейство его баз. Тогда:
1) [math]\mathcal{B} \ne \varnothing[/math];
2) если [math]B_1, B_2 \in \mathcal{B}[/math] и [math]B_1 \ne B_2[/math], то [math]B_1 \nsubseteq B_2[/math] и [math]B_2 \nsubseteq B_1[/math];
3) если [math]B_1, B_2 \in \mathcal{B}[/math], то для [math]\forall b_1 \in B_1 \: \exists b_2 \in B_2 [/math] такой, что [math](B_1 \setminus b_1) \cup b_2 \in \mathcal{B}[/math]. |
| Доказательство: |
| [math]\triangleright[/math] |
|
1) Следует из первой аксиомы определения матроида.
2) Из теоремы о равномощности баз следует, что [math]\neg (B_1 \subset B_2)[/math] и [math]\neg (B_2 \subset B_1)[/math].
А с условием [math]B_1 \ne B_2[/math] получаем [math]B_1 \nsubseteq B_2[/math] и [math]B_2 \nsubseteq B_1[/math].
3) По второй аксиоме определения матроида [math]\forall b_1 \in B_1[/math] верно, что [math](B_1 \setminus b_1) \in I[/math].
По теореме о равномощности баз [math]|B_2|\gt |B_1 \setminus b_1|[/math].
Значит по третьей аксиоме определения матроида [math]\exists b_2 \in B_2 [/math] такой, что [math](B_1 \setminus b_1) \cup b_2 \in I[/math].
А так как [math]|(B_1 \setminus b_1) \cup b_2| = |B_1| \:[/math] и [math]B_1[/math] — база, то [math](B_1 \setminus b_1) \cup b_2 \in \mathcal{B}[/math], что и требовалось доказать. |
| [math]\triangleleft[/math] |
