308
правок
Изменения
Дописано доказательство про эквивалентность; лемма про дополнение до базы внесена внутрь
|definition=
'''Двойственный матроид''' к <tex> M = \; \langle X, I \rangle</tex> {{---}} это матроид <tex>M^* = \langle X, I^* \rangle</tex>, где <tex>I^* = \{A\ |\ \exists B \in \mathcal B: A \cap B = \varnothing\}</tex>
}}
Требуется показать, что <tex> I_1 = I_2 </tex>
* <tex> A \in I_1 \Rightarrow A \in I_2 </tex>
*: Дополним Покажем от противного, что <tex> \exists B \in \mathcal B: A \in B </tex> до базы (.*:: Предположим <tex> B C \in I </tex> - множество максимального размера среди таких, что <tex> A \in C </tex>, причём <tex> C </tex>)не база. Возмём также какое-нибудь <tex>B \in I_1 \Rightarrow mathcal B</tex>. *:: Раз <tex> C </tex> не база, то <tex> |C| < |B| </tex>. В таком случае по 3-ему свойству матроида <tex> \exists b \overline in B : C \cap b \in I </tex>. Поскольку Получили противоречие, поскольку <tex> B C \cap \overline b </tex> имеет большую мощность чем <tex> C </tex>.*: Итак, возьмём базу <tex> B = \varnothing </tex>, то включающую в себя <tex> A </tex>. По '''определению 1''' <tex> B \in I_2 \mathcal B_1 \Rightarrow \overline B \in \mathcal B </tex>. Так как Поскольку <tex> B \cap \overline B = \varnothing, A \in B </tex>, то <tex> A \cap \overline B = \varnothing </tex> . В таком случае по '''определению 2''' <tex> A \in I_2 </tex>
* <tex> A \in I_2 \Rightarrow A \in I_1 </tex>
*: Возьмём Раз <tex> A \in I_2 </tex>, то <tex> \exists B \in \mathcal B: A \cap B = \varnothing </tex>. Тогда верно <tex> A \subseteq \overline B </tex>. Заметим что поскольку <tex> B \in I_1\mathcal B </tex>,то <tex> \ I_2 overline B \in \mathcal B_1 </tex>. , то есть тогда <tex> A \in subseteq \overline B \Rightarrow A in \mathcal B_1 \in subseteq I_1</tex>
}}
