34
правки
Изменения
м
Нет описания правки
{{Определение
|definition= Пусть дан [[Определение матроида|матроид]] <tex> M = \langle X, I \rangle</tex>. '''Ранговая функция(rank function)''' <tex>r: 2^X \to Z_+</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 r(A) + r(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 subseteq 2^X</tex> выполняется следующее:
#<tex> 0 \leqslant r(A) \leqslant |A| </tex>
#<tex> A \in subseteq B \to 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 \in subseteq A</tex> {{---}} максимальное независимое подмножество. Т.к. <tex>A \in subseteq B</tex>, то <tex>C \in subseteq 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.
[[Категория:Алгоритмы и структуры данных]]
[[Категория:Матроиды]]
[[Категория:Основные факты теории матроидов]]
