25
правок
Изменения
→Закрытые множества
{{Теорема
|statement = Пусть <tex> S </tex> {{---}} какое-то множество и <tex> \mathcal L \subseteq S </tex>. Закрытые множества обладают следующими свойствами:
# <tex> A, B \in \mathcal L \ \; \Rightarrow \ A \cap B \in \mathcal L </tex>
# Если <tex> F \in \mathcal L,\ p \in X \setminus F </tex> и <tex> F' </tex> {{---}} наименьшее закрытое множество, содержащее <tex> F \cup p, </tex> тогда не существует <tex> F'' \in \mathcal L :\ F \subseteq F'' \subseteq F'. </tex>
|proof ='''Необходимость'''. Пусть <tex> \mathcal L </tex> семейство закрытых множеств матроида <tex> M = (S, \mathcal I) </tex>. 1 свойство следует из <tex> span(A \cap B) \subseteq span(A) \cap span(B) = A \cap B </tex>. Посмотрим на 2 свойства, допустим, что такой <tex> F'' </tex> существует, и выберем <tex> s \in F'' \setminus F </tex>. Таким образом <tex> s \notin span(F)</tex>. Согласно тому, что <tex> F' \not\subseteq F'' </tex>, мы получаем, что <tex> t \notin span(F \cup s)</tex>. Поэтому, по 2 свойству покрывающего множества для <tex> T := F </tex> получаем противоречие, т.к. <tex> s \notin span(F) = F'</tex>. '''Достаточность'''. Пусть <tex> \mathcal L </tex> удовлетворяет свойствам закрытого множества и <tex> span(Y) </tex> будет наименьшем множеством в <tex> \mathcal L </tex> содержащий <tex> Y </tex>, для <tex> F \subseteq S </tex>. Поскольку <tex> F \in \mathcal L \Longleftrightarrow span(F) = F </tex>, этого достаточно, чтобы увидеть, что <tex> span </tex> удовлетворяет свойствам покрытого множества. 1 свойство тривиально. Рассмотрим 2 свойство, пусть <tex>T \subseteq S, t \in S \setminus T, </tex> и <tex> s \in span(T \cup t) \setminus span(T) </tex>. Тогда <tex> span(T ) \subset span(T \cup s) \subseteq span(T \cup t) </tex>. Следовательно, по 2 свойству, <tex>span(T \cup s) = span(T \cup t) </tex>, и следовательно, <tex> t \in span(T \cup s)</tex>.
}}
