97
правок
Изменения
→Теорема о рангах
{{Определение
|definition= Пусть дан [[Определение матроида|матроид]] <tex> M = \langle X, I \rangle</tex>. '''Ранговая функция''' (англ: . ''rank function'') <tex>r: A \in 2^X \to \mathbb{N}</tex> определяется как: <tex>r(A) = \max \{ |B| : B \subset A, B \in I\}</tex>
}}
{{Теорема
|id=theorem
|statement=Пусть дан матроид <tex> M = \langle X, I \rangle</tex>, и <tex>r: A \in 2^X \to \{0\} \cup \mathbb{N}</tex> {{---}} его ранговая функция. Тогда для любых <tex>A, B \subseteq 2^X</tex> выполняется следующее:
#<tex> 0 \leqslant r(A) \leqslant |A| </tex>
#<tex> A \in subseteq B \Rightarrow r(A) \leqslant r(B) </tex>
#Неравенство полумодулярности: <tex>\forall A, B \subset X,</tex> <tex>r(A \cup B) + r(A \cap B) \leqslant r(A) + r(B)</tex>
|proof=
