Изменения

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

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

8 байт убрано, 21:31, 15 мая 2011
м
Нет описания правки
{{Теорема
|statement = Оператор замыкания для матроидов обладает следующими свойствами:
1) # <tex>A \subset B \Rightarrow \langle A \rangle \subset \langle B \rangle</tex> 2) # <tex>q \notin \langle A \rangle,\; q \in \langle A \cup p \rangle \Rightarrow p \in \langle A \cup q \rangle</tex> 3) # <tex>\langle \langle A \rangle \rangle = \langle A \rangle </tex>
|proof =
1) # Пусть <tex>\langle A \rangle \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> Получили противоречие. 2) # Так как <tex>q \in \langle A \cup p \rangle </tex> и <tex>q \notin \langle A \rangle,</tex> то существует зависимое множество <tex>\mathcal {f} a_1, a_2, ... a_n, p, q \mathcal {g} (a_i \in A).</tex> Заметим, что множество <tex>\mathcal {f} a_1, a_2, ... a_n, q \mathcal {g} \in I.</tex> То есть <tex>\mathcal {f} a_1, a_2, ... a_n, p, q \mathcal {g} - </tex> цикл. Ч.т.д.
}}
205
правок

Навигация