308
правок
Изменения
м
Нет описания правки
== Замыкание ==
{{Определение
|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> \langle A \rangle \subseteq \langle \langle A \rangle \rangle </tex>. Предположим <tex>\exists p \in \langle \langle A \rangle \rangle \setminus \langle A \rangle.</tex> Возьмем максимальное по мощности множество <tex>B \in I :\ B \subseteq 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) \geqslant |B \cup p| = r(A) + 1 = r(\langle A \rangle) + 1,</tex> что невозможно.
}}
== Покрытие ==
{{Определение
|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 \cup x \notin I \mathcal {g} </tex>
}}
{{Утверждение
|statement=Эти определения эквивалентны.
|proof=
}}
{{Теорема
|id = theorem2
|statement = Покрытие обладает следующими свойствами:
# <tex> A, B \in X;\ A \subseteq span(B) \ \Rightarrow \ span(A) \subseteq span(B) </tex>
# <tex> A \in X,\ p \in X \setminus A,\ q \in span(A \cup p) \Rightarrow p \in span(A \cup q) </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| = r(span(A)) </tex>. Учитывая <tex> |D| > r(A) </tex>, будет <tex> D \nsubseteq A. </tex>
#*: Возьмём <tex> S, p:\ S \subseteq A \cap D,\ p \in D \setminus A </tex>.
}}
== Примечания ==
