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

редактировать

В теории матроидов двоичный матроид является матроидом которые могут быть представлены над конечным полем GF (2). То есть, с точностью до изоморфизма, они представляют собой матроиды, элементы которых являются столбцами (0,1) -матрицы и чьи наборы элементов независимы тогда и только тогда, когда соответствующие столбцы являются линейно независимый в GF (2).

Содержание

1 Альтернативные характеристики
2 Связанные матроиды
3 Дополнительные свойства
4 Ссылки

Альтернативные характеристики

Матроид $M {\ displaystyle M}$ $M$ является двоичным тогда и только тогда, когда

Это матроид, определенный из симметричной (0,1)- матрицы.
Для каждого набора $S { \ displaystyle {\ mathcal {S}}}$ ${\ mathcal {S}}$ схем матроида, симметричная разность схем в $S {\ displaystyle {\ mathcal {S}}}$ ${\ mathcal {S}}$ можно представить как непересекающееся объединение схем.
Для каждой пары схем матроида их симметричная разность содержит другую схему.
Для каждой пары $C, D {\ displaystyle C, D}$ $C, D$ , где $C {\ displaystyle C}$ $C$ - это цепь $M {\ displaystyle M }$ $M$ и $D {\ displaystyle D}$ $D$ представляет собой схему двойного матроида из $M {\ displaystyle M}$ $M$ , $| C ∩ D | {\ displaystyle | C \ cap D |}$ ${\ displaystyle | C \ cap D |}$ - четное число.
Для каждой пары $B, C {\ displaystyle B, C}$ $B, C$ где $B {\ displaystyle B}$ $B$ является основой $M {\ displaystyle M}$ $M$ и $C {\ displaystyle C}$ $C$ представляет собой схему $M {\ displaystyle M}$ $M$ , $C {\ displaystyle C}$ $C$ - симметричную разность основных цепей, индуцированных в $B {\ displaystyle B}$ $B$ элементами $C ∖ B {\ displaystyle C \ setminus B}$ ${\ displaystyle C \ setminus B}$ .
Нет второстепенный матроид из $M {\ displaystyle M}$ $M$ однородный матроид $U 4 2 {\ displaystyle U {} _ {4} ^ {2}}$ $U {} _ {4} ^ {2}$ , четырехточечная линия.
In геометрическая решетка, связанная с матроидом, каждый интервал высоты два имеет не более пяти элементов.

Связанные матроиды

Каждый обычный матроид и каждый графический матроид, является двоичным. Двоичный матроид является правильным тогда и только тогда, когда он не содержит плоскости Фано (семиэлементный нерегулярный двоичный матроид) или его двойника в качестве второстепенного. Двоичный матроид является графическим тогда и только тогда, когда его второстепенные элементы не включают двойник графического матроида $K 5 {\ displaystyle K_ {5}}$ $K_ { 5}$ или $K 3, 3 { \ Displaystyle K_ {3,3}}$ $K_ {3,3}$ . Если каждая схема двоичного матроида имеет нечетную мощность, то все его схемы должны быть не пересекающимися друг с другом; в этом случае он может быть представлен как графический матроид кактусового графа.

Дополнительные свойства

Если $M {\ displaystyle M}$ $M$ является двоичным матроидом, то он двойственен и каждый второстепенный из $M {\ displaystyle M}$ $M$ . Кроме того, прямая сумма двоичных матроидов является двоичной.

Harary Welsh (1969) определяют двудольный матроид как матроид, в котором каждая схема имеет четную мощность, а матроид Эйлера как матроид, в котором элементы можно разбить на непересекающиеся схемы. В классе графических матроидов эти два свойства описывают матроиды двудольных графов и эйлеровых графов (необязательно связных графов, в которых все вершины имеют четную степень) соответственно. Для плоских графов (и, следовательно, также для графических матроидов планарных графов) эти два свойства двойственны: планарный граф или его матроид двудольны тогда и только тогда, когда его двойственный эйлеров. То же самое и с бинарными матроидами. Однако существуют недвоичные матроиды, для которых эта двойственность нарушается.

Любой алгоритм, который проверяет, является ли данный матроид двоичным, при доступе к матроиду через оракул независимости, должен выполнять экспоненциальное количество запросов оракула и, следовательно, не может занять полиномиальное время.

Ссылки