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

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

Пример

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

Отношение к двудольным графам

Двудольные матроиды были определены Валлийский (1969) как обобщение двудольные графы, графики, в которых каждый цикл имеет четный размер. А графический матроид является двудольным тогда и только тогда, когда оно происходит от двудольного графа.^[1]

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

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

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

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

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

Рекомендации

1. Валлийский, Д. Дж. А. (1969), «Эйлер и двудольные матроиды», Журнал комбинаторной теории, 6: 375–377, Дои:10.1016 / с0021-9800 (69) 80033-5, МИСТЕР  0237368.
2. Ловас, Ласло; Сересс, Акос (1993), "Решетка коциклов бинарных матроидов", Европейский журнал комбинаторики, 14 (3): 241–250, Дои:10.1006 / eujc.1993.1027, МИСТЕР  1215334.
3. Jensen, Per M .; Корте, Бернхард (1982), "Сложность алгоритмов свойств матроидов", SIAM Журнал по вычислениям, 11 (1): 184–190, Дои:10.1137/0211014, МИСТЕР  0646772.