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

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

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

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

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

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

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

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

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

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

;
если [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];
если [math]B_1, B_2 \in \mathcal{B}[/math], то для такой, что .

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

Следует из первой аксиомы определения матроида.
Из теоремы о равномощности баз следует, что [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].
По второй аксиоме определения матроида [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] такой, что .
А так как и [math]B_1[/math] — база, то , что и требовалось доказать.

Сильная теорема о базах

Для доказательства сильной теоремы о базах нам понадобится альтернативное определение оператора замыкания.

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

Пусть — матроид. Тогда замыкание (англ. closure) множества — это множество такое, что , где - ранговая функция

Лемма (о свойствах замыкания):

1. Если , то
2. Если , то

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

Рассмотрим [math]e \in \langle A \rangle[/math]. По полумодулярности ранговой функции имеем:
.
По определению замыкания, [math]r(A \cup e) = r(A)[/math], следовательно, [math]r(B) \geqslant r(B \cup e)[/math], но [math]r(B \cup e) \geqslant r(B)[/math] (по определению ранговой функции), значит,
[math]r(B) = r(B \cup e)[/math], что, в свою очередь, значит, что [math]e \in \langle B \rangle[/math].
В силу произвольности .
По пункту 1 очевидно, что . Докажем обратное: .
Рассмотрим . По полумодулярности ранговой функции имеем:
.
Но [math]r(A \cup e) = r(A)[/math] (так как [math]e \in \langle A \rangle[/math]), значит, , что в свою очередь влечет .
Но так как и [math]e \in \langle A \rangle[/math], .
Следовательно, по определению, [math]f \in \langle A \rangle[/math].
В силу произвольности .

Лемма (о циклах):

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

— цикл

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

Докажем единственность.
Так как [math]A \cup a \notin I[/math], найдется цикл [math]C_1 \subseteq A \cup a[/math]. Пусть существует и другой цикл .
Тогда, так как [math]A \in I[/math], [math] a \in C_1[/math] и [math]a \in C_2[/math]. Из теоремы о циклах заключаем, что в таком случае [math]\exists C[/math] - цикл, .
Но это невозможно, так как , следовательно, предположение неверно, и [math]C_2 = C_1[/math].
Пусть [math]\exists b \in C[/math], такой, что . Значит, [math](A \cup a) \setminus b[/math] содержит цикл [math]C' \neq C[/math].
Но тогда его содержит и [math]A \cup a[/math], что противоречит пункту 1 леммы. Следовательно,

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

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

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

Рассмотрим [math]x \in B_1 \setminus B_2[/math]. Так как [math]B_2[/math] - база, [math]B_2 \cup x \notin I[/math], а значит, по лемме, [math]\exists ! \ C[/math] - цикл, [math]C \subseteq B_2 \sup x[/math], причем [math]x \in C[/math].
Так как [math]C[/math] — цикл, [math]r(C) = r(C \setminus x)[/math], а значит, .
, так что по пункту 1 леммы о замыкании: .
Тогда по пункту 2 той же леммы имеем: (т. к. [math]B_1[/math] - база).
Из этого следует, что [math]\exists B'[/math] — база, такая, что .
Множество [math]B_1 \setminus x [/math] независимо, и , a значит (по 3 аксиоме матроидов): .
Но , следовательно, . Значит, [math]y \in B_2 \setminus B_1[/math], что и требовалось.

Докажем теперь, что — база. Это следует из пункта 2 леммы 2: , а значит — база.

См. также

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

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

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

Сильная теорема о базах

См. также

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

Навигация

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

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

Варианты

Просмотры

Ещё

Поиск

Навигация

Инструменты