В математике двудольный матроид - это матроид, все схемы которого имеют одинаковый размер.
Пример
Равномерный матроид двудольна тогда и только тогда, когда - нечетное число, поскольку схемы в таком матроиде имеют размер .
Связь с двудольными графами
Двудольные матроиды были определены Уэлшем (1969) как обобщение двудольных графов , графов, в которых каждый цикл имеет четный размер. Графический матроид двудольный тогда и только тогда , когда он приходит из двудольного графа. [1]
Двойственность с эйлеровыми матроидами
Эйлерово график является тот , в котором все вершины имеют четную степень; Графы Эйлера могут быть отключены. Для плоских графов свойства двудольности и эйлеровости двойственны: плоский граф двудольный тогда и только тогда, когда его дуальный граф эйлеров. Как показал Уэлш, эта двойственность распространяется на бинарные матроиды : бинарный матроид является двудольным тогда и только тогда, когда его двойственный матроид является эйлеровым матроидом , матроидом, который может быть разделен на непересекающиеся схемы.
Для матроидов, которые не являются бинарными, двойственность между эйлеровыми и двудольными матроидами может нарушиться. Например, однородный матроид не является двудольным, но двойственным эйлерово, так как его можно разбить на два 3-цикла. Самодуальный однородный матроид является двудольным, но не эйлеровым.
Вычислительная сложность
Можно проверить за полиномиальное время , является ли данный двоичный матроид двудольным. [2] Однако любой алгоритм, который проверяет, является ли данный матроид эйлеровым, при условии доступа к матроиду через оракул независимости , должен выполнять экспоненциальное количество запросов оракула и, следовательно, не может занимать полиномиальное время. [3]
Рекомендации
- ^ Валлийский, DJA (1969), "Эйлера и двудольные матроиды", Журнал комбинаторной теории , 6 (4): 375-377, DOI : 10.1016 / s0021-9800 (69) 80033-5 , МР 0237368.
- ^ Ловас, Ласло ; Seress, Ákos (1993), "Коцикл решетка бинарных матроидов", Европейский журнал Комбинаторика , 14 (3): 241-250, DOI : 10,1006 / eujc.1993.1027 , МР 1215334.
- ^ Jensen, Per M .; Корте, Бернхард (1982), "Сложность алгоритмов матроидных собственности", SIAM журнал по вычислениям , 11 (1): 184-190, DOI : 10,1137 / 0211014 , МР 0646772.