Материал из Викиконспекты
|
|
| (не показаны 2 промежуточные версии 2 участников) |
| Строка 46: |
Строка 46: |
| | Значит, <tex>y \in B_2 \setminus B_1</tex>, что и требовалось. | | Значит, <tex>y \in B_2 \setminus B_1</tex>, что и требовалось. |
| | | | |
| − | Докажем теперь, что <tex>(B_2 \setminus y) \cup x</tex> {{---}} база. Пусть это не так, тогда <tex>\exists C'</tex> - цикл, <tex>C \subseteq (B_2 \setminus y) \cup x</tex>, причем <tex>С' \ne C</tex>, ведь <tex>y \in C</tex>. Но мы уже установили, что <tex>C</tex> {{---}} единственный цикл в <tex>B_2 \cup x</tex> {{---}} противоречие. Значит, <tex>(B_2 \setminus y) \cup x</tex> {{---}} база. | + | Докажем теперь, что <tex>(B_2 \setminus y) \cup x</tex> {{---}} база. Пусть это не так, тогда <tex>\exists C'</tex> - цикл, <tex>C \subseteq (B_2 \setminus y) \cup x</tex>, причем <tex>C' \ne C</tex>, ведь <tex>y \in C</tex>. Но мы уже установили, что <tex>C</tex> {{---}} единственный цикл в <tex>B_2 \cup x</tex> {{---}} противоречие. Значит, <tex>(B_2 \setminus y) \cup x</tex> {{---}} база. |
| | }} | | }} |
| | | | |
Текущая версия на 19:15, 4 сентября 2022
| Определение: |
| База (англ. 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] — семейство его баз. Тогда:
- [math]\mathcal{B} \ne \varnothing[/math];
- если [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];
- если [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] |
- Следует из первой аксиомы определения матроида.
- Из теоремы о равномощности баз следует, что [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].
- По второй аксиоме определения матроида [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]\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 \cup x[/math], причем [math]x \in C[/math]. (см. пункт 3 теоремы о двойственном матроиде)
Так как [math]C[/math] — цикл, [math]r(C) = r(C \setminus x)[/math], а значит, [math]x \in \langle C \setminus x \rangle[/math].
[math]C \setminus x \subseteq (B_1 \cup C) \setminus x[/math], так что по 1 свойству оператора замыкания: [math]x \in \langle (B_1 \cap C) \setminus x \rangle[/math].
Тогда по 3 свойству оператора замыкания имеем: [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] — база. Пусть это не так, тогда [math]\exists C'[/math] - цикл, [math]C \subseteq (B_2 \setminus y) \cup x[/math], причем [math]C' \ne C[/math], ведь [math]y \in C[/math]. Но мы уже установили, что [math]C[/math] — единственный цикл в [math]B_2 \cup x[/math] — противоречие. Значит, [math](B_2 \setminus y) \cup x[/math] — база. |
| [math]\triangleleft[/math] |
См. также
Источники информации
