Изменения

Перейти к: навигация, поиск

Двойственный матроид

37 байт добавлено, 23:29, 5 июня 2014
м
Нет описания правки
|about=1
|definition=
'''Двойственный матроид''' (англ. '''dual matroid''') к <tex> M = \; \langle X, B \rangle</tex> {{---}} это [[Определение_матроида | матроид]] <tex>M^* = \; \langle X, \mathcal B^* \rangle</tex>, где <tex> \mathcal B^* = \; \{ \overline B |\; B \in \mathcal B \} </tex> {{---}} множество всех кобаз матроида <tex>M.</tex>
}}
# Следует из <tex> | \mathcal B | = | \mathcal B^* | </tex>.
# Предположим <tex>\overline B_1, \overline B_2 \in \mathcal B^*, \ \overline B_1 \ne \overline B_2, \ \overline {B_1} \subseteq \overline {B_2} </tex>. Тогда по второй аксиоме баз для <tex> B_{1,2} \ (B_1, B_2 \in \mathcal B):\ \overline {B_1} \subseteq \overline {B_2} \Rightarrow B_2 \subseteq B_1 </tex>, а [[Теорема_о_базах#definition | определение базы]] гласит, что в таком случае <tex> B_1 = B_2, </tex> пришли к противоречию.
# Пусть <tex> \overline{B_1}, \overline {B_2} \in \mathcal B^*</tex> и <tex> p\in \overline{B_1}.</tex>. #: Покажем, что в <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> То есть выполняется третья аксиома баз.
}}
308
правок

Навигация