308
правок
Изменения
→Покрытие
{{Определение
|definition = Пусть <tex>M =\; \langle X,I \rangle</tex> {{---}} матроид. Тогда '''покрытие''' (''span'') множества <tex>A \subseteq X</tex> {{---}} это множество <tex> span(A) \subseteq X </tex> такое, что <tex> span(A) = \mathcal {f} x \in X \; |\; r(A) = r(A \cup x) \mathcal {g}</tex>
}}
{{Определение
|definition = <tex> span(A) = A \cup \mathcal {f} x \in X \; |\; \forall S \subseteq A,\ S \in I ,\ |S| = r(A) :\ S \cup x \notin I \mathcal {g} </tex>
}}
{{Утверждение
|statement=Эти определения эквивалентны.
|proof=Понятно, что <tex> x \in A </tex> подходят под оба определения. Для остальных же <tex> x \ r(A) = r(A \cup x) </tex> означает, что нету множеств <tex> S' \in I,\ S' \subseteq A \cup x,\ |S'| > r(A). </tex> Для такого <tex> S' </tex> обязательно будет выполнено <tex> x \in S', </tex> в противном случае <tex> S' \subseteq A, </tex> и тогда <tex> r(A) \geqslant |S'|ю </tex> Тогда для <tex> S = S' \setminus x </tex> верно <tex> S \subseteq A,\ S \in I. </tex> Из последнего получается, что <tex> r(A) \geqslant |S|, </tex> и учитывая <tex> r(A) < |S'|,\ |S| + 1 = |S'| </tex> имеем <tex> r(A) = |S|. </tex> Другими словами, не должно существовать множеств <tex> S \subseteq A,\ S \in I,\ |S| = r(A):\ S' = S \cup x \in I. </tex>
}}
|proof =
# Выпишем несколько полезных нам фактов.
#* <tex> r(A) \leqslant r(span(B)) </tex> (так как <tex> A \subseteq span(B) </tex>)<ref>Свойство ранга</ref>)
#* <tex> r(A) = r(span(A)) </tex>
#*: Предположим <tex> r(A) < r(span(A)) </tex>, тогда . Тогда по определению ранга имеем <tex> \exists D \in I,\ D \subseteq span(A),D \ in I, |D| = r(span(A)) </tex>. Учитывая #*: Положим <tex> |S = D \cap A, p \in D\setminus A. </tex> }} == Замкнутые множества =={{Определение| definition = Множество <tex> r(A) \subseteq X</tex>называется '''замкнутым''' (''closed'', ''flat''), будет если <tex> D \nsubseteq span(A) = A. </tex>#*: Возьмём Множество замкнутых множеств обозначается <tex> S, p:\ S \subseteq A \cap D,\ p \in D \setminus A mathcal L </tex>.
}}
{{Теорема
|id = theorem3
|statement = Замкнутые множества обладают следующими свойствами:
# <tex> A, B \in \mathcal L \ \Rightarrow \ A \cap B \in \mathcal L </tex>
# Если <tex> F \in \mathcal L,\ p \in X \setminus A </tex> и <tex> F' </tex> {{---}} наименьшее по включению замкнутое множество, содержащее <tex> F \cup p, </tex> тогда не существует <tex> F'' \in \mathcal L :\ F \subseteq F'' \subseteq F'. </tex>
|proof =
}}
== Примечания ==
