Изменения

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

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

4 байта добавлено, 21:47, 9 июня 2014
м
Нет описания правки
{{Определение
|definition = Пусть <tex>M =\; \langle X,I \rangle</tex> {{---}} [[Определение матроида|матроид]]. Тогда '''замыкание ''' (''closure)''' ) множества <tex>A \subseteq X</tex> {{---}} это множество <tex>\langle A \rangle \subseteq X</tex> такое, что <tex>\langle A \rangle = A \cup \mathcal {f} x \in X \; |\; \exists H \subseteq A :\ H \in I ,\; H \cup x \notin I \mathcal {g}</tex>
}}
#* <tex>\exists H \subseteq A :\ H \in I,\ H \cup x \notin I.</tex> Для такого <tex> H </tex> также верно <tex>H \subseteq B,</tex> потому <tex>x \in \langle B \rangle.</tex>
# Опять два случая:
#* <tex> q \in A \cup p. </tex> Зная, что <tex> p q \notin \langle A \rangle, </tex> приходим к <tex> q = p, </tex> чего нам более чем достаточно.
#* <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> H' = H \setminus p: </tex>
308
правок

Навигация