Теорема о базах

Определение:

База (англ. base) — максимальное по включению независимое множество. То есть — база, если .

Теорема (о равномощности баз):

Пусть и — базы матроида . Тогда .

Доказательство:

Доказательство от противного. Пусть [math]|B_1| \gt |B_2|[/math]. Тогда по третьей аксиоме определения матроида такой, что [math]B_2 \cup {x} \in I[/math]. То есть [math]B_2[/math] — не максимальное по включению независимое множество, что противоречит определению базы.

Случай разбирается аналогично.

Теорема (о базах):

Пусть — матроид и — семейство его баз. Тогда:

1) ;
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) если , то для такой, что .

Доказательство:

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]\exists b_2 \in B_2 [/math] такой, что .

А так как и — база, то , что и требовалось доказать.

Лемма:

Пусть — матроид, . Тогда:

1) [math]\exists ! \ C \in A \cup a[/math] — цикл

2)

Доказательство:

TBD

Теорема (Сильная теорема о базах):

Пусть — матроид и — семейство его баз. Тогда такой, что и

Доказательство:

TBD

См. также

Аксиоматизация матроида базами

Источники информации

Теорема о базах

См. также

Источники информации

Навигация

Персональные инструменты

Пространства имён

Варианты

Просмотры

Ещё

Поиск

Навигация

Инструменты