Изменения
Нет описания правки
{{Определение
|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> A </tex> {{---}} это все элементы из <tex> A, </tex> а также такие <tex> x \in X, </tex> которые при добавлении к некоторым независимым подмножествам <tex> A </tex> не оставляют их независимыми.
{{Определение
|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 = \mathcal {f} x \in X \; |\; r(A \cup x) = r(A) \mathcal {g}</tex>, где <tex>r: 2^X \to \mathbb{N}</tex> - [[Ранговая_функция,_полумодулярность|ранговая функция]]
}}
#*: Как видим, множество <tex> H' \cup q </tex> подходит под определение <tex> p \in \langle A \cup q \rangle. </tex>
# По первому свойству очевидно, что <tex>\langle A \rangle \subseteq \langle A \cup e \rangle</tex>. Докажем обратное: <tex>\langle A \cup e \rangle \subseteq \langle A \rangle</tex>.<br>Воспользуемся вторым определением оператора замыкания. Рассмотрим <tex>f \in \langle A \cup e \rangle</tex>. По [[Ранговая_функция,_полумодулярность|полумодулярности ранговой функции]] имеем: <br><tex>r(A \cup e) + r(A \cup f) \geqslant r(A \cup e \cup f) + r((A \cup e) \cap (A \cup f)) \geqslant r(A \cup e \cup f) + r(A)</tex>.<br>Но <tex>r(A \cup e) = r(A)</tex> (так как <tex>e \in \langle A \rangle</tex>), значит, <tex>r(A \cup f) \geqslant r(A \cup e \cup f)</tex>, что в свою очередь влечет <tex>r(A \cup f) = r(A \cup e \cup f)</tex>.<br>Но так как <tex>f \in \langle A \cup e \rangle</tex> и <tex>e \in \langle A \rangle</tex>, то имеем <tex>r(A) = r(A \cup e) = r(A \cup e \cup f) = r(A \cup f)</tex>.<br>Следовательно, по определению, <tex>f \in \langle A \rangle</tex>. <br>В силу произвольности <tex>f: \langle A \cup e \rangle \subseteq \langle A \rangle</tex>.
# Следует из третьего свойства: <tex>\forall e \in \langle A \rangle : \langle A \cup e \rangle = \langle A \rangle</tex>, а значит, <tex>\langle \langle A \rangle \rangle = \langle A \cup \langle A \rangle \rangle = \langle A \cup e_1 \cup e_2 \cup e_3 \cup ... \ldots \rangle = \langle A \rangle</tex> (где <tex>e_1, e_2, ...\ldots \in \langle A \rangle</tex>)
}}
== Смотри также ==
* [[Покрытия, закрытые множества]]
* [[Двойственный матроид]]
== Источники информации ==
