308
правок
Изменения
Добавлена лемма про дополнение до базы
|about=1
|definition=
'''Двойственный матроид ''' к <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>
}}
{{Теорема
|statement= Множество <tex>B^*</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= Пусть <tex> A \in I </tex>. Тогда <tex> \exists B \in \mathcal B: A \in B </tex> |proof= Докажем от противного.Пускай <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>.
}}
