В математике равномерный матроид - это матроид, в котором независимые множества - это в точности множества, содержащие не более r элементов для некоторого фиксированного целого числа r . Альтернативное определение состоит в том, что каждая перестановка элементов является симметрией .
Определение
Унифицированный матроид определяется над набором элементы. Подмножество элементов является независимым тогда и только тогда, когда оно содержит не болееэлементы. Подмножество является базовым, если оно имеет ровно элементов, и это схема, если в ней ровно элементы. Оценка подмножества является а ранг матроида . [1] [2]
Матроид ранга равномерно тогда и только тогда, когда все его схемы имеют ровно элементы. [3]
Матроид называется -точечная линия .
Двойственность и несовершеннолетние
Двойной матроидом равномерной матроиду это еще один однородный матроид . Равномерный матроид самодвойственен тогда и только тогда, когда. [4]
Каждый минор однородного матроида однороден. Ограничение однородного матроида на один элемент (до тех пор, пока ) производит матроид и сжимая его на один элемент (до тех пор, пока ) производит матроид . [5]
Реализация
Унифицированный матроид можно представить как матроид аффинно независимых подмножествточки в общем положении в-мерное евклидово пространство , или как матроид линейно независимых подмножеств векторов общего положения в -мерное вещественное векторное пространство .
Каждый равномерный матроид также может быть реализован в проективных пространствах и векторных пространствах над всеми достаточно большими конечными полями . [6] Однако поле должно быть достаточно большим, чтобы включать достаточно независимых векторов. Например,-точная линия может быть реализовано только над конечными полями или больше элементов (потому что в противном случае проективная линия над этим полем имела бы меньше чем точки): не является двоичным матроидом ,не является тернарным матроидом и т. д. По этой причине однородные матроиды играют важную роль в гипотезе Роты о запрещенной минорной характеризации матроидов, которая может быть реализована над конечными полями. [7]
Алгоритмы
Проблема нахождения базиса минимального веса взвешенного однородного матроида хорошо изучена в информатике как проблема выбора . Ее можно решить за линейное время . [8]
Любой алгоритм, который проверяет, является ли данный матроид однородным, при условии доступа к матроиду через оракул независимости , должен выполнять экспоненциальное количество запросов оракула и, следовательно, не может занимать полиномиальное время. [9]
Связанные матроиды
Пока не , однородный матроид связано: это не прямая сумма двух меньших матроидов. [10] Прямая сумма семейства однородных матроидов (не обязательно все с одинаковыми параметрами) называется матроидом разбиения .
Каждый равномерный матроид является мощение матроида , [11] трансверсален матроид [12] и строгим gammoid . [6]
Не каждый однородный матроид является графическим , и однородные матроиды представляют собой наименьший пример неграфического матроида,. Унифицированный матроид графический матроид -реберный дипольный граф , а двойственный однородный матроидявляется графическим матроидом его двойственного графа ,-реберный график цикла . является графическим матроидом графа с петли и графический матроид -крайний лес . Кроме этих примеров, каждый однородный матроид с участием содержит как второстепенный и поэтому не является графическим. [13]
В -point line представляет собой пример матроида Сильвестра, матроида , в котором каждая строка содержит три или более точек. [14]
Смотрите также
Рекомендации
- ^ Оксли, Джеймс Г. (2006), «Пример 1.2.7», Теория матроидов , Oxford Graduate Texts in Mathematics, 3 , Oxford University Press, p. 19, ISBN 9780199202508. Относительно функции ранга см. Стр. 26.
- ^ Валлийский, DJA (2010), Теория матроидов , Courier Dover Publications, стр. 10, ISBN 9780486474397.
- ^ Оксли (2006) , стр. 27.
- Перейти ↑ Oxley (2006) , pp. 77 & 111.
- ↑ Oxley (2006) , стр. 106–107 и 111.
- ^ a b Оксли (2006) , стр. 100.
- Перейти ↑ Oxley (2006) , pp. 202–206.
- ^ Кормен, Томас Х .; Лейзерсон, Чарльз Э .; Ривест, Рональд Л .; Стейн, Клиффорд (2001), «Глава 9: Медианы и статистика порядка», Введение в алгоритмы (2-е изд.), MIT Press и McGraw-Hill, стр. 183–196, ISBN 0-262-03293-7.
- ^ Jensen, Per M .; Корте, Бернхард (1982), "Сложность алгоритмов матроидных собственности", SIAM журнал по вычислениям , 11 (1): 184-190, DOI : 10,1137 / 0211014 , МР 0646772.
- ^ Оксли (2006) , стр. 126.
- Перейти ↑ Oxley (2006 , p. 26).
- ↑ Oxley (2006) , стр. 48–49.
- ↑ Валлийский (2010) , стр. 30.
- ↑ Валлийский (2010) , стр. 297.