Изменения

|definition= Пусть дан [[Определение матроида|матроид]] <tex> M = \langle X, I \rangle</tex>. '''Ранговая функция''' (англ. ''rank function'') <tex>r: A \subset in 2^X \to Z_+\mathbb{N}</tex> определяется как: <tex>r(A) = \max \{ |B| : B \subset A, B \in I\}</tex>

Докажем свойство полумодулярности (англ: ''submodularity'') ранговой функции: <tex>\forall A, B \subset X,</tex> <tex>r(A \cup B) + r(A \cap B) \le leqslant r(A) + r(B)</tex>. Для начала небольшая лемма.

|statement= Дан матроид <tex> M = \langle X, I \rangle</tex> и множество <tex>A \subset X</tex>. Пусть также <tex>B \subset A</tex>, <tex>B \in I</tex>, тогда существует <tex>D : B\subset D \subset A, D \in I, |D| = rgr(A)</tex>.

Пусть <tex>E</tex> {{---}} подмножество <tex>A</tex> такое, что <tex>rgr(A) = |E|, E \in I</tex> (по определению ранговой функции такое <tex>E</tex> всегда существует). Предположим, что это не так лемма неверна и максимальное независимое подмножество, которое мы можем получить из <tex>B</tex> добавляя элементы из <tex>A</tex> {{---}} это <tex>C</tex>, причем <tex>|C| < rgr(A)</tex>. Тогда имеем: <tex>C \in I, E \in I, |C| < |E|</tex>, следовательно существует элемент <tex>x \in E \setminus C: C \cup \{x\} \in I</tex>. Заметим также что <tex>|C \cup {x}| = |C| + 1 > |C|</tex> и <tex>x \in A</tex>, т.к. <tex>E \setminus C \subset A</tex>, <tex>B \subset C \subset C \cup \{x\}</tex>. Итак пришли к противоречию, мы получили множество большее по мощности, чем <tex>C</tex> такое, что <tex>B \subset C \subset A, C \in I</tex>, значит исходное предположение было не верно, и мы можем найти множество <tex>D</tex> удовлетворяющее необходимым условиям.

|statement=Пусть дан матроид <tex> M = \langle X, I \rangle</tex>, тогда <tex>\forall A, B \subset X,</tex> <tex>r(A \cup B) + r(A \cap B) \le leqslant r(A) + r(B)</tex>

Рассмотрим множество <tex>D_\cap \subset A \cap B : D_\cap \in I, |D_\cap| = r(A \cap B)</tex>, такое всегда существует по определению <tex>r</tex>. Дополним множество <tex>D_\cap</tex> элементами из <tex>B \setminus D_\cap</tex> до множества <tex>D_B : |D_B| = rg r (B), D_B \in I</tex> (по [[#lemma|лемме]] такое возможно).

Далее дополним <tex>D_B</tex> элементами из <tex>A \cup B \setminus D_B</tex> до множества <tex>D_\cup : |D_\cup| = rgr(A \cup B), D_\cup \in I</tex>. Заметим, что на последнем шаге будут добавляться только элемента из <tex>A</tex>, т.к. пусть на том этапе мы взяли <tex>x \in B</tex>, тогда <tex>\{x\} \cup D_B \subset D_\cup, D_\cup \in I </tex>, следовательно <tex>\{x\} \cup D_B \in I</tex> (по [[Определение матроида|определению матроида]]), а также<tex>|\{x\} \cup D_B| = |D_B| + 1 = r(B) + 1</tex>, что невозможно по определению <tex>r</tex>.

(по [[Определение матроида|определению матроида]]), значит (по определению ранговой функции):

<tex>r(A) \ge geqslant |(D_\cup \setminus D_B) \cup D_\cap| = |D_\cup| - |D_B| + |D_\cap|</tex>

<tex>r(A) + r(B) \ge geqslant r(A \cup B) + r(A \cap B) </tex> }} 

Что ==Теорема о рангах=={{Теорема|id=theorem|statement=Пусть дан матроид <tex> M = \langle X, I \rangle</tex>, и требовалось доказать<tex>r: A \in 2^X \to \mathbb{N}</tex> {{---}} его ранговая функция. Тогда для любых <tex>A, B \subseteq 2^X</tex> выполняется следующее:#<tex> 0 \leqslant r(A) \leqslant |A| </tex> #<tex> A \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= #Очевидно из определения: максимальное независимое подмножество по мощности не может быть больше самого множества и меньше нуля.#Пусть <tex>C \subseteq A</tex> {{---}} максимальное независимое подмножество. Т.к. <tex>A \subseteq B</tex>, то <tex>C \subseteq B</tex> {{---}} независимое подмножество. Поэтому <tex>r(B) \geqslant |C|</tex> по определению, а значит <tex>r(B) \geqslant r(A)</tex>#Доказано выше.