Матроид ранг - Matroid rank

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

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

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

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

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

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

Прочие свойства матроидов из ранга

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

• Набор является независимым тогда и только тогда, когда его ранг равен его мощности, и зависимым тогда и только тогда, когда он имеет большую мощность, чем ранг.^[3]
• Непустое множество - это схема, если ее мощность равна единице плюс ее ранг, и каждое подмножество, образованное удалением одного элемента из набора, имеет равный ранг.^[3]
• Набор является базисом, если его ранг равен его мощности и рангу матроида.^[3]
• Набор закрывается, если он максимальный для его ранга, в том смысле, что не существует другого элемента, который можно было бы добавить к нему при сохранении того же ранга.
• Разница ${\displaystyle |A|-r(A)}$ называется ничтожность подмножества ${\displaystyle A}$. Это минимальное количество элементов, которые необходимо удалить из ${\displaystyle A}$ чтобы получить независимый набор.^[4]
• В кокон подмножества ${\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]

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

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

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

1. Шикаре, М. М .; Waphare, Б. Н. (2004), Комбинаторная оптимизация, Alpha Science Int'l Ltd., стр. 155, ISBN  9788173195600.
2. Валлийский, Д. Дж. А. (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, Дои:10.1016 / 0166-218X (85) 90057-5, Zbl  0573.68017.
7. Фиала, Иржи; Клокс, Тон; Кратохвил, Ян (2001), "Сложность λ-разметки с фиксированными параметрами", Дискретная прикладная математика, 113 (1): 59–72, Дои:10.1016 / S0166-218X (00) 00387-5, Zbl  0982.05085.
8. Оксли, Джеймс Г. (2006), Матроид Теория, Тексты для выпускников Оксфорда по математике, 3, Oxford University Press, стр. 81, ISBN  9780199202508.
9. Линдстрем Б. (1988), "Матроиды, алгебраические и неалгебраические", Алгебраическая, экстремальная и метрическая комбинаторика, 1986 (Montreal, PQ, 1986), Лондонская математика. Soc. Lecture Note Ser., 131, Кембридж: Cambridge Univ. Press, стр. 166–174, Г-Н  1052666.