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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Лемма о циклах)
Строка 40: Строка 40:
 
1) <tex>\exists ! \ C \in A \cup a</tex> — цикл <br>
 
1) <tex>\exists ! \ C \in 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=TBD
+
|proof=
 +
1) Докажем единственность. <br>
 +
Так как <tex>A \cup a \notin I</tex>, найдется цикл <tex>C_1 \subseteq A \cup a</tex>. Пусть существует и другой цикл <tex>C_2 \subseteq A \cup a, C_2 \neq C_1</tex>. <br>
 +
Тогда, так как <tex>A \in I</tex>, <tex> a \in C_1</tex> и <tex>a \in C_2</tex>. Из [[Теорема о циклах|теоремы о циклах]] заключаем, что в таком случае <tex>\exists C</tex> - цикл, <tex>C \subseteq C_1 \cap C_2 \setminus a</tex>. <br>
 +
Но это невозможно, так как <tex>C_1 \cap C_2 \setminus a \subseteq A \in I</tex>, следовательно, предположение неверно, и <tex>C_2 = C_1</tex>.
 +
 
 +
2) Пусть <tex>\exists b \in C</tex>, такой, что <tex>(A \cup a) \setminus b \notin I</tex>. Значит, <tex>(A \cup a) \setminus b</tex> содержит цикл <tex>C' \neq C</tex>. <br> Но тогда его содержит и <tex>A \cup a</tex>, что противоречит пункту 1 леммы. Следовательно, <tex>\forall b \in C, (A \cup a) \setminus b \in I</tex>
 
}}
 
}}
  

Версия 14:41, 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] — матроид, [math]A \in I, a \notin A, A \cup a \notin I[/math]. Тогда:

1) [math]\exists ! \ C \in 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[/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]
TBD
[math]\triangleleft[/math]

См. также

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