116
правок
Изменения
Альтернативное определение оператора замыкания
Если <tex>q \in B,</tex> то <tex>(H \cup q) \subseteq A,\ </tex> но <tex> (H \cup q) \cup p \notin I </tex> в силу <tex> H \cup p \notin I </tex> (противоречие с максимальностью множества <tex>H</tex>). Если <tex>q = p,</tex> то <tex>(H \cup p) \in I</tex> (противоречит выбору множества <tex>H</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> - [[Ранговая_функция,_полумодулярность|ранговая функция]]
}}
{{Лемма
|statement = Данное определение эквивалентно предыдущему
|proof =
Пусть <tex>\langle A \rangle_1</tex> {{---}} замыкание <tex>A</tex> в смысле первого определения, <tex>\langle A \rangle_2</tex> {{---}} замыкание <tex>A</tex> в смысле второго определения.<br>
Покажем, что <tex>\langle A \rangle_1 = \langle A \rangle_2</tex>
# <tex>\langle A \rangle_1 \subseteq \langle A \rangle_2</tex> <br> По предыдущей лемме, <tex>r(A) = r(\langle A \rangle_1)</tex>, а значит, <tex>\forall a \in \langle A \rangle_1 : r(A \cup a) = r(A)</tex>, а значит, <tex>a \in \langle A \rangle_2</tex>. <br> В силу произвольности <tex>a</tex>, <tex>\langle A \rangle_1 \subseteq \langle A \rangle_2</tex>.
# <tex>\langle A \rangle_2 \subseteq \langle A \rangle_1</tex> <br> Рассмотрим <tex>a \in \langle A \rangle_2 : r(A \cup a) = r(A)</tex>. Возьмем <tex>B \subseteq A, \; B \in I</tex> {{---}} наибольшее независимое подмножество <tex>A</tex>. Тогда <tex>B \cup a \notin I</tex>, так как иначе <tex>r(A \cup e) = |B \cup e| > |B| = r(A)</tex>. <br> Следовательно, <tex>b \in \langle A \rangle_1</tex>, и в силу произвольности <tex>b</tex>, <tex>\langle A \rangle_2 \subseteq \langle A \rangle_1</tex>
}}
