Изменения
Нет описания правки
{{Определение
|definition = Пусть <tex>M =\; \langle X,I \rangle</tex> {{- --}} [[Определение матроида|матроид]]. Тогда '''замыкание ''' (англ. ''closure)''' ) множества <tex>A \subset subseteq X</tex> {{- --}} это множество <tex>\langle A \rangle \subset 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 \}</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 \subset 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> {{---}} максимальное независимое множество из <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 x p \notin I </tex> (противоречие с максимальностью множества <tex>H</tex>). Если <tex>q = p,</tex> то <tex>(H \mathcal cup p) \in I</tex> (противоречит выбору множества <tex>H</tex>).}} {g{Определение|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 \subset X</tex>. Тогда <tex>r(A) = r(\langle A \rangle),</tex> где <tex>r</tex> - [[Ранговая функция, полумодулярность|ранг]].Данное определение эквивалентно предыдущему
|proof =
Пусть существуют такие множества <tex>B, C \in I: B \subset A, C \subset \langle A \rangle, |B| = r(A) < r(\langle A \rangle) = |C|.rangle_1</tex> Тогда по аксиоме замен {{---}} замыкание <tex>\exists p \in C \setminus B : B \cup p \in I.A</tex> Так как <tex>B</tex> - максимальнов смысле первого определения, то <tex>p \in \langle A \rangle \setminus A.rangle_2</tex> По определению замыкания существует такое множество {{---}} замыкание <tex>D \subset A: D \in I, D\cup p \notin I.</tex> В силу аксиомы наследования можно считать, что <tex>|D| = |B|в смысле второго определения.</texbr> Тогда Покажем, что <tex>r(\langle A) \rangle_1 = |D| < |B \cup p|.</tex> По аксиоме замены существует <tex>q langle A \in (B \cup p)\setminus D : D \cup q \in I.rangle_2</tex>
}}
|id = theorem
|statement = Оператор замыкания для матроидов обладает следующими свойствами:
# <tex>A \subset subseteq B \Rightarrow \langle A \rangle \subset subseteq \langle B \rangle</tex>
# <tex>q \notin \langle A \rangle,\; q \in \langle A \cup p \rangle \Rightarrow p \in \langle A \cup q \rangle</tex>
# <tex>e \in \langle A \rangle \Rightarrow \langle A \cup e \rangle = \langle A \rangle</tex>
# <tex>\langle \langle A \rangle \rangle = \langle A \rangle </tex>
|proof =
# Положим <tex>x \in \langle A \rangle.</tex> Тогда по определению В соответствии с первым определением оператора замыкания есть 2 случая:#* <tex> x \in A. </tex> Тогда <tex> x \in B </tex>, и следовательно <tex> x \in \langle B \rangle. </tex> #* <tex>\exists C H \subseteq A :\ H \in I, C \subset A : C H \cup x \notin I.</tex> Но Для такого <tex> H </tex> также верно <tex>C H \subset subseteq B,</tex> поэтому потому <tex>x \in \langle B \rangle.</tex> Ч.т.д.# Так как Опять два случая: #* <tex>q \in \langle A \cup p \rangle . </tex> и Зная, что <tex>q \notin \langle A \rangle,</tex> то существует независимое множество приходим к <tex> q = p, </tex> чего нам более чем достаточно.#* <tex>B : B \subset exists H \subseteq A \cup p:\ H \in I, B \ H \cup q \notin I.</tex> Так как #*: Заметим, что <tex> p \in H </tex>, иначе бы <tex> H </tex> подходило для <tex>q \notin in \langle A \rangle,</tex> то поэтому запишем имеющееся у нас иначе, положив <tex> H' = H \setminus p: </tex>#*:: <tex>\exists H' \subseteq A:\ H' \cup p \in BI, (B \setminus H' \cup p)\cup q \in notin I.</tex> Тогда #*: <tex>((B \setminus p)H' \cup q) \cup p in I </tex>, в противном случае в силу <tex> H' \notin in I</tex> было бы <tex> q \in \langle A \rangle. </tex>#*: Как видим,множество <tex> H' \cup q </tex> то есть подходит под определение <tex>p \in \langle A \cup q \rangle.</tex># Пусть По первому свойству очевидно, что <tex>\exists p langle A \rangle \in subseteq \langle A \cup e \rangle</tex>. Докажем обратное: <tex>\langle A \rangle cup e \rangle \setminus subseteq \langle A \rangle.</tex> Возьмем максимальное по мощности множество .<br>Воспользуемся вторым определением оператора замыкания. Рассмотрим <tex>B f \in I \langle A \cup e \rangle</tex>. По [[Ранговая_функция,_полумодулярность|полумодулярности ранговой функции]] имеем: B <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)) \subset geqslant r(A\cup e \cup f) + r(A)</tex>.<br>Но <tex>r(A \cup e) = r(A)</tex> Так (так как <tex>p e \notin in \langle A \rangle,</tex> то по определению замыкания ), значит, <tex>B r(A \cup f) \geqslant r(A \cup p e \in I.cup f)</tex> Следовательно, что в свою очередь влечет <tex>r(\langle A \ranglecup f) = r(A \cup e \cup f)</tex>.<br>Но так как <tex>f \langle in \langle A \cup e \rangle </tex> и <tex>e \in \langle A \rangle</tex>, то имеем <tex>r(A) \ge |B = r(A \cup p| e) = r(A\cup e \cup f) + 1 = r(A \cup f)</tex>.<br>Следовательно, по определению, <tex>f \in \langle A \rangle) + 1</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> что невозможно.)
}}
== Литература Смотри также ==* [[Покрытия, закрытые множества]]* [[Двойственный матроид]] == Источники информации ==*''Асанов М. О., Баранский В. А., Расин В. В.'' {{--- }} Дискретная математика: Графы, матроиды, алгоритмы. '''ISBN 978-5-8114-1068-2'''<br * [[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] [[Категория:Алгоритмы и структуры данных]][[Категория:Матроиды]][[Категория:Основные факты теории матроидов]]
