Просмотр исходного текста страницы Ранговая функция, полумодулярность

{{Определение
|definition= Пусть дан [[Определение матроида|матроид]]  <tex> M = \langle X, I \rangle</tex>. '''Ранговая функция''' <tex>r: 2^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| = r(A)</tex>.
|proof=
Пусть <tex>E</tex> {{---}} подмножество <tex>A</tex> такое, что <tex>r(A) = |E|, E \in I</tex> (по определению ранговой функции такое <tex>E</tex> всегда существует).  
Предположим, что лемма неверна и максимальное независимое подмножество, которое мы можем получить из <tex>B</tex> добавляя элементы из <tex>A</tex> {{---}} это <tex>C</tex>, причем <tex>|C| < r(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 \cup \{x\}</tex>. Итак пришли к противоречию, мы получили множество большее по мощности, чем <tex>C</tex> такое, что <tex>B \subset C \subset A, C \in I</tex>, значит исходное предположение было не верно, и мы можем найти множество <tex>D</tex> удовлетворяющее необходимым условиям.
}}

Итак теперь мы готовы доказать свойство полумодулярности ранговой функции.

{{Теорема
|id=theorem
|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 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| = 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| = r(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|</tex>

Заменяя мощности на ранги:

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

Что и требовалось доказать.
}}


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

==См. так же==
*[[Теорема о циклах]]
*[[Теорема о базах]]

==Источники информации==
*Асанов М. О., Баранский В. А., Расин В. В.'' - Дискретная математика: Графы, матроиды, алгоритмы. '''ISBN 978-5-8114-1068-2''' <br>
*Will Johnson'' - Mathroids. June 3, 2009.

[[Категория:Алгоритмы и структуры данных]]
[[Категория:Матроиды]]
[[Категория:Основные факты теории матроидов]]