Ранг матроида

Максимальный размер независимого набора матроида

В математической теории матроидов ранг матроида — это максимальный размер независимого множества в матроиде. Ранг подмножества 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. Тогда функция ранга r ( B ) — это количество вершин в графе минус количество связных компонентов B (включая одновершинные компоненты).

Свойства и аксиоматизация

Ранговая функция матроида подчиняется следующим свойствам.

(R1) Значение функции ранга всегда является неотрицательным целым числом , а ранг пустого множества равен 0.

(R2) Для любых двух подмножеств и из , . То есть ранг является субмодульной функцией множества . ${\displaystyle A}$ ${\displaystyle B}$ ${\displaystyle E}$ ${\displaystyle r(A\cup B)+r(A\cap B)\leq r(A)+r(B)}$

(R3) Для любого множества и элемента , . ${\displaystyle A}$ ${\displaystyle x}$ ${\displaystyle r(A)\leq r(A\cup \{x\})\leq r(A)+1}$

Эти свойства можно использовать как аксиомы для характеристики функции ранга матроидов: каждая целочисленная субмодульная функция множества на подмножествах конечного набора, которая подчиняется неравенствам для всех и является функцией ранга матроида. ^{[1] [2]} ${\displaystyle r(A)\leq r(A\cup \{x\})\leq r(A)+1}$ ${\displaystyle A}$ ${\displaystyle x}$

Вышеуказанные свойства подразумевают дополнительные свойства:

• Если , то . То есть ранг является монотонной функцией . ${\displaystyle A\subset B\subset E}$ ${\displaystyle r(A)\leq r(B)\leq r(E)}$
• ${\displaystyle r(A)\leq |A|}$.

Другие свойства матроида из ранга

Функция ранга может использоваться для определения других важных свойств матроида:

• Множество независимо тогда и только тогда, когда его ранг равен его мощности, и зависимо тогда и только тогда, когда его мощность больше, чем ранг. ^[3]
• Непустое множество называется схемой, если его мощность равна единице плюс его ранг и каждое подмножество, образованное удалением одного элемента из множества, имеет одинаковый ранг. ^[3]
• Множество является базисом, если его ранг равен мощности и рангу матроида. ^[3]
• Множество называется замкнутым, если оно максимально для своего ранга, в том смысле, что не существует другого элемента, который можно добавить к нему, сохранив тот же ранг.
• Разница называется нульностью подмножества . Это минимальное количество элементов, из которого необходимо удалить , чтобы получить независимый набор. ^[4] ${\displaystyle |A|-r(A)}$ ${\displaystyle A}$ ${\displaystyle A}$
• Коранг подмножества может относиться как минимум к двум различным величинам: некоторые авторы используют его для обозначения ранга в двойном матроиде, в то время как другие авторы используют коранг для обозначения разности . ${\displaystyle A}$ ${\displaystyle A}$ ${\displaystyle r^{*}(A)=|A|+r(E\setminus A)-r(E)}$ ${\displaystyle r(E)-r(A)}$

Звания специальных матроидов

В теории графов ранг схемы ( или цикломатическое число) графа является корангом соответствующего графического матроида ; он измеряет минимальное количество ребер, которые необходимо удалить из графа, чтобы оставшиеся ребра образовали лес. ^[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 на основе максимальной мощности. сопоставление в двудольных графах.

Функции матроидного ранга являются подклассом валовых оценок-заменителей .

Смотрите также

• Ранг оракула

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

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