Dual matroid: различия между версиями
Glk (обсуждение | вклад) (Новая страница: «'''Dual matroid''' --- матроид двойственный For a ''matroid'' <math>{\mathcal M}</math> on a set <math>E</math> with a family <math>{\mathcal …») |
Glk (обсуждение | вклад) Нет описания правки |
||
| Строка 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.