308
правок
Изменения
Нет описания правки
|proof=
* 1. Пусть <tex>B_1, B_2 \in \mathcal B.</tex> <tex>B_1 \subseteq B_2 \Leftrightarrow \overline {B_1} \supseteq \overline {B_2}.</tex> Тогда по первой аксиоме для <tex>B_{1,2} </tex> <tex>: \ \overline {B_2} = \overline {B_1}.</tex>
* 2. Пусть <tex> \overline{B_1}, \overline {B_2} \in \mathcal B^*</tex> и <tex> p\in \overline{B_1}.</tex> Так как <tex> p\notin {B_1},</tex> то в <tex> B_1 \cup p </tex> имеется точно один цикл <tex>C</tex>. Поскольку цикл <tex>C</tex> не лежит в <tex>B_2</tex>, существует <tex>q \in C \cap \overline {B_2}.</tex> Множество <tex>(B_1 \cup p) \setminus q</tex> не содержит циклов, т.к. разрушен единственный цикл. Поэтому оно независимо и <tex>|(B_1 \cup p) \setminus q| = |B_1|.</tex> Следовательно, <tex> (B_1 \cup p) \setminus q</tex> - база. Тогда <tex>\overline {(B_1 \cup p \setminus q)} = \overline {(B_1 \cup p)} \cup q = (\overline {B_1} \setminus p) \cup q,</tex> где <tex>q \in \overline {B_2}.</tex> То есть выполняется вторая аксиома баз.
}}
|about=2
|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>
}}
|statement=Определения 1 и 2 эквивалентны.
|proof=
* <tex> A \in I_1 \Rightarrow A \in I_2 </tex>
*: Покажем Для начала покажем от противного, что <tex> \exists B \in \mathcal B: \ A \in B </tex>.*:: Предположим <tex> C \in I </tex> - множество максимального размера среди таких, что <tex> A \in C </tex>, причём <tex> C </tex> {{---}} не база. Возмём также какое-нибудь <tex> B \in \mathcal B</tex>. *:: Раз <tex> C </tex> не база, то <tex> |C| < |B| </tex>. В таком случае по [[Определение_матроида | 3-ему свойству матроида ]] <tex> \exists b \in B: \ C \cap b \in I </tex>. Получили противоречие, поскольку <tex> C \cap b </tex> имеет большую мощность чем <tex> C </tex>.*: Итак, возьмём <tex> B </tex> {{---}} базу <tex> B M_1^* </tex> , включающую в себя <tex> A </tex>. По '''определению 1''' <tex>B \in \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 \mathcal B </tex>, то <tex> \Rightarrow \overline B \in \mathcal B_1 </tex>, то есть тогда по определению <tex> M_1^* </tex>. Подытожив вышесказанное можем написать <tex> A \subseteq \overline B \in \mathcal B_1 </tex>, откуда следует <tex> A \subseteq in I_1 </tex>
}}
