Изменения

Перейти к: навигация, поиск

Оператор замыкания для матроидов

4 байта добавлено, 19:58, 7 июня 2014
м
Нет описания правки
#* <tex> \exists H \subseteq A \cup p :\ H \in I,\ H \cup q \notin I. </tex>
#*: Заметим что <tex> p \in H </tex>, иначе бы <tex> H </tex> подходило для <tex> q \in \langle A \rangle, </tex> поэтому запишем данное нам иначе:
#*:: <tex> \exists H' \subseteq A:\ H' \cup p \in I,\ (H' \cup p) \cup q \notin I. </tex>
#*: <tex> H' \cup q \in I </tex>, в противном случае в силу <tex> H' \in I </tex> было бы <tex> q \in \langle A \rangle. </tex>
#*: Как видим, у нас есть всё необходимое чтобы сказать, что множество <tex> H' \cup q </tex> подходит под определение <tex> p \in \langle A \cup q \rangle. </tex>
# Из определения понятно, что <tex> \langle A \rangle \subseteq \langle \langle A \rangle \rangle </tex>. Предположим <tex>\exists p \in \langle \langle A \rangle \rangle \setminus \langle A \rangle.</tex> Возьмем максимальное по мощности множество <tex>B \in I :\ B \subseteq A.</tex> Так как <tex>p \notin \langle A \rangle,</tex> то по определению замыкания <tex>B \cup p \in I.</tex> Тогда, последовательно применив вышеуказанную лемму, дважды [[Ранговая функция, полумодулярность | определение ранга]] и снова лемму, получим <tex>r(\langle A \rangle) = r(\langle \langle A \rangle \rangle) \geqslant |B \cup p| = r(A) + 1 = r(\langle A \rangle) + 1,</tex> что невозможно.
}}
308
правок

Навигация