Двойной матроид - Dual matroid

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

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

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

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

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

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

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

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

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

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

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

Семейства матроидов

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

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

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

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

1. Шрайвер, Александр (2003), Комбинаторная оптимизация: многогранники и эффективность. Vol. B: Матроиды, деревья, конюшни, Алгоритмы и комбинаторика, 24, Берлин: Springer-Verlag, стр. 652, г. ISBN  3-540-44389-4, МИСТЕР  1956925.
2. Валлийский, Д. Дж. А. (2010), Теория матроидов, Courier Dover Publications, стр. 34, ISBN  9780486474397.
3. Оксли, Джеймс Г. (2006), Теория матроидов, Тексты для выпускников Оксфорда по математике, 3, Oxford University Press, стр. 69–70, ISBN  9780199202508.
4. Уитни, Хасслер (1935), «Об абстрактных свойствах линейной зависимости», Американский журнал математики, Издательство Университета Джона Хопкинса, 57 (3): 509–533, Дои:10.2307/2371182, HDL:10338.dmlcz / 100694, JSTOR  2371182, МИСТЕР  1507091. Перепечатано в Кунг (1986) Ошибка harvtxt: нет цели: CITEREFKung1986 (помощь)С. 55–79. См., В частности, раздел 11 «Двойные матроиды», стр. 521–524.
5. Шрайвер (2003), п. 653.
6. Jensen, Per M .; Корте, Бернхард (1982), "Сложность алгоритмов свойств матроидов", SIAM Журнал по вычислениям, 11 (1): 184–190, Дои:10.1137/0211014, МИСТЕР  0646772.
7. Уитни (1935), Раздел 13, «Ортогональные гиперплоскости и дуальные матроиды».
8. Шрайвер (2003), стр. 659–661; Валлийский (2010) С. 222–223.
9. Оксли (2006), стр.77 и 111.
10. Тутте, У. Т. (1965), «Лекции по матроидам», Журнал исследований Национального бюро стандартов, 69B: 1–47, Дои:10.6028 / jres.069b.001, МИСТЕР  0179781.
11. Валлийский, Д. Дж. А. (1969), «Эйлер и двудольные матроиды», Журнал комбинаторной теории, 6 (4): 375–377, Дои:10.1016 / с0021-9800 (69) 80033-5, МИСТЕР  0237368.
12. Харари, Фрэнк; Валлийский, доминик (1969), «Матроиды против графов», Многогранность теории графов (Proc. Conf., Western Mich. Univ., Kalamazoo, Mich., 1968), Конспект лекций по математике, 110, Берлин: Springer, стр. 155–170, Дои:10.1007 / BFb0060114, ISBN  978-3-540-04629-5, МИСТЕР  0263666.