В теории матроидов , тем двойственная матроида это еще один матроид который имеет те же элементы, что и , и в котором множество независимо тогда и только тогда, когда имеет не пересекающийся с ней базис. [1] [2] [3]
Дуалы матроидов восходят к исходной статье Хасслера Уитни, определяющей матроиды. [4] Они обобщают на матроиды понятия двойственности плоских графов .
Основные свойства
Двойственность - это инволюция : для всех, . [1] [3] [4]
Альтернативное определение двойственного матроида состоит в том, что его базисные множества являются дополнениями базисных множеств. Аксиома обмена базисом, используемая для определения матроидов по их базам, является самодополнительной, поэтому двойник матроида обязательно является матроидом. [3]
В квартирах из являются дополнительными к циклическим множествам (объединениям схем) , и наоборот. [3]
Если является ранговой функцией матроида на земле установлен , то ранговая функция двойственного матроида равна . [1] [3] [4]
Несовершеннолетние
Матроид минор формируется из большей матроиды двумя операциями: ограничение удаляет элемент из без изменения независимости или ранга остальных наборов, а сокращение удаляет из после вычитания единицы из ранга каждого набора, к которому он принадлежит. Эти две операции двойственны: а также . Таким образом, минор дуала - это то же самое, что дуал минора. [5]
Самодуальные матроиды
Индивидуальный матроид является самодвойственным (обобщающим, например, самодвойственные многогранники для графических матроидов), если он изоморфен своему собственному двойственному. Изоморфизм может, но не обязательно, оставить элементы матроида фиксированными. Любой алгоритм, который проверяет, является ли данный матроид самодвойственным, при условии доступа к матроиду через оракул независимости , должен выполнять экспоненциальное количество запросов оракула и, следовательно, не может занимать полиномиальное время. [6]
Семейства матроидов
Многие важные семейства матроидов являются самодуальными, что означает, что матроид принадлежит к семейству тогда и только тогда, когда его дуал принадлежит. Многие другие семейства матроидов входят в двойные пары. Примеры этого явления включают:
- В бинарных матроиды (матроиды представима над GF (2) ), то матроиды представимых над любой другой области, и регулярные матроиды , все автодуальные семьи. [7]
- В gammoids образуют автодуальную семью. Строгие гаммоиды двойственны поперечным матроидам . [8]
- В равномерных матроидах и перегородки матроиды самодвойственны. Двойник к однородному матроиду равномерный матроид . [9]
- Двойник графического матроида сам по себе является графическим тогда и только тогда, когда лежащий в основе граф плоский; матроид двойственного к плоскому графу такой же, как двойственный к матроиду графа. Таким образом, семейство графических матроидов планарных графов самодуально. [10]
- Среди графических матроидов и, в более общем смысле, среди двоичных матроидов двудольные матроиды (матроиды, в которых каждая схема четная) двойственны эйлеровым матроидам (матроидам, которые могут быть разделены на непересекающиеся схемы). [11] [12]
Вопрос о том, является ли семейство алгебраических матроидов самодуальным, остается открытым .
Если V является векторным пространством и V * является его ортогональным дополнением , то линейный матроид из V и линейный матроид из V * являются двойственными. Как следствие, двойственный к любому линейному матроиду является линейным матроидом. [13]
Рекомендации
- ^ a b c Шрайвер, Александр (2003), Комбинаторная оптимизация: многогранники и эффективность. Vol. B: Матроиды, деревья, стабильные множества , алгоритмы и комбинаторика, 24 , Берлин: Springer-Verlag, стр. 652, ISBN 3-540-44389-4, MR 1956925.
- ^ Валлийский, DJA (2010), Теория матроидов , Courier Dover Publications, стр. 34, ISBN 9780486474397 CS1 maint: обескураженный параметр ( ссылка ).
- ^ а б в г д Оксли, Джеймс Г. (2006), Теория матроидов , Oxford Graduate Texts in Mathematics, 3 , Oxford University Press, стр. 69–70, ISBN 9780199202508 CS1 maint: обескураженный параметр ( ссылка ).
- ^ а б в Уитни, Хасслер (1935), «Об абстрактных свойствах линейной зависимости», Американский журнал математики , издательство Johns Hopkins University Press, 57 (3): 509–533, doi : 10.2307 / 2371182 , hdl : 10338.dmlcz / 100694 , JSTOR 2371182 , Руководство по ремонту 1507091 CS1 maint: обескураженный параметр ( ссылка ). Перепечатано в Kung (1986) С. 55–79. См., В частности, раздел 11 «Двойные матроиды», стр. 521–524.
- ^ Шрайвер (2003) , стр. 653.
- ^ Jensen, Per M .; Корте, Бернхард (1982), "Сложность алгоритмов матроидных собственности", SIAM журнал по вычислениям , 11 (1): 184-190, DOI : 10,1137 / 0211014 , МР 0646772.
- ^ Whitney (1935) , раздел 13, "Ортогональные гиперплоскости и двойственные матроиды".
- ^ Шрайвер (2003) , стр 659-661. Валлийский (2010) , стр. 222–223.
- Перейти ↑ Oxley (2006) , pp. 77 & 111.
- ^ Tutte, WT (1965), "Лекция по матроидам" , Журнал исследований Национального бюро стандартов , 6 : 1-47, DOI : 10,6028 / jres.069b.001 , MR 0179781.
- ^ Валлийский, DJA (1969), "Эйлер и двудольные матроиды", Журнал комбинаторной теории , 6 (4): 375-377, DOI : 10.1016 / s0021-9800 (69) 80033-5 , МР 0237368 CS1 maint: обескураженный параметр ( ссылка ).
- ^ Харари, Фрэнк ; Валлийский, Доминик (1969), «Матроиды против графов», Многогранность теории графов (Proc. Conf., Western Mich. Univ., Kalamazoo, Mich., 1968) , Lecture Notes in Mathematics, 110 , Berlin: Springer, . С. 155-170, DOI : 10.1007 / BFb0060114 , ISBN 978-3-540-04629-5, MR 0263666.
- ^ Федерико, Ардила (2012). «Матроиды, лекция 9» .