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

В теории матроида — двойник матроида. $M$ это еще один матроид $M^{\ast }$ который имеет те же элементы, что и $M$ , и в котором множество независимо тогда и только тогда, когда $M$ имеет непересекающийся с ним базисный набор. ^{[ 1 ]}^{[ 2 ]}^{[ 3 ]}

Двойные матроиды восходят к оригинальной статье Хасслера Уитни, определяющей матроиды. ^{[ 4 ]} Они обобщают на матроиды понятия двойственности плоского графа .

Основные свойства

Двойственность — это инволюция : для всех $M$ , $(M^{\ast })^{\ast }=M$ . ^{[ 1 ]}^{[ 3 ]}^{[ 4 ]}

Альтернативное определение двойственного матроида состоит в том, что его базисные наборы являются дополнениями к базисным наборам $M$ . Аксиома обмена базисами, используемая для определения матроидов по их базам, является самодополняющей, поэтому двойственный матроид обязательно является матроидом. ^{[ 3 ]}

Квартиры $M$ дополняют циклические множества (объединения схем) $M^{\ast }$ , и наоборот. ^{[ 3 ]}

Если $r$ это ранговая функция матроида $M$ на земле $E$ , то ранговая функция двойственного матроида равна $r^{\ast }(S)=r(E\setminus S)+|S|-r(E)$ . ^{[ 1 ]}^{[ 3 ]}^{[ 4 ]}

Несовершеннолетние

формируется Младший матроид из более крупного матроида. $M$ двумя операциями: ограничением $M\setminus x$ удаляет элемент $x$ от $M$ без изменения независимости или ранга остальных множеств, а сокращение $M/x$ удаляет $x$ от $M$ после вычитания единицы из ранга каждого множества, которому оно принадлежит. Эти две операции двойственны: $M\setminus x=(M^{\ast }/x)^{\ast }$ и $M/x=(M^{\ast }\setminus x)^{\ast }$ . Таким образом, минор дуала — это то же самое, что дуал минора. ^{[ 5 ]}

Самодуальные матроиды

Отдельный матроид является самодвойственным (обобщающим, например, самодвойственные многогранники для графических матроидов), если он изоморфен своему собственному двойственному. Изоморфизм может, но не обязан, оставлять элементы матроида фиксированными. Любой алгоритм, который проверяет, является ли данный матроид самодвойственным, при наличии доступа к матроиду через оракул независимости , должен выполнять экспоненциальное количество запросов оракула и, следовательно, не может занимать полиномиальное время. ^{[ 6 ]}

Семьи матроидов

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

Бинарные матроиды (матроиды, представимые в GF(2) ), матроиды, представимые в любом другом поле, и регулярные матроиды — все самодуальные семейства. ^{[ 7 ]}
Гаммоиды . образуют самодуальное семейство Строгие гаммоиды двойственны трансверсальным матроидам . ^{[ 8 ]}
Однородные матроиды и матроиды разбиения самодвойственны. Двойник однородного матроида $U{}_{n}^{r}$ это универсальный матроид $U{}_{n}^{n-r}$ . ^{[ 9 ]}
Двойник графического матроида сам по себе является графическим тогда и только тогда, когда лежащий в его основе граф планарен; матроид двойственного планарному графу такой же, как и двойственный матроиду графа. Таким образом, семейство графических матроидов планарных графов самодуально. ^{[ 10 ]}
Среди графических матроидов и, в более общем смысле, среди бинарных матроидов, двудольные матроиды (матроиды, в которых каждая схема четна) двойственны эйлеровым матроидам (матроиды, которые можно разбить на непересекающиеся схемы). ^{[ 11 ]}^{[ 12 ]}

Вопрос о том, является ли семейство алгебраических матроидов самодуальным, остается открытым.

Если V — векторное пространство и V * — его дополнение , то линейный матроид V V и линейный матроид ортогональное * двойственны. Как следствие, двойник любого линейного матроида является линейным матроидом. ^{[ 13 ]}

Ссылки

^ Перейти обратно: ^а ^б ^с Шрийвер, Александр (2003), Комбинаторная оптимизация: многогранники и эффективность. Том. B: Матроиды, деревья, устойчивые множества , алгоритмы и комбинаторика, том. 24, Берлин: Springer-Verlag, с. 652, ISBN 3-540-44389-4 , МР 1956925 .
^ Уэлш, DJA (2010), Теория Матроидов , Courier Dover Publications, стр. 34, ISBN 9780486474397 .
^ Перейти обратно: ^а ^б ^с ^д ^и Оксли, Джеймс Г. (2006), Теория матроидов , Тексты для выпускников Оксфорда по математике, том. 3, Oxford University Press, стр. 69–70, ISBN. 9780199202508 .
^ Перейти обратно: ^а ^б ^с Уитни, Хасслер (1935), «Об абстрактных свойствах линейной зависимости», American Journal of Mathematics , 57 (3), The Johns Hopkins University Press: 509–533, doi : 10.2307/2371182 , hdl : 10338.dmlcz/100694 , АЭСТОР 2371182 , МР 1507091 . Перепечатано в Kung (1986) , стр. 55–79. См., в частности, раздел 11 «Двойные матроиды», стр. 521–524.
^ Писатель (2003) , с. 653.
^ Дженсен, Пер М.; Корте, Бернхард (1982), «Сложность алгоритмов свойств матроидов», SIAM Journal on Computing , 11 (1): 184–190, doi : 10.1137/0211014 , MR 0646772 .
^ Уитни (1935) , Раздел 13, «Ортогональные гиперплоскости и двойственные матроиды».
^ Писатель (2003) , стр. 659–661; Валлийский (2010) , стр. 222–223.
^ Оксли (2006) , стр. 77 и 111.
^ Тутте, WT (1965), «Лекции по матроидам» , Журнал исследований Национального бюро стандартов , 69B : 1–47, doi : 10.6028/jres.069b.001 , MR 0179781 .
^ Уэлш, DJA (1969), «Эйлер и двудольные матроиды», Journal of Combinatorial Theory , 6 (4): 375–377, doi : 10.1016/s0021-9800(69)80033-5 , MR 0237368 .
^ Харари, Фрэнк ; Уэлш, Доминик (1969), «Матроиды против графов», «Многие аспекты теории графов» (Proc. Conf., Western Mich. Univ., Каламазу, Мичиган, 1968) , Конспекты лекций по математике, том. 110, Берлин: Springer, стр. 155–170, doi : 10.1007/BFb0060114 , ISBN. 978-3-540-04629-5 , МР 0263666 .
^ Федерико, Ардила (2012). «Матроиды, лекция 9» .

Цитируемые работы

Кунг, Джозеф ПСв, изд. (1986), Справочник по теории матроидов , Бостон: Birkhäuser, doi : 10.1007/978-1-4684-9199-9 , ISBN 978-0-8176-3173-4 , МР 0890330 .

[s03-1] Перейти обратно: ^а ^б ^с Шрийвер, Александр (2003), Комбинаторная оптимизация: многогранники и эффективность. Том. B: Матроиды, деревья, устойчивые множества , алгоритмы и комбинаторика, том. 24, Берлин: Springer-Verlag, с. 652, ISBN 3-540-44389-4 , МР 1956925 .

[2] Уэлш, DJA (2010), Теория Матроидов , Courier Dover Publications, стр. 34, ISBN 9780486474397 .

[oxley-3] Перейти обратно: ^а ^б ^с ^д ^и Оксли, Джеймс Г. (2006), Теория матроидов , Тексты для выпускников Оксфорда по математике, том. 3, Oxford University Press, стр. 69–70, ISBN. 9780199202508 .

[w35-4] Перейти обратно: ^а ^б ^с Уитни, Хасслер (1935), «Об абстрактных свойствах линейной зависимости», American Journal of Mathematics , 57 (3), The Johns Hopkins University Press: 509–533, doi : 10.2307/2371182 , hdl : 10338.dmlcz/100694 , АЭСТОР 2371182 , МР 1507091 . Перепечатано в Kung (1986) , стр. 55–79. См., в частности, раздел 11 «Двойные матроиды», стр. 521–524.

[5] Писатель (2003) , с. 653.

[6] Дженсен, Пер М.; Корте, Бернхард (1982), «Сложность алгоритмов свойств матроидов», SIAM Journal on Computing , 11 (1): 184–190, doi : 10.1137/0211014 , MR 0646772 .

[7] Уитни (1935) , Раздел 13, «Ортогональные гиперплоскости и двойственные матроиды».

[8] Писатель (2003) , стр. 659–661; Валлийский (2010) , стр. 222–223.

[9] Оксли (2006) , стр. 77 и 111.

[10] Тутте, WT (1965), «Лекции по матроидам» , Журнал исследований Национального бюро стандартов , 69B : 1–47, doi : 10.6028/jres.069b.001 , MR 0179781 .

[11] Уэлш, DJA (1969), «Эйлер и двудольные матроиды», Journal of Combinatorial Theory , 6 (4): 375–377, doi : 10.1016/s0021-9800(69)80033-5 , MR 0237368 .

[12] Харари, Фрэнк ; Уэлш, Доминик (1969), «Матроиды против графов», «Многие аспекты теории графов» (Proc. Conf., Western Mich. Univ., Каламазу, Мичиган, 1968) , Конспекты лекций по математике, том. 110, Берлин: Springer, стр. 155–170, doi : 10.1007/BFb0060114 , ISBN. 978-3-540-04629-5 , МР 0263666 .

[13] Федерико, Ардила (2012). «Матроиды, лекция 9» .

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]

[ 8 ]

[ 9 ]

[ 10 ]

[ 11 ]

[ 12 ]

[ 13 ]