Двудольный матроид

В математике двудольный матроид — это матроид , все схемы которого имеют четный размер.

Пример

матроида Униформа $U{}_{n}^{r}$ двудольный тогда и только тогда, когда $r$ – нечетное число, поскольку схемы в таком матроиде имеют размер $r+1$.

Связь с двудольными графами

Двудольные матроиды были определены Уэлшем (1969) как обобщение двудольных графов , графов, в которых каждый цикл имеет четный размер. Графический матроид является двудольным тогда и только тогда, когда он происходит из двудольного графа.

Двойственность с эйлеровыми матроидами

— Эйлеров граф это граф, в котором все вершины имеют четную степень; Эйлеровы графы могут быть несвязными. Для плоских графов свойства двудольности и эйлерова двойственны: планарный граф является двудольным тогда и только тогда, когда его двойственный граф является эйлеровым. Как показал Уэлш, эта двойственность распространяется и на бинарные матроиды : бинарный матроид является двудольным тогда и только тогда, когда его двойственный матроид является эйлеровым матроидом , который можно разбить на непересекающиеся схемы.

Для матроидов, которые не являются бинарными, двойственность между эйлеровыми и двудольными матроидами может нарушиться. Например, универсальный матроид $U{}_{6}^{4}$ не двудольный, но двойственный $U{}_{6}^{2}$ является эйлеровым, так как его можно разбить на два 3-цикла. Самодуальный однородный матроид $U{}_{6}^{3}$ является двудольным, но не эйлеровым.

Вычислительная сложность

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