32
правки
Изменения
Исправил русскую "С" на
{{Определение
|id=definition
|definition=
'''База''' (англ. ''base'') — максимальное по включению независимое множество. То есть
<tex>B \in I</tex> — база, если <tex> \forall A \in I : B \subseteq A \Rightarrow A = B </tex>.
}}
{{Теорема
|about=
{{Теорема
|id=base_theorem
|about=
о базах
|statement= Пусть <tex>M</tex> — матроид и <tex>B_s\mathcal{B}</tex> — семейство его баз. Тогда: <br> 1) # <tex>B_s \mathcal{B} \ne \varnothing</tex>;<br>2) # если <tex>B_1, B_2 \in B_s\mathcal{B}</tex> и <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, B_2 \in B_s\mathcal{B}</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\mathcal{B}</tex>.
|proof=
}}
{{Теорема
|id=strong_base_theorem
|about=
Сильная теорема о базах
|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>
|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 \cup x</tex>, причем <tex>x \in C</tex>. (см. пункт 3 [[Двойственный_матроид|теоремы о двойственном матроиде]])<br>
Так как <tex>C</tex> {{---}} цикл, <tex>r(C) = r(C \setminus x)</tex>, а значит, <tex>x \in \langle C \setminus x \rangle</tex>.<br>
<tex>C \setminus x \subseteq (B_1 \cup C) \setminus x</tex>, так что по 1 свойству [[Оператор замыкания для матроидов|оператора замыкания]]: <tex>x \in \langle (B_1 \cap C) \setminus x \rangle</tex>.<br>
Тогда по 3 свойству [[Оператор замыкания для матроидов|оператора замыкания]] имеем: <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> {{---}} база. Пусть это не так, тогда <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> {{---}} база.
}}
== См. также ==
* [[Аксиоматизация матроида базами]]
* [[Теорема о циклах]]
* [[Аксиоматизация матроида циклами]]
== Источники информации ==
* [https://courses.engr.illinois.edu/cs598csc/sp2010/Lectures/Lecture14.pdf Chandra Chekuri: Combinatorial Optimization, Lecture 14 - Introduction to Matroids]
* [https://courses.engr.illinois.edu/cs598csc/sp2010/Lectures/Lecture16.pdf Chandra Chekuri: Combinatorial Optimization, Lecture 16 - Base Exchange Properties]
* [http://math.mit.edu/~goemans/18438F09/lec11.pdf Michel X. Goemans: Advanced Combinatorial Optimization, Lecture 11: Matroid Intersection]
[[Категория:Алгоритмы и структуры данных]]
[[Категория:Матроиды]]
