Ранг матроида
В математической теории матроидов ранг матроида — это максимальный размер независимого множества в матроиде. Ранг подмножества S элементов матроида аналогично максимальному размеру независимого подмножества S , а функция ранга матроида отображает множества элементов в их ранги.
Функция ранга — одно из фундаментальных понятий теории матроидов, с помощью которого матроиды могут быть аксиоматизированы. Функции ранга матроида образуют важный подкласс субмодулярных функций множества . Функции ранга матроидов, определенные на основе некоторых других типов математических объектов, таких как неориентированные графы , матрицы и расширения полей, важны при изучении этих объектов.
Примеры [ править ]
Во всех примерах E — базовый набор матроида, а B некоторое подмножество E. —
- Пусть M — свободный матроид , где все независимые множества — это E. подмножества Тогда ранговая функция M просто: r ( B ) = | Б |.
- Пусть M — однородный матроид , где независимые множества — это подмножества E , содержащие не более k элементов, для некоторого целого числа k . Тогда ранговая функция M равна: r ( B ) = min( k , | B |).
- Пусть M — матроид разбиения : элементы E разбиты на категории, каждая категория c имеет емкость k c , а независимыми множествами являются те, которые содержат не более k c элементов категории c . Тогда ранговая функция M равна: r ( B ) = sum c min( k c , | B c |) где B c — подмножество B, содержащееся в категории c .
- Пусть M — графический матроид независимыми множествами являются все ациклические множества ребер ( леса ) некоторого фиксированного неориентированного графа G. , где Тогда функция ранга ( B ) — это количество вершин в графе минус количество компонентов связности B r (включая одновершинные компоненты).
Свойства и аксиоматизация [ править ]
Ранговая функция матроида подчиняется следующим свойствам.
(R1) Значение функции ранга всегда является неотрицательным целым числом , а ранг пустого множества равен 0.
(R2) Для любых двух подмножеств и из , . То есть ранг является субмодульной функцией множества .
(R3) Для любого набора и элемент , .
Эти свойства можно использовать как аксиомы для характеристики ранговой функции матроидов: каждая целочисленная субмодульная функция множества на подмножествах конечного множества, подчиняющаяся неравенствам для всех и — ранговая функция матроида. [1] [2]
Вышеуказанные свойства подразумевают дополнительные свойства:
- Если , затем . То есть ранг является монотонной функцией .
- .
Другие свойства матроидов из ранга [ править ]
Функция ранга может использоваться для определения других важных свойств матроида:
- Множество независимо тогда и только тогда, когда его ранг равен его мощности, и зависимо тогда и только тогда, когда его мощность больше, чем ранг. [3]
- Непустое множество называется схемой, если его мощность равна единице плюс его ранг и каждое подмножество, образованное удалением одного элемента из множества, имеет одинаковый ранг. [3]
- Множество является базисом, если его ранг равен мощности и рангу матроида. [3]
- Множество называется замкнутым, если оно максимально для своего ранга, в том смысле, что не существует другого элемента, который можно добавить к нему, сохранив тот же ранг.
- Разница называется нулевым значением подмножества . Это минимальное количество элементов, которые необходимо удалить из чтобы получить независимый набор. [4]
- Пробка подмножества может относиться как минимум к двум различным величинам: некоторые авторы используют его для обозначения ранга в двойном матроиде, , в то время как другие авторы используют пробку для обозначения разницы .
Звания специальных матроидов [ править ]
В теории графов ранг схемы (или цикломатическое число) графа является корангом соответствующего графического матроида ; он измеряет минимальное количество ребер, которые необходимо удалить из графа, чтобы оставшиеся ребра образовали лес. [5] Несколько авторов изучали параметризованную сложность графовых алгоритмов, параметризованных этим числом. [6] [7]
В линейной алгебре ранг линейного матроида, определяемый линейной независимостью от столбцов матрицы , является рангом матрицы, [8] и это также размерность векторного пространства, охватываемого столбцами.
В абстрактной алгебре ранг матроида, определенный из наборов элементов расширения поля L / K посредством алгебраической независимости, известен как степень трансцендентности . [9]
ранга Maroid как функции служебные Функции
Функции ранга матроида (MRF) использовались для представления функций полезности агентов в задачах распределения товаров на ярмарке . Если функция полезности агента является MRF, это означает, что:
- Полезность агента имеет убывающую отдачу (это следует из того, что MRF является субмодульной функцией);
- агента Предельная полезность для каждого предмета является дихотомической (двоичной) - либо 0, либо 1. То есть добавление предмета в набор либо не добавляет никакой полезности, либо добавляет полезность, равную 1.
Для этой настройки известны следующие решения:
- Бабайофф, Эзра и Файги [10] Разработайте детерминированный правдивый механизм с полиномиальным временем , называемый приоритетным эгалитарным, который выводит доминирующее распределение Лоренца, которое, следовательно, также является EFX 0 , максимизирует продукт полезностей, достигает 1/2-доли максиминной доли и достигает полной максимальной доли при оценках являются аддитивными. Благодаря случайным приоритетам этот механизм также не вызывает зависти . Они также изучают e -дихотомические оценки, в которых предельная полезность либо неположительна, либо находится в диапазоне [1,1+ e ].
- Бенаббу, Чакраборти, Игараси и Зик [11] покажите, что в этой ситуации каждое оптимальное по Парето распределение максимизирует сумму полезностей ( утилитарное благосостояние ), набор распределений, которые максимизируют симметричную строго вогнутую функцию f среди всех распределений с максимальной суммой, не зависит от выбора f , и все эти f -максимизирующие распределения являются EF1. Это означает, что распределения максимального продукта являются лексимин-оптимальными распределениями, и все они представляют собой максимальную сумму и EF1. Они также представляют алгоритм с полиномиальным временем, который вычисляет максимальную сумму и распределение EF1 (который не обязательно максимизирует вогнутую функцию), а также алгоритм с полиномиальным временем, который максимизирует вогнутую функцию для особого случая MRF на основе максимальной мощности. сопоставление в двудольных графах.
Функции матроидного ранга являются подклассом валовых оценок-заменителей .
См. также [ править ]
Ссылки [ править ]
- ^ Шикаре, ММ; Вапаре, Б.Н. (2004), Комбинаторная оптимизация , Alpha Science Int'l Ltd., стр. 155, ISBN 9788173195600 .
- ^ Уэлш, DJA (2010), Теория Матроидов , Courier Dover Publications, стр. 8, ISBN 9780486474397 .
- ^ Jump up to: Перейти обратно: а б с Оксли (2006) , с. 25.
- ^ Оксли (2006) , с. 34.
- ^ Берже, Клод (2001), «Цикломатическое число», Теория графов , Courier Dover Publications, стр. 27–30, ISBN 9780486419756 .
- ^ Копперсмит, Дон ; Вишкин, Узи (1985), «Решение NP-трудных задач в« почти деревьях »: вершинное покрытие», Дискретная прикладная математика , 10 (1): 27–45, doi : 10.1016/0166-218X(85)90057-5 , Збл 0573.68017 .
- ^ Фиала, Иржи; Клокс, Тон; Краточвил, Ян (2001), «Сложность λ-маркировок с фиксированным параметром», Discrete Applied Mathematics , 113 (1): 59–72, doi : 10.1016/S0166-218X(00)00387-5 , Zbl 0982.05085 .
- ^ Оксли, Джеймс Г. (2006), Теория матроидов , Тексты для выпускников Оксфорда по математике, том. 3, Издательство Оксфордского университета, с. 81, ISBN 9780199202508 .
- ^ Линдстрем, Б. (1988), «Матроиды, алгебраические и неалгебраические», Алгебраическая, экстремальная и метрическая комбинаторика, 1986 (Монреаль, PQ, 1986) , London Math. Соц. Лекционная конспект. Сер., т. 1, с. 131, Кембридж: Кембриджский университет. Пресс, стр. 166–174, МР 1052666 .
- ^ Бабаёв, Моше; Эзра, Томер; Файги, Уриэль (27 июля 2020 г.). «Справедливые и правдивые механизмы дихотомических оценок». arXiv : 2002.10704 [ cs.GT ].
- ^ Бенаббу, Наваль; Чакраборти, Митхун; Игараси, Аюми; Зик, Яир (2020). Поиск справедливого и эффективного распределения, когда оценки не сходятся . Конспекты лекций по информатике. Том. 12283. стр. 32–46. arXiv : 2003.07060 . дои : 10.1007/978-3-030-57980-7_3 . ISBN 978-3-030-57979-1 . S2CID 208328700 .