Изменения
Новая страница: «{{Определение |definition= Пусть дан матроид <tex> M = \langle X, I \rangle</tex>. '''Ранг…»
{{Определение
|definition= Пусть дан [[Определение матроида|матроид]] <tex> M = \langle X, I \rangle</tex>. '''Ранговая функция''' <tex>r: A \subset X \to Z_+</tex> определяется как: <tex>r(A) = \max \{ |B| : B \subset A, B \in I\}</tex>
}}
==Полумодулярность ранговой функции==
Докажем свойство полумодулярности ранговой функции: <tex>\forall A, B \subset X,</tex> <tex>r(A \cup B) + r(A \cap B) \le r(A) + r(B)</tex>. Для начала небольшая лемма.
{{Лемма
|id=lemma
|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| = rg(A)</tex>.
|proof=
Пусть <tex>E</tex> {{---}} подмножество <tex>A</tex> такое, что <tex>rg(E) = |E|, E \in I</tex> (по определению ранговой функции такое <tex>E</tex> всегда существует.
Предположим, что это не так и максимальное независимое подмножество, которое мы можем получить из <tex>B</tex> добавляя элементы из <tex>A</tex> {{---}} это <tex>C</tex>, причем <tex>|C| < rg(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> удовлетворяющее необходимым условиям.
}}
Итак теперь мы готовы доказать свойство полумодулярности ранговой функции.
{{Теорема
|id=theorem
|statement=<tex>\forall A, B \subset X,</tex> <tex>r(A \cup B) + r(A \cap B) \le r(A) + r(B)</tex>
|proof=
Рассмотрим множество <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 (B), D_B \in I</tex> (по [[#lemma|лемме]] такое возможно). Далее дополним <tex>D_B</tex> элементами из <tex>A \cup B \setminus D_B</tex> до множества <tex>D_\cup : |D_\cup| = rg(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>(D_\cup \setminus D_B) \cup D_\cap \subset A</tex>, <tex>(D_\cup \setminus D_B) \cup D_\cap \in I</tex> (по [[Определение матроида]]), значит <tex>r(A) \ge |(D_\cup \setminus D_B) \cup D_\cap| = |D_\cup| - |D_B| + |D_\cap| = r(A \cup B) - r(B) + r(A \cap B) </tex>. Что и требовалось доказать.
}}
|definition= Пусть дан [[Определение матроида|матроид]] <tex> M = \langle X, I \rangle</tex>. '''Ранговая функция''' <tex>r: A \subset X \to Z_+</tex> определяется как: <tex>r(A) = \max \{ |B| : B \subset A, B \in I\}</tex>
}}
==Полумодулярность ранговой функции==
Докажем свойство полумодулярности ранговой функции: <tex>\forall A, B \subset X,</tex> <tex>r(A \cup B) + r(A \cap B) \le r(A) + r(B)</tex>. Для начала небольшая лемма.
{{Лемма
|id=lemma
|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| = rg(A)</tex>.
|proof=
Пусть <tex>E</tex> {{---}} подмножество <tex>A</tex> такое, что <tex>rg(E) = |E|, E \in I</tex> (по определению ранговой функции такое <tex>E</tex> всегда существует.
Предположим, что это не так и максимальное независимое подмножество, которое мы можем получить из <tex>B</tex> добавляя элементы из <tex>A</tex> {{---}} это <tex>C</tex>, причем <tex>|C| < rg(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> удовлетворяющее необходимым условиям.
}}
Итак теперь мы готовы доказать свойство полумодулярности ранговой функции.
{{Теорема
|id=theorem
|statement=<tex>\forall A, B \subset X,</tex> <tex>r(A \cup B) + r(A \cap B) \le r(A) + r(B)</tex>
|proof=
Рассмотрим множество <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 (B), D_B \in I</tex> (по [[#lemma|лемме]] такое возможно). Далее дополним <tex>D_B</tex> элементами из <tex>A \cup B \setminus D_B</tex> до множества <tex>D_\cup : |D_\cup| = rg(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>(D_\cup \setminus D_B) \cup D_\cap \subset A</tex>, <tex>(D_\cup \setminus D_B) \cup D_\cap \in I</tex> (по [[Определение матроида]]), значит <tex>r(A) \ge |(D_\cup \setminus D_B) \cup D_\cap| = |D_\cup| - |D_B| + |D_\cap| = r(A \cup B) - r(B) + r(A \cap B) </tex>. Что и требовалось доказать.
}}
