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>, что и требовалось доказать.
}}
Для доказательства сильной теоремы о базах нам понадобится альтернативное определение оператора замыкания.
{{Определение
|definition = Пусть <tex>M =\; \langle X,I \rangle</tex> {{---}} [[Определение матроида|матроид]]. Тогда '''замыкание''' (англ. ''closure'') множества <tex>A \subseteq X</tex> {{---}} это множество <tex>\langle A \rangle \subseteq X</tex> такое, что <tex>\langle A \rangle = \mathcal {f} x \in X \; |\; r(A \cup x) = r(A) \mathcal {g}</tex>, где <tex>r: 2^X \to \mathbb{N}</tex> - [[Ранговая_функция,_полумодулярность|ранговая функция]]
}}
{{Лемма
|id=lemma_1
|about=о свойствах замыкания
|statement=
1) Если <tex>A \subseteq B</tex>, то <tex>\langle A \rangle \subseteq \langle B \rangle</tex> <br>
2) Если <tex>e \in \langle A \rangle</tex>, то <tex>\langle A \cup e \rangle = \langle A \rangle</tex>
|proof=
1) Рассмотрим <tex>e \in \langle A \rangle</tex>. По полумодулярности ранговой функции имеем:
<tex>r(A \cup e) + r(B) \geqslant r((A \cup e) \cap B) + r(B \cup e) \geqslant r(A) + r(B \cup e)</tex>.
По определению замыкания, <tex>r(A \cup e) = r(A)</tex>, следовательно, <tex>r(B) \geqslant r(B \cup e)</tex>, но <tex>r(B \cup e) \geqslant r(B)</tex> (по определению ранговой функции), значит, <br>
<tex>r(B) = r(B \cup e)</tex>, что, в свою очередь, значит, что <tex>e \in \langle B \rangle</tex>.<br> В силу произвольности <tex>e: \langle A \rangle \subseteq \langle B \rangle</tex>.
2) По пункту 1 очевидно, что <tex>\langle A \rangle \subseteq \langle A \cup e \rangle</tex>. Докажем обратное: <tex>\langle A \cup e \rangle \subseteq \langle A \rangle</tex>.<br>
Рассмотрим <tex>f \in \langle A \cup e \rangle</tex>. По полумодулярности ранговой функции имеем: <br>
<tex>r(A \cup e) + r(A \cup f) \geqslant r(A \cup e \cup f) + r((A \cup e) \cap (A \cup f)) \geqslant r(A \cup e \cup f) + r(A)</tex>.
Но <tex>r(A \cup e) = r(A)</tex> (так как <tex>e \in \langle A \rangle</tex>), значит, <tex>r(A \cup f) \geqslant r(A \cup e \cup f)</tex>, что в свою очередь влечет <tex>r(A \cup f) = r(A \cup e \cup f)</tex>.<br>
Но так как <tex>f \in \langle A \cup e \rangle</tex> и <tex>e \in \langle A \rangle</tex>, <tex>r(A) = r(A \cup e) = r(A \cup e \cup f) = r(A \cup f)</tex>.<br>
Следовательно, по определению, <tex>f \in \langle A \rangle</tex>.
В силу произвольности <tex>f: \langle A \cup e \rangle \subseteq \langle A \rangle</tex>.
}}
{{Лемма
|id=lemma_2
|about=о циклах
|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 subseteq A \cup a</tex> — цикл <br>
2) <tex>\forall b \in C, (A \cup a) \setminus b \in I</tex>
|proof=
|about=
Сильная теорема о базах
|statement= Пусть <tex>M= \langle X, I \rangle</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Рассмотрим <tex>x \in B_1 \setminus B_2</tex>. Так как <tex>B_2</tex> - база, <tex>B_2 \cup x \notin I</tex>, а значит, по лемме, <tex>\exists ! \ C</tex> - цикл, <tex>C \subseteq B_2 \sup x</tex>, причем <tex>x \in C</tex>.<br>Так как <tex>C</tex> {{---}} цикл, <tex>r(C) = r(C \setminus x)</tex>, а значит, <tex>x \in \langle C \setminus x \rangle</tex>.<br><tex>С \setminus x \subseteq (B_1 \cup C) \setminus x</tex>, так что по пункту 1 леммы о замыкании: <tex>x \in \langle (B_1 \cap C) \setminus x \rangle</tex>.<br>Тогда по пункту 2 той же леммы имеем: <tex>\langle (B_1 \cap C) \setminus x \rangle = \langle B_1 \cap C \setminus x \rangle = X</tex> (т. к. <tex>B_1</tex> - база).<br>Из этого следует, что <tex>\exists B'</tex> {{---}} база, такая, что <tex>B' \subseteq (B \cap C) \setminus x</tex>.<br>Множество <tex>B_1 \setminus x </tex> независимо, и <tex>|B_1 \setminus x| < |B'|</tex>, a значит (по 3 аксиоме матроидов): <tex>\exists y \in B' \setminus (B_1 \setminus x) : (B_1 \setminus x) \cup y \in \mathcal{B}</tex>.<br>Но <tex>B' \setminus (B_1 \setminus x) \subseteq ((B_1 \cup C) \setminus x) \setminus (B_1 \setminus x) \subseteq C \setminus x</tex>, следовательно, <tex>y \in C \setminus x \subseteq B_2</tex>.Значит, <tex>y \in B_2 \setminus B_1</tex>, что и требовалось. Докажем теперь, что <tex>(B_2 \setminus y) \cup x</tex> {{---}} база. Это следует из пункта 2 леммы 2: <tex>y \in C \subseteq B_2 \cup x, \; B_2 \cup x \notin I \Rightarrow (B_2 \setminus y) \cup x \in I</tex>, а значит {{---}} база.
}}
