Dual matroid: различия между версиями

Материал из WEGA
Перейти к навигации Перейти к поиску
(Новая страница: «'''Dual matroid''' --- матроид двойственный For a ''matroid'' <math>{\mathcal M}</math> on a set <math>E</math> with a family <math>{\mathcal …»)
 
Нет описания правки
 
Строка 3: Строка 3:
For a ''matroid'' <math>{\mathcal M}</math> on a set <math>E</math> with a family  <math>{\mathcal  B}</math>  of
For a ''matroid'' <math>{\mathcal M}</math> on a set <math>E</math> with a family  <math>{\mathcal  B}</math>  of
''bases'', another family <math>{\mathcal B}^{\ast}</math> defined by
''bases'', another family <math>{\mathcal B}^{\ast}</math> defined by
<math>{\mathcal B}^{\ast} = \{E \setminus B : B \in {\mathcal B}\}</math>
<math>{\mathcal B}^{\ast} = \{E \setminus B : B \in {\mathcal B}\}</math>
is shown  to  be  the  family  of  bases  of  another  matroid  <math>{\mathcal
is shown  to  be  the  family  of  bases  of  another  matroid  <math>{\mathcal
M}^{\ast}</math> on the same set <math>E</math>, which is called the '''dual matroid'''.
M}^{\ast}</math> on the same set <math>E</math>, which is called the '''dual matroid'''.

Текущая версия от 17:33, 5 апреля 2011

Dual matroid --- матроид двойственный

For a matroid [math]\displaystyle{ {\mathcal M} }[/math] on a set [math]\displaystyle{ E }[/math] with a family [math]\displaystyle{ {\mathcal B} }[/math] of bases, another family [math]\displaystyle{ {\mathcal B}^{\ast} }[/math] defined by

[math]\displaystyle{ {\mathcal B}^{\ast} = \{E \setminus B : B \in {\mathcal B}\} }[/math]

is shown to be the family of bases of another matroid [math]\displaystyle{ {\mathcal M}^{\ast} }[/math] on the same set [math]\displaystyle{ E }[/math], which is called the dual matroid. Obviously, [math]\displaystyle{ ({\mathcal M}^{\ast})^{\ast} = {\mathcal M} }[/math].

A base and a circuit of [math]\displaystyle{ {\mathcal M}^{\ast} }[/math] are called a cobase and a cocircuit of [math]\displaystyle{ {\mathcal M} }[/math], respectively.