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

---

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

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

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

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

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

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

---