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

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 17: Строка 17:
 
3) если <tex>B_1, B_2 \in B_s</tex>, то для <tex>\forall b_1 \in B_1 \: \exists b_2 \in B_2 </tex> такой, что <tex>(B_1 \setminus b_1) \cup b_2 \in B_s</tex>.
 
3) если <tex>B_1, B_2 \in B_s</tex>, то для <tex>\forall b_1 \in B_1 \: \exists b_2 \in B_2 </tex> такой, что <tex>(B_1 \setminus b_1) \cup b_2 \in B_s</tex>.
 
|proof=
 
|proof=
1) Следует из первой аксиомы [[Определение матроида|определения матроида]]; <br>
+
1) Следует из первой аксиомы [[Определение матроида|определения матроида]]. <br>
 
2) Из теоремы о равномощности баз следует, что <tex>B_1 \neg \subset B_2</tex> и <tex>B_2 \neg \subset B_1</tex>.  
 
2) Из теоремы о равномощности баз следует, что <tex>B_1 \neg \subset B_2</tex> и <tex>B_2 \neg \subset B_1</tex>.  
А с условием <tex>B_1 \ne B_2</tex> получаем <tex>B_1 \nsubseteq B_2</tex> и <tex>B_2 \nsubseteq B_1</tex>; <br>
+
А с условием <tex>B_1 \ne B_2</tex> получаем <tex>B_1 \nsubseteq B_2</tex> и <tex>B_2 \nsubseteq B_1</tex>. <br>
3) По второй аксиоме [[Определение матроида|определения матроида]] <tex>(B_1 \setminus b_1) \in I</tex> <br>
+
3) По второй аксиоме [[Определение матроида|определения матроида]] <tex>\forall b_1 \in B_1</tex> верно, что <tex>(B_1 \setminus b_1) \in I</tex>. <br>
 
По теореме о равномощности баз <tex>|B_2|>|B_1 \setminus b_1|</tex>. <br>
 
По теореме о равномощности баз <tex>|B_2|>|B_1 \setminus b_1|</tex>. <br>
 
Значит по третьей аксиоме [[Определение матроида|определения матроида]] <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 B_s</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 B_s</tex>, что и требовалось доказать.
 
}}
 
}}

Версия 06:42, 17 мая 2011

Теорема (о равномощности баз):
Пусть [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]B_s[/math] — семейство его баз. Тогда:

1) [math]B_s \ne \varnothing[/math];
2) если [math]B_1, B_2 \in B_s[/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 B_s[/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 B_s[/math].
Доказательство:
[math]\triangleright[/math]

1) Следует из первой аксиомы определения матроида.
2) Из теоремы о равномощности баз следует, что [math]B_1 \neg \subset B_2[/math] и [math]B_2 \neg \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 B_s[/math], что и требовалось доказать.
[math]\triangleleft[/math]