Изменения

|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 }</tex>}} <!---ну хз кто догадался так записать, я исправляю такое без разрешения.)))--->Другими словами, замыкание множества <tex> A </tex> {{---}} это все элементы из <tex> A, </tex> а также такие <tex> x \in X, </tex> которые при добавлении к некоторым независимым подмножествам <tex> A </tex> не оставляют их независимыми.  {{Лемма|statement = Пусть <tex>M =\; \langle X,I \rangle</tex> {{---}} матроид, <tex>A \subseteq X</tex>. Тогда <tex>r(A) = r(\langle A \rangle),</tex> где <tex>r</tex> {{---}} [[Ранговая функция, полумодулярность|ранг]].|proof =Пусть существуют множества <tex>B, D \in I:\ B \subseteq A,\ D \subseteq \langle A \rangle,\ |B| = r(A) < r(\langle A \rangle) = |D|.</tex> Тогда по [[Определение матроида | 3-ей аксиоме]] <tex>\exists p \in D \setminus B :\ B \cup p \in I.</tex> Так как <tex>B</tex> {g{---}}максимальное независимое множество из <tex> A </tex>, то <tex>p \notin A,</tex>то есть <tex> p \in \langle A \rangle \setminus A. </tex> Согласно определению замыкания возьмём максимальное по мощности множество <tex>H \subseteq A:\ H \in I,\ H\cup p \notin I.</tex> Поскольку <tex> |H| \leqslant |B| < |B \cup p|,</tex> то по аксиоме замены существует <tex>q \in (B \cup p)\setminus H :\ H \cup q \in I.</tex>  Если <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 = \{ x \in X \; |\; r(A \cup x) = r(A) \}</tex>, где <tex>r: 2^X \to \mathbb{N}</tex> - [[Ранговая_функция,_полумодулярность|ранговая функция]]

|statement = Пусть <tex>M =\; \langle X,I \rangle</tex> {{---}} матроид, <tex>A \subseteq X</tex>. Тогда <tex>r(A) = r(\langle A \rangle),</tex> где <tex>r</tex> {{---}} [[Ранговая функция, полумодулярность|ранг]].Данное определение эквивалентно предыдущему

Пусть существуют множества <tex>B, C \in I:\ B \subseteq A, C \subseteq \langle A \rangle, |B| = r(A) < r(\langle A \rangle) = |C|.</tex> Тогда по аксиоме замен<ref>[[Определение матроида | Определение матроида]], 3-я аксиома</ref> <tex>\exists p \in C \setminus B :\ B \cup p \in I.</tex> Так как <tex>Brangle_1</tex> {{---}} максимально, то замыкание <tex>p \in \langle A \rangle \setminus A.</tex> По определению замыкания существует множество в смысле первого определения, <tex>H \subseteq langle A:\ H \in I,\ H\cup p \notin I.rangle_2</tex> В силу аксиомы наследования<ref>[[Определение матроида | Определение матроида]], 2{{---я аксиома</ref> можно считать, что }} замыкание <tex>|H| = |B|.A</tex> Тогда <tex>r(A) = |H| < |B \cup p|в смысле второго определения.</texbr> По аксиоме замены существует Покажем, что <tex>q \in (B langle A \cup p)rangle_1 = \setminus H :\ H langle A \cup q \in I.rangle_2</tex>

Если # <tex>q \in Blangle 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(H A \cup qa) = 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>H\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>q = pB \subseteq A,\; B \in I</tex> {{---}} наибольшее независимое подмножество <tex>A</tex> то . Тогда <tex>B \cup a \notin I</tex>, так как иначе <tex>r(H A \cup pe) = |B \cup e| > |B| = r(A)</tex>. <br> Следовательно, <tex>b \in I\langle A \rangle_1</tex>, и в силу произвольности <tex>b</tex> (противоречит выбору множества , <tex>H\langle A \rangle_2 \subseteq \langle A \rangle_1</tex>).

# Положим <tex>x \in \langle A \rangle.</tex> В соответствии с первым определением оператора замыкания есть 2 случая:

#* <tex> q \in A \cup p. </tex> Зная, что <tex> p q \notin \langle A \rangle, </tex> приходим к <tex> q = p, </tex> чего нам более чем достаточно.

#*: Заметим , что <tex> p \in H </tex>, иначе бы <tex> H </tex> подходило для <tex> q \in \langle A \rangle, </tex> поэтому запишем данное нам имеющееся у нас иначе, положив <tex> H' = H \setminus p: </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>\exists p f \in \langle A \cup e \langle 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 \rangle cup e \cup f) + r(A)</tex>.<br>Но <tex>r(A \rangle cup e) = r(A)</tex> (так как <tex>e \setminus in \langle A \rangle.</tex> Возьмем максимальное по мощности множество ), значит, <tex>B r(A \cup f) \in I :geqslant r(A \ B cup e \subseteq 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>p e \notin 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>B f: \langle A \cup p e \rangle \subseteq \langle A \rangle</tex>.# Следует из третьего свойства: <tex>\forall e \in I.\langle A \rangle : \langle A \cup e \rangle = \langle A \rangle</tex> Тогда, последовательно применив вышеуказанную лемму, дважды [[Ранговая функция, полумодулярность | определение ранга]] и снова леммуа значит, получим <tex>r(\langle \langle A \rangle) \rangle = r(\langle A \cup \langle A \rangle \rangle) = \langle A \cup e_1 \cup e_2 \geqslant |B cup e_3 \cup p| \ldots \rangle = r(\langle A) + 1 = r\rangle</tex> (где <tex>e_1, e_2, \ldots \in \langle A \rangle) + 1,</tex> что невозможно.)

== Примечания Смотри также ==<references/>* [[Покрытия, закрытые множества]]* [[Двойственный матроид]]

*''Асанов М. О., Баранский В. А., Расин В. В.'' {{---}} Дискретная математика: Графы, матроиды, алгоритмы. '''ISBN 978-5-8114-1068-2'''* [[wikipedia:en:Matroid#Closure operators | Wikipedia {{---}} Matroid]]* [[wikipedia:ru:Матроид#Определение в терминах правильного замыкания | Википедия {{---}} Матроид]]* [http://dictionary.sensagent.com/Matroid/en-en/ sensagent.com {{---}} Matroid]* [http://math.mit.edu/~goemans/18438F09/lec11.pdf Michel X. Goemans: Advanced Combinatorial Optimization, Lecture 11: Matroid Intersection]