Dual matroid

Материал из WikiGrapp
Версия от 17:33, 5 апреля 2011; Glk (обсуждение | вклад)
(разн.) ← Предыдущая версия | Текущая версия (разн.) | Следующая версия → (разн.)

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.