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

В математической теории матроидов, то ранг матроиды максимального размер независимого множества в матроиде. Ранг подмножества S элементов матроида аналогичным образом является максимальным размером независимого подмножества S, и функция ранга матроида отображает наборы элементов в их ранги.

Функция ранга - одно из фундаментальных понятий теории матроидов, с помощью которого матроиды могут быть аксиоматизированы. Функции ранга матроидов образуют важный подкласс субмодульных функций множества. Ранговые функции матроидов, определенные на основе некоторых других типов математических объектов, таких как неориентированные графы, матрицы и расширения полей, важны при изучении этих объектов.

• 1 Примеры
• 2 Свойства и аксиоматизация
• 3 Прочие свойства матроидов с ранга
• 4 ранга особых матроидов
• 5 Ранговые функции Matroid как функции полезности
• 6 См. Также
• 7 ссылки

Во всех примерах, Е представляет собой базовый набор матроидом и Б некоторое подмножество Е.

• Пусть М будет свободным матроидом, где независимые множества всех подмножеств Е. Тогда функция ранга M просто: r ( B) = | 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.
• Пусть М будет графический матроидом, где независимые множества являются все краевым ациклическим-множество ( лес ) некоторый фиксированным неориентированного графа G. Тогда функция ранга г ( Б) представляет собой число вершин в графе, минус число компонент связности из B (включая компоненты с одной вершиной).

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

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

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

(R 3) Для любого множества и элемента,. ${\ displaystyle A}$${\ displaystyle x}$${\ Displaystyle г (А) \ Leq г (А \ чашка \ {х \}) \ Leq г (А) +1}$

Эти свойства могут использоваться в качестве аксиом для характеристики функции ранга матроидов: каждая целочисленная функция субмодульного множества на подмножествах конечного множества, которая подчиняется неравенствам для всех и является функцией ранга матроида. ${\ Displaystyle г (А) \ Leq г (А \ чашка \ {х \}) \ Leq г (А) +1}$${\ displaystyle A}$${\ displaystyle x}$

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

• Если, то. То есть ранг - это монотонная функция. ${\ Displaystyle A \ подмножество B \ подмножество E}$${\ Displaystyle г (А) \ Leq г (В) \ Leq г (Е)}$
• ${\ Displaystyle г (А) \ leq | А |}$.

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

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

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

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

В абстрактной алгебре, ранг матроида определяется из множества элементов в расширении полого L / K с помощью алгебраической независимости известен как степень трансцендентности.

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

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

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

• Babaioff, Эзра и Feige дизайн детерминированный полиномиальный правдивый механизм, называемый приоритезированных Эгалитарный, который выводит Lorenz доминирующую распределение, которое, следовательно, и EFX 0, максимизирует продукт утилитами, достигает 1/2 дробь доли максиминной, и достигает полного доля максимина, когда оценки являются аддитивными. Со случайными приоритетами этот механизм также не требует зависти. Они также изучают е -дихотомические оценки, в которых предельная полезность либо неположительна, либо находится в диапазоне [1,1+ e ].
• Бенаббу, Чакраборти, Игараси и Зик показывают, что в этой ситуации каждое оптимальное по Парето распределение максимизирует сумму полезностей ( утилитарное благосостояние), а набор распределений, который максимизирует симметричную строго вогнутую функцию f по всем распределениям максимальной суммы, делает это. не зависят от выбора f, и все эти f- максимизирующие выделения являются EF1. Это означает, что распределения max-product являются лексимин-оптимальными распределениями, и все они являются max-sum и EF1. Они также представляют алгоритм с полиномиальным временем, который вычисляет максимальную сумму и распределение EF1 (которое не обязательно максимизирует вогнутую функцию), и алгоритм с полиномиальным временем, который максимизирует вогнутую функцию для особого случая MRF на основе максимальной мощности паросочетание в двудольных графах.

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

• Оракул ранга