Изменения

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

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

106 байт убрано, 00:47, 4 июня 2011
Нет описания правки
# <tex>\langle \langle A \rangle \rangle = \langle A \rangle </tex>
|proof =
# Пусть <tex>\langle A \rangle \not\subset \langle B \rangle,</tex> тогда <tex>\exists x \notin \langle B \rangle, x \in \langle A \rangle.</tex> Следовательно, Тогда по определению оператора замыкания <tex>\exists C \in I, C \subset A : C \cup x \notin I.</tex> Но так как <tex>C \subset B,</tex> то поэтому <tex>x \in \langle B \rangle.</tex> Получили противоречиеЧ.т.д.
# Так как <tex>q \in \langle A \cup p \rangle </tex> и <tex>q \notin \langle A \rangle,</tex> то существует независимое множество <tex>B : B \subset A \cup p, B \cup q \notin I.</tex> Так как <tex>q \notin \langle A \rangle,</tex> то <tex>p \in B, (B \setminus p)\cup q \in I.</tex> Тогда <tex>((B \setminus p)\cup q) \cup p \notin I,</tex> то есть <tex>p \in \langle A \cup q \rangle.</tex>
# Пусть <tex>\exists p \in \langle \langle A \rangle \rangle \setminus \langle A \rangle.</tex> Возьмем максимальное по мощности множество <tex>B \in I : B \subset 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) \ge |B \cup p| = r(A) + 1 = r(\langle A \rangle) + 1,</tex> что невозможно.
}}
Анонимный участник

Навигация