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

В математической теории матроидов ранг матроида — это максимальный размер независимого множества в матроиде. Ранг подмножества 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) Для любых двух подмножеств $A$ и $B$ из $E$ , $r(A\cup B)+r(A\cap B)\leq r(A)+r(B)$ . То есть ранг является субмодульной функцией множества .

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

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

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

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

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

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

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

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

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

В линейной алгебре ранг линейного матроида, определяемый линейной независимостью от столбцов матрицы , является рангом матрицы, ^[8] и это также размерность векторного пространства, охватываемого столбцами.

В абстрактной алгебре ранг матроида, определенный из наборов элементов расширения поля L / K посредством алгебраической независимости, известен как степень трансцендентности . ^[9]

ранга Maroid как функции служебные Функции

Функции ранга матроида (MRF) использовались для представления функций полезности агентов в задачах распределения товаров на ярмарке . Если функция полезности агента является MRF, это означает, что:

Полезность агента имеет убывающую отдачу (это следует из того, что MRF является субмодульной функцией);
агента Предельная полезность для каждого предмета является дихотомической (двоичной) - либо 0, либо 1. То есть добавление предмета в набор либо не добавляет никакой полезности, либо добавляет полезность, равную 1.

Для этой настройки известны следующие решения:

Бабайофф, Эзра и Файги ^[10] Разработайте детерминированный правдивый механизм с полиномиальным временем , называемый приоритетным эгалитарным, который выводит доминирующее распределение Лоренца, которое, следовательно, также является EFX ₀ , максимизирует продукт полезностей, достигает 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 .

[1] Шикаре, ММ; Вапаре, Б.Н. (2004), Комбинаторная оптимизация , Alpha Science Int'l Ltd., стр. 155, ISBN 9788173195600 .

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

[o25-3] Jump up to: Перейти обратно: ^а ^б ^с Оксли (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. Соц. Лекционная конспект. Сер., т. 1, с. 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 .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]