34
правки
Изменения
Добавлена теорема о рангах, добавлен список литературы.
Что и требовалось доказать.
}}
==Теорема о рангах==
{{Теорема
|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> выполняется следующее: <br>
1) <tex> 0 \le r(A) \le |A| </tex> <br>
2) <tex> A \in B \to r(A) \le r(B) </tex> <br>
3) Неравенство полумодулярности: <tex>\forall A, B \subset X,</tex> <tex>r(A \cup B) + r(A \cap B) \le r(A) + r(B)</tex>
|proof=
1) Очевидно из определения: максимальное независимое подмножество по мощности не может быть больше самого множества и меньше нуля. <br>
2) Пусть <tex>C \in A</tex> - максимальное независимое подмножество. Т.к. <tex>A \in B</tex>, то <tex>C \in B</tex> - независимое подмножество. Поэтому <tex>r(B) \ge |C|</tex> по определению, а значит <tex>r(B) \ge r(A)</tex> <br>
3) Доказано выше.
}}
== Литература ==
''Асанов М. О., Баранский В. А., Расин В. В.'' - Дискретная математика: Графы, матроиды, алгоритмы. '''ISBN 978-5-8114-1068-2''' <br>
''Will Johnson'' - Mathroids. June 3, 2009.
[[Категория:Алгоритмы и структуры данных]]
[[Категория:Матроиды]]
