Теорема о базах — различия между версиями
(Новая страница: «{{Теорема |about= о базах |statement= Пусть <tex>B_1</tex> и <tex>B_2</tex> — базы матроида <tex>M</tex>. Тогда <tex>|B_1| = |B…») |
|||
| Строка 4: | Строка 4: | ||
|statement= Пусть <tex>B_1</tex> и <tex>B_2</tex> — базы матроида <tex>M</tex>. Тогда <tex>|B_1| = |B_2|</tex>. | |statement= Пусть <tex>B_1</tex> и <tex>B_2</tex> — базы матроида <tex>M</tex>. Тогда <tex>|B_1| = |B_2|</tex>. | ||
|proof= | |proof= | ||
| − | Докажем от противного. | + | Докажем от противного.Пусть <tex>|B_1| > |B_2|</tex>. Тогда по третьей аксиоме из [[Определение матроида|определения матроида]] <tex>\exists x \in B_1 \setminus B_2</tex> такой, что <tex>B_2 \cup {x} \in I</tex>. То есть <tex>B_2</tex> — не максимальное по включению независимое множество, что противоречит определению базы. |
| − | Пусть <tex>|B_1| > |B_2|</tex>. Тогда по третьей аксиоме из определения матроида <tex>\exists x \in B_1 \setminus B_2</tex> такой, что <tex>B_2 \cup {x} \in I</tex>. То есть <tex>B_2</tex> — не максимальное по включению независимое множество, что противоречит определению базы. | ||
}} | }} | ||
Версия 06:37, 8 мая 2011
| Теорема (о базах): |
Пусть и — базы матроида . Тогда . |
| Доказательство: |
| Докажем от противного.Пусть . Тогда по третьей аксиоме из определения матроида такой, что . То есть — не максимальное по включению независимое множество, что противоречит определению базы. |
