Изменения

{{Определение|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(\langle A \ranglecup e) = + r(\langle \langle A \rangle \ranglecup f) \geqslant |B \cup p| = r(A\cup e \cup f) + 1 = r(\langle (A \ranglecup e) + 1,</tex> что невозможно.}} == Покрытие == {{Определение|definition = Пусть <tex>M =\; \langle X,I \rangle</tex> {{---}} матроид. Тогда '''покрытие''' cap (''span'') множества <tex>A \subseteq X</tex> {{---}} это множество <tex> span(Acup f)) = \mathcal {f} x \in X \; |\; r(A) = geqslant r(A \cup x) \mathcal {g}</tex>}}{{Определение|definition = <tex> span(A) = A e \cup \mathcal {f} x \in X \; |\; \forall S \subseteq A,\ S \in I,\ |S| = ) + r(A) :\ S \cup x \notin I \mathcal {g} </tex> }} {{Утверждение|statement=Эти определения эквивалентны.|proof=Понятно, что <texbr> x \in A </tex> подходят под оба определения. Для остальных же Но <tex> x \ r(A\cup e) = r(A \cup x) </tex> означает, что нету множеств (так как <tex> S' e \in I,\ S' \subseteq langle A \cup x,\ |S'| > r(A). rangle</tex> Для такого <tex> S' </tex> обязательно будет выполнено <tex> x \in S'), </tex> в противном случае <tex> S' \subseteq Aзначит, </tex> и тогда <tex> r(A\cup f) \geqslant |S'|ю </tex> Тогда для <tex> S = S' \setminus x </tex> верно <tex> S \subseteq r(A,\ S cup e \in I. cup f)</tex> Из последнего получается, что в свою очередь влечет <tex> r(A\cup f) \geqslant |S|, </tex> и учитывая <tex> = r(A\cup e \cup f) < |S'|,\ |S| + 1 = |S'| </tex> имеем <tex> r(A) = |S|. </texbr>  Другими словами, не должно существовать множеств Но так как <tex> S \subseteq A,\ S f \in I, \ |S| = r(langle A):\ S' = S \cup x e \in I. rangle</tex> }} {{Теорема|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>). <refbr>Свойство ранга</ref>#* В силу произвольности <tex> r(A) = r(span(A)) </tex>#*f: Предположим <tex> r(\langle A) < r(span(A)) </tex>. Тогда по определению ранга <tex> \exists D cup e \rangle \subseteq span(\langle A), D \in I, |D| = r(span(A)) rangle</tex>.#*Следует из третьего свойства: Положим <tex> S = D \cap forall e \in \langle A, p \in D rangle : \setminus langle A. </tex>  }} \cup e \rangle == Замкнутые множества =={{Определение|definition = Множество <tex>\langle A \subseteq Xrangle</tex> называется '''замкнутым''' (''closed'', ''flat'')а значит, если <tex> span(\langle \langle A) \rangle \rangle = A. </tex> Множество замкнутых множеств обозначается <tex> \mathcal L </tex>}} {{Теорема|id = theorem3|statement = Замкнутые множества обладают следующими свойствами:# <tex> langle A, B \in cup \mathcal L langle A \ rangle \Rightarrow rangle = \ langle A \cap B cup e_1 \in cup e_2 \mathcal L </tex># Если <tex> F cup e_3 \in cup \mathcal L,ldots \ p rangle = \in X langle A \setminus A rangle</tex> и (где <tex> F' </tex> {{---}} наименьшее по включению замкнутое множествоe_1, e_2, содержащее <tex> F \cup p, </tex> тогда не существует <tex> F'' ldots \in \mathcal L :langle A \ F \subseteq F'' \subseteq F'. rangle</tex> |proof =)

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