Изменения

{{Определение|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 \{ 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 \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 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 = A \cup \mathcal {f} x \in X \; |\; r(A \exists H \subseteq cup x) = r(A :) \ H \in I }</tex>,где <tex>r: 2^X \; H \cup x \notin I to \mathcal mathbb{gN}</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, D \in I:\ B \subseteq A,\ D \subseteq \langle A \rangle,\ |B| = r(A) < r(\langle A \rangle) = |D|.</tex> Тогда по аксиоме замен<ref>[[Определение матроида | Определение матроида]], 3-я аксиома</ref> <tex>\exists p \in D \setminus B :\ B \cup p \in I.</tex> Так как <tex>Brangle_1</tex> {{---}} максимальное независимое множество из замыкание <tex> A </tex>в смысле первого определения, то <tex>p \notin A,</tex> то есть <tex> p \in \langle A \rangle \setminus A. rangle_2</tex> Согласно определению замыкания возьмём максимальное по мощности множество {{---}} замыкание <tex>H \subseteq A:\ H \in I,\ H\cup p \notin I.</tex> Поскольку в смысле второго определения.<texbr> |H| \leqslant |B| < |B \cup p|Покажем,что </tex> то по аксиоме замены существует <tex>q \in (B langle A \cup p)rangle_1 = \setminus H :langle A \ H \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>\langle A \rangle_2 \subseteq \langle A,\ rangle_1</tex> но <br> Рассмотрим <tex> a \in \langle A \rangle_2 : r(H A \cup qa) = r(A) \cup p \notin I </tex> в силу . Возьмем <tex> H B \subseteq A, \cup p ; B \notin in I </tex> (противоречие с максимальностью множества {{---}} наибольшее независимое подмножество <tex>HA</tex>). Если Тогда <tex>q = p,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> \langle A \rangle \subseteq \langle \langle A \rangle cup e \rangle </tex>. Предположим Докажем обратное: <tex>\exists p \in \langle \langle A \rangle cup e \rangle \setminus subseteq \langle A \rangle.</tex> Возьмем максимальное по мощности множество .<texbr>B \in I :\ B \subseteq AВоспользуемся вторым определением оператора замыкания.Рассмотрим </tex> Так как <tex>p f \notin in \langle A \cup e \rangle,</tex> то по определению замыкания <tex>B \cup p \in I.</tex> Тогда, последовательно применив вышеуказанную лемму, дважды По [[Ранговая функцияРанговая_функция, полумодулярность _полумодулярность| определение рангаполумодулярности ранговой функции]] и снова лемму, получим имеем: <br><tex>r(A \langle cup e) + r(A \ranglecup f) = \geqslant r(A \langle cup e \langle cup f) + r((A \rangle cup e) \cap (A \ranglecup f)) \geqslant |B \cup p| = r(A\cup e \cup f) + 1 = r(\langle A \rangle) + 1,</tex> что невозможно.}} == Покрытие == {{Определение|definition = Пусть <br>Но <tex>M r(A \cup e) =\; \langle X,I \rangler(A)</tex> {{---}} матроид. Тогда '''покрытие''' (''span'') множества так как <tex>e \in \langle A \subseteq Xrangle</tex> {{---}} это множество ), значит, <tex> spanr(A\cup f) \subseteq X geqslant r(A \cup e \cup f)</tex> такое, что в свою очередь влечет <tex> spanr(A) = \mathcal {cup f} x \in X \; |\; r(A) = r(A \cup xe \cup f) \mathcal {g}</tex>}}{{Определение|definition = .<br>Но так как <tex> span(A) = A \cup \mathcal {f} x \in X \; |\; \forall S \subseteq langle A,\ S \in I :\ S \cup x e \notin I \mathcal {g} rangle</tex> }} {{Утверждение|statement=Эти определения эквивалентны.|proof=}} {{Теорема|id = theorem2|statement = Покрытие обладает следующими свойствами:# и <tex> A, B e \in X;\ langle A \subseteq span(B) \ \Rightarrow \ span(A) \subseteq span(B) rangle</tex># , то имеем <tex> r(A \in X,\ p \in X \setminus A,\ q \in span) = r(A \cup pe) \Rightarrow p \in span= r(A \cup qe \cup f) </tex>|proof =# Выпишем несколько полезных нам фактов.#* <tex> r(A) \leqslant r(span(B)cup f) </tex> (так как .<br>Следовательно, по определению, <tex> f \in \langle A \subseteq span(B) rangle</tex>. <ref>Свойство ранга</refbr>) #* В силу произвольности <tex> r(f: \langle A) = r(span(\cup e \rangle \subseteq \langle A)) \rangle</tex>.#*Следует из третьего свойства: Предположим <tex> r(\forall e \in \langle A \rangle : \langle A) < r(span(\cup e \rangle = \langle A)) \rangle</tex>, тогда по определению ранга имеем а значит, <tex> \exists D langle \langle A \in I,rangle \rangle = \langle A \ D cup \subseteq span(langle A),\ |D| rangle \rangle = r(span(\langle A)) </tex>. Учитывая <tex> |D| > r(\cup e_1 \cup e_2 \cup e_3 \cup \ldots \rangle = \langle A) </tex>, будет <tex> D \nsubseteq A. rangle</tex>#*: Возьмём (где <tex> Se_1, p:\ S \subseteq A \cap De_2,\ p ldots \in D \setminus langle A \rangle</tex>.)

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