Теорема о базах — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Лемма о циклах)
(Сильная теорема о базах дописана)
Строка 32: Строка 32:
 
Значит по третьей аксиоме [[Определение матроида|определения матроида]] <tex>\exists b_2 \in B_2 </tex> такой, что <tex>(B_1 \setminus b_1) \cup b_2 \in I</tex>. <br>
 
Значит по третьей аксиоме [[Определение матроида|определения матроида]] <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>, что и требовалось доказать.
 
А так как <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
 
|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=
 
|statement=
 
Пусть <tex>M = \langle X, I \rangle</tex> — матроид, <tex>A \in I, a \notin A, A \cup a \notin I</tex>. Тогда: <br>
 
Пусть <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>
+
1) <tex>\exists ! \ C \subseteq A \cup a</tex> — цикл <br>
 
2) <tex>\forall b \in C, (A \cup a) \setminus b \in I</tex>
 
2) <tex>\forall b \in C, (A \cup a) \setminus b \in I</tex>
 
|proof=
 
|proof=
Строка 53: Строка 85:
 
|about=
 
|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>
+
|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>
 
такой, что <tex>(B_1 \setminus x) \cup y \in \mathcal{B}</tex> и <tex>(B_2 \setminus y) \cup x \in \mathcal{B}</tex>
|proof=TBD
+
|proof=
 +
Рассмотрим <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>, а значит {{---}} база.
 
}}
 
}}
  

Версия 18:20, 15 июня 2015

Определение:
База (англ. 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]

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


Определение:
Пусть [math]M =\; \langle X,I \rangle[/math]матроид. Тогда замыкание (англ. closure) множества [math]A \subseteq X[/math] — это множество [math]\langle A \rangle \subseteq X[/math] такое, что [math]\langle A \rangle = \mathcal {f} x \in X \; |\; r(A \cup x) = r(A) \mathcal {g}[/math], где [math]r: 2^X \to \mathbb{N}[/math] - ранговая функция


Лемма (о свойствах замыкания):
1) Если [math]A \subseteq B[/math], то [math]\langle A \rangle \subseteq \langle B \rangle[/math]
2) Если [math]e \in \langle A \rangle[/math], то [math]\langle A \cup e \rangle = \langle A \rangle[/math]
Доказательство:
[math]\triangleright[/math]

1) Рассмотрим [math]e \in \langle A \rangle[/math]. По полумодулярности ранговой функции имеем:

[math]r(A \cup e) + r(B) \geqslant r((A \cup e) \cap B) + r(B \cup e) \geqslant r(A) + r(B \cup e)[/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].
В силу произвольности [math]e: \langle A \rangle \subseteq \langle B \rangle[/math].

2) По пункту 1 очевидно, что [math]\langle A \rangle \subseteq \langle A \cup e \rangle[/math]. Докажем обратное: [math]\langle A \cup e \rangle \subseteq \langle A \rangle[/math].
Рассмотрим [math]f \in \langle A \cup e \rangle[/math]. По полумодулярности ранговой функции имеем:

[math]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)[/math].

Но [math]r(A \cup e) = r(A)[/math] (так как [math]e \in \langle A \rangle[/math]), значит, [math]r(A \cup f) \geqslant r(A \cup e \cup f)[/math], что в свою очередь влечет [math]r(A \cup f) = r(A \cup e \cup f)[/math].
Но так как [math]f \in \langle A \cup e \rangle[/math] и [math]e \in \langle A \rangle[/math], [math]r(A) = r(A \cup e) = r(A \cup e \cup f) = r(A \cup f)[/math].
Следовательно, по определению, [math]f \in \langle A \rangle[/math].

В силу произвольности [math]f: \langle A \cup e \rangle \subseteq \langle A \rangle[/math].
[math]\triangleleft[/math]
Лемма (о циклах):
Пусть [math]M = \langle X, I \rangle[/math] — матроид, [math]A \in I, a \notin A, A \cup a \notin I[/math]. Тогда:

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

2) [math]\forall b \in C, (A \cup a) \setminus b \in I[/math]
Доказательство:
[math]\triangleright[/math]

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

2) Пусть [math]\exists b \in C[/math], такой, что [math](A \cup a) \setminus b \notin I[/math]. Значит, [math](A \cup a) \setminus b[/math] содержит цикл [math]C' \neq C[/math].
Но тогда его содержит и [math]A \cup a[/math], что противоречит пункту 1 леммы. Следовательно, [math]\forall b \in C, (A \cup a) \setminus b \in I[/math]
[math]\triangleleft[/math]
Теорема (Сильная теорема о базах):
Пусть [math]M = \langle X, I \rangle[/math] — матроид и [math]\mathcal{B}[/math] — семейство его баз. Тогда [math]\forall B_1, B_2 \in \mathcal{B} : \forall x \in B_1 \setminus B_2 : \exists y \in B_2 \setminus B_1[/math] такой, что [math](B_1 \setminus x) \cup y \in \mathcal{B}[/math] и [math](B_2 \setminus y) \cup x \in \mathcal{B}[/math]
Доказательство:
[math]\triangleright[/math]

Рассмотрим [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], а значит, [math]x \in \langle C \setminus x \rangle[/math].
[math]С \setminus x \subseteq (B_1 \cup C) \setminus x[/math], так что по пункту 1 леммы о замыкании: [math]x \in \langle (B_1 \cap C) \setminus x \rangle[/math].
Тогда по пункту 2 той же леммы имеем: [math]\langle (B_1 \cap C) \setminus x \rangle = \langle B_1 \cap C \setminus x \rangle = X[/math] (т. к. [math]B_1[/math] - база).
Из этого следует, что [math]\exists B'[/math] — база, такая, что [math]B' \subseteq (B \cap C) \setminus x[/math].
Множество [math]B_1 \setminus x [/math] независимо, и [math]|B_1 \setminus x| \lt |B'|[/math], a значит (по 3 аксиоме матроидов): [math]\exists y \in B' \setminus (B_1 \setminus x) : (B_1 \setminus x) \cup y \in \mathcal{B}[/math].
Но [math]B' \setminus (B_1 \setminus x) \subseteq ((B_1 \cup C) \setminus x) \setminus (B_1 \setminus x) \subseteq C \setminus x[/math], следовательно, [math]y \in C \setminus x \subseteq B_2[/math]. Значит, [math]y \in B_2 \setminus B_1[/math], что и требовалось.

Докажем теперь, что [math](B_2 \setminus y) \cup x[/math] — база. Это следует из пункта 2 леммы 2: [math]y \in C \subseteq B_2 \cup x, \; B_2 \cup x \notin I \Rightarrow (B_2 \setminus y) \cup x \in I[/math], а значит — база.
[math]\triangleleft[/math]

См. также

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