Jump to content

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

В математической теории матроидов ранг матроида — это максимальный размер независимого множества в матроиде. Ранг подмножества 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 на основе максимальной мощности. сопоставление в двудольных графах.

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

См. также [ править ]

Ссылки [ править ]

  1. ^ Шикаре, ММ; Вапаре, Б.Н. (2004), Комбинаторная оптимизация , Alpha Science Int'l Ltd., стр. 155, ISBN  9788173195600 .
  2. ^ Уэлш, DJA (2010), Теория Матроидов , Courier Dover Publications, стр. 8, ISBN  9780486474397 .
  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 .
Arc.Ask3.Ru: конец переведенного документа.
Arc.Ask3.Ru
Номер скриншота №: 964dd18f08d820955452eda717e71bfa__1695292080
URL1:https://arc.ask3.ru/arc/aa/96/fa/964dd18f08d820955452eda717e71bfa.html
Заголовок, (Title) документа по адресу, URL1:
Matroid rank - Wikipedia
Данный printscreen веб страницы (снимок веб страницы, скриншот веб страницы), визуально-программная копия документа расположенного по адресу URL1 и сохраненная в файл, имеет: квалифицированную, усовершенствованную (подтверждены: метки времени, валидность сертификата), открепленную ЭЦП (приложена к данному файлу), что может быть использовано для подтверждения содержания и факта существования документа в этот момент времени. Права на данный скриншот принадлежат администрации Ask3.ru, использование в качестве доказательства только с письменного разрешения правообладателя скриншота. Администрация Ask3.ru не несет ответственности за информацию размещенную на данном скриншоте. Права на прочие зарегистрированные элементы любого права, изображенные на снимках принадлежат их владельцам. Качество перевода предоставляется как есть. Любые претензии, иски не могут быть предъявлены. Если вы не согласны с любым пунктом перечисленным выше, вы не можете использовать данный сайт и информация размещенную на нем (сайте/странице), немедленно покиньте данный сайт. В случае нарушения любого пункта перечисленного выше, штраф 55! (Пятьдесят пять факториал, Денежную единицу (имеющую самостоятельную стоимость) можете выбрать самостоятельно, выплаичвается товарами в течение 7 дней с момента нарушения.)