308
правок
Изменения
Нет описания правки
#: Покажем, что в <tex> B_1 \cup p </tex> содержится ровно один цикл.
#:: Так как <tex> p\notin {B_1}, </tex> то по определению базы <tex> B_1 \cup p \notin I </tex>, а значит существует цикл <tex>C \subseteq B_1 \cup p </tex>.
#:: Убедимся также, что он единственный. Положим <tex> \exists C_1, C_2 \in \mathfrak {C}: \ C_1, C_2 \subseteq B_1 \cup p,\ C_1 \ne C_2 </tex>. Заметим, что <tex> p \in C_1, C_2 </tex>, в противном случае цикл не содержащий <tex> p </tex> был бы подмножеством <tex> B_1 </tex>, что невозможно. Следовательно по [[Теорема_о_циклах | 3-му свойству циклов]] <tex> \exists C_3 \in \mathfrak {C}: \ C_3 \subseteq (C_1 \cup C_2) \setminus p </tex>. Но помимо этого выполнено <tex> (C_1 \cup C_2) \setminus p \subseteq B_1 </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^* {\circ} = \langle X, I^* {\circ} \rangle</tex>, где <tex>I^* {\circ} = \{A\ |\ \exists B \in \mathcal B: \ A \cap B = \varnothing\}</tex>
}}
{{Теорема
|statement=Определения 1 Матроиды <tex> M^* </tex> и 2 эквивалентны<tex> M^{\circ} </tex> совпадают.
|proof=
*: Для начала покажем от противного, что <tex> \exists B \in \mathcal B: \ A \subseteq B </tex>.
*:: Предположим <tex> S \in I </tex> {{---}} множество максимального размера среди таких, что <tex> A \subseteq S </tex>, причём <tex> S </tex> {{---}} не база. Возмём также какое-нибудь <tex> B \in \mathcal B</tex>.
*:: Раз <tex> S </tex> не база, то <tex> |S| < |B| </tex>. В таком случае по [[Определение_матроида | 3-ей аксиоме матроидов]] <tex> \exists b \in B: \ S \cup b \in I </tex>. Получили противоречие, поскольку <tex> S \cup b </tex> имеет большую мощность чем <tex> S </tex>.
*: Итак, возьмём <tex> B </tex> {{---}} базу <tex> M_1M^* </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 \subseteq B </tex>, то <tex> A \cap \overline B = \varnothing </tex>. В таком случае по '''определению 2''' <tex> A \in I_2 I^{\circ} </tex>.
* <tex> A \in I_2 I^{\circ} \Rightarrow A \in I_1 I^* </tex>*: <tex> A \in I_2 I^{\circ} </tex> означает что <tex> \exists B \in \mathcal B: \ A \cap B = \varnothing </tex>. Последнее можно записать иначе: <tex> A \subseteq \overline B </tex>. *: Кроме того <tex> B \in \mathcal B \Rightarrow \overline B \in \mathcal B_1 </tex> по определению <tex> M_1M^* </tex>. Получили <tex> A \subseteq \overline B \in \mathcal B_1 </tex>, откуда следует <tex> A \in I_1 I^* </tex>.
}}
