Изменения

|definition = Пусть <tex>M =\; \langle X,I \rangle</tex> {{---}} матроид. Тогда '''покрытие''' (англ. ''span'') множества <tex>A \subseteq X</tex> {{---}} это множество <tex> spanspan_M(A) = \mathcal {f} x \in X \; |\; r(A) = r(A \cup x) \mathcal {g}</tex>

|definition = <tex> span(A) = A \cup \mathcal {f} x \in X \setminus A \; |\; \forall S \subseteq A \setminus x,\ S \in I,\ |S| = r(A) :\ S \cup x \notin I \mathcal {g} </tex>

|proof=Понятно, что элементы из <tex> A </tex> подходят под оба определения. Для остальных же <tex> x </tex> равенство <tex> \ r(A) = r(A \cup x) </tex> означает, что не найдётся множеств <tex> S' \subseteq A \cup x :\ S' \in I,\ |S'| > r(A). </tex> Для такого <tex> S' </tex> обязательно будет выполнено <tex> x \in S', </tex> в противном случае <tex> S' \subseteq A, </tex> откуда следует что приведёт к <tex> r(A) \geqslant |S'|. </tex> Следовательно Тогда для <tex> S = S' \setminus x </tex> верно <tex> S \subseteq A,\ S \in I. </tex> Из последнего получается, что <tex> r(A) \geqslant |S|, </tex> и учитывая <tex> r(A) < |S'|,\ |S| + 1 = |S'| </tex> имеем <tex> r(A) = |S|. </tex>

Иначе говоря, не должно существовать множеств <tex> S \subseteq A,\ x \notin S,\ S \in I,\ |S| = r(A):\ S' = S \cup x \in I. </tex>

|statement=Определения замыкания и покрытия похожи Для множества <tex> A \subseteq X </tex> выполнено <tex> span(???A)\subseteq \langle A \rangle. </tex>

: <tex>\langle A \rangle = A \cup \mathcal {f} x \in X \setminus A \; |\; \exists H \subseteq A \setminus x, \; H \in I , \; |H| = r(A) :\ H \cup x \notin I \mathcal {g}</tex>

: Пусть <tex> \exists H \subseteq A :\ H \in I ,\; H \cup x \notin I, </tex> но <tex> |H| < r(A). </tex> По [[Ранговая функция, полумодулярность | определению ранга]] <tex> \exists D \subseteq A ,\; D \in I :\ |D| = r(A). </tex> Поскольку <tex> |H| < |D| </tex>, можно применить [[Определение матроида | 3-ю аксиому матроидов ]] несколько раз и получить <tex> H' \subseteq A :\ H \subseteq H' ,\; H' \in I ,\; |H'| = r(A). </tex> : <tex> H' \cup x \notin I </tex> также будет выполнено, поскольку в противном случае <tex> H \cup x \notin I </tex> будет неверно (в силу [[Определение матроида | 2-ой аксиомы матроидов]]).Второе ограничение {{---}} <tex> H x \subseteq A in X \setminus x </tex> вместо <tex> H \subseteq A </tex> {{---}} вытекает само собойможно наложить по той причине, поскольку в случае что элементы <tex> x \in H </tex> не могут одновременно выполнятся <tex> H \in I A </tex> и <tex> H \cup x \notin Iтак входят в замыкание благодаря левой части объединения. </tex>  

|statement = Покрытие обладает следующими свойствамиПусть S {{---}} конечное множество. Функция <tex> span : \mathcal P (S) \rightarrow \mathcal P (S) </tex> является покрытием матроида тогда и только тогда, когда удовлетворяет следующим свойствам:# <tex> AT, B U \in Xsubseteq S;\ A U \subseteq span(BT) \ \Rightarrow \ span(AU) \subseteq span(BT) </tex># <tex> A T \subseteq S,\ t \in XS \setminus T,\ p s \in X span(T \cup t) \setminus Aspan(T) \ \Rightarrow \ t \in span(T \cup s) </tex>|proof ='''Необходимое условие'''. Пусть <tex> span </tex> будет функцией покрытия матроида <tex> M = (S, L) </tex> с ранговой функцией <tex> r </tex>. Покажем,что <tex> s \ q in span(T)</tex>. Пусть <tex>U \subseteq span(T)</tex> и <tex>s \in span(A U)</tex>. Предположим, что <tex> s </tex> не принадлежит <tex>T</tex>. Тогда по [[ Ранговая_функция, полумодулярность | полумодулярность ранговой функции]] мы имеем:: <tex> r(T \cup {s}) \leqslant r(T \cup U \cup {s}) \leqslant r(T \cup U) + r(U \cup {s}) - r(U) = r(T \cup U) = r(T)</tex>Это показывает, что <tex> s \in span(T) </tex>. Заметим, что <tex> s \in span(T \cup p{t}) \Rightarrow p span(T) </tex> эквивалентно таким выражениям: <tex> r(T \cup {t} \cup {s}) = r(T \cup {t}) </tex> и <tex> r(T \cup {s}) > r(T)</tex>. Следовательно: <tex>r(T \cup t \cup {s}) = r(T \cup {t}) <= r(T) + 1 <= r(T \cup {s}) </tex>то есть, <tex> t \in span(A T \cup q{s}) </tex>. '''Достаточное условие'''. Пусть функция <tex>span</tex> удовлетворяет свойствам и определена, как::<tex> L = \{ I \subseteq S \; |\; \forall s \in I : s \notin span(I \setminus {s}) \} </tex>Сперва посмотрим на следующее: :если <tex> I \in L </tex>, тогда <tex>span(I) = I \cup \{ t \; |proof \; I \cup {t} \in L \} </tex>. <tex>(1)</tex> Действительно, если <tex> t \in span(I) \setminus I </tex>, тогда <tex> I \cup {t} \notin L </tex>, по определению независимого множества. С другой стороны, <tex> I \subseteq span(I)</tex>. Кроме того, если <tex> I \cup {t} \notin L </tex>, тогда по определению независимого множества получаем, что <tex> \exists s \in I \cup t : s \in span(I \cup {t} \setminus {s}) </tex>. Если <tex> s = t </tex>, тогда <tex> t \in span(I) </tex>. Предположим, что <tex> s \neq t </tex>, т.е. <tex> s \in I </tex>. Мы знаем, что <tex> s \notin span(I \setminus {s}) </tex>, так как <tex> I \in L </tex>. Таким образом по <tex>3</tex> свойству доказывается (для <tex> T \in I \setminus {s} </tex>), <tex> t \in span(I) </tex>. Теперь покажем, что <tex> M = (S, L) </tex> {{---}} матроид. Очевидно, <tex> \emptyset \in L </tex>. Для начала покажем, что <tex> I </tex> закрытое множество под полученным подмножеством, Пусть <tex> I \in L </tex> и <tex> J \subseteq I </tex>. Мы видим, что <tex> J \in I </tex>. Предположим наоборот, что <tex>\exists s \in J : s \in span(J \setminus {s}) </tex>. Тогда по второму свойству <tex> span(J \setminus {s}) \subseteq span(I \setminus {s})</tex>. Следовательно, <tex> s \in span( I \setminus {s})</tex>, что противоречит условию, что <tex> I \in L </tex>.  Для того чтобы проверить [[Определение матроида | 3-ю аксиому матроидов]], допустим, что <tex> I, J \in L </tex>, <tex> |I \setminus J| = 1 </tex> и <tex> |J \setminus I| = 2</tex>. Пусть <tex>I \setminus J = \{ i \}</tex> и <tex>J \setminus I = \{ {j_1, j_2} \}</tex>. Предположим, что <tex> I \cup {j_1} \notin L</tex>, т.е. <tex> J \cup {i} \setminus {j_2} \notin L</tex>, и так по <tex>(1)</tex> применяется к <tex>J \setminus {j_2} </tex>, <tex> i \in span(J \setminus {j_2}) </tex>. Поэтому, <tex> I \subseteq span(J \setminus {j_2})</tex> и <tex> span(I) \subseteq span(J \setminus {j_2}) </tex>. Таким образом <tex> j_2 \notin span(i) </tex>(как и <tex> J \in L</tex>) и поэтому, <tex>(1)</tex> применяется к <tex> I </tex> и к <tex> I \cup {j_2} \in L </tex>. Таким образом <tex> M </tex> является матроидом. Теперь покажем, что <tex>span = span_M</tex>. Выберем такое множество <tex> T \subseteq S </tex>, чтобы увидеть, что <tex> span(T) = span_M(T) </tex>, пусть <tex> I </tex> будет базой <tex> T </tex> (в <tex> M </tex>). Тогда используя (1), мы получаем::<tex>span_M(T) = T \cup \{ x \; | \; I \cup {x} \notin L \} =span(I) \subseteq(T) </tex>Таким образом, мы показали, что <tex> span(T) \subseteq span(I)</tex> т.е. по <tex>1</tex> свойству <tex> T \subseteq span(I)</tex>. Теперь выберем <tex> t \in T \setminus I</tex>. В силу максимальности <tex> I </tex>, мы знаем, что <tex>I \cup t \notin L</tex>, и, следовательно, по <tex>(1)</tex> получаем, что <tex> t \in span(I) </tex>.

|statement = Замкнутые Пусть <tex> S </tex> {{---}} какое-то множество и <tex> \mathcal L \subseteq S </tex>. Закрытые множества обладают следующими свойствами:

# Если <tex> F \in \mathcal L,\ p \in X \setminus A F </tex> и <tex> F' </tex> {{---}} наименьшее по включению закрытое множество, содержащее <tex> F \cup p, </tex> тогда не существует <tex> F'' \in \mathcal L :\ F \subseteq F'' \subseteq F'. </tex> |proof ='''Необходимость'''. Пусть <tex> \mathcal L </tex> семейство закрытых множеств матроида <tex> M = (S, \mathcal I) </tex>. Первое свойство следует из <tex> span(A \cap B) \subseteq span(A) \cap span(B) = A \cap B </tex>, по определению закрытого множества мы получаем, что пересечение закрытых множеств закрыто. Посмотрим на <tex>2</tex> свойства, допустим, что такой <tex> F'' </tex> существует, и выберем <tex> s \in F'' \setminus F </tex>. Таким образом <tex> s \notin span(F)</tex>. Согласно тому, что <tex> F' \not\subseteq F'' </tex>, мы получаем, что <tex> t \notin span(F \cup s)</tex>. Поэтому, по второму свойству покрывающего множества для <tex> T := F </tex> получаем противоречие, т.к. <tex> s \notin span(F) = F'</tex>. '''Достаточность'''. Пусть <tex> \mathcal L </tex> удовлетворяет свойствам закрытого множества и <tex> span(Y) </tex> будет наименьшем множеством в <tex> \mathcal L </tex> содержащий <tex> Y </tex>, для <tex> F \subseteq S </tex>. Поскольку <tex> F \in \mathcal L \Longleftrightarrow span(F) = F </tex>, этого достаточно, чтобы увидеть, что <tex> span </tex> удовлетворяет свойствам покрытого множества. Первое свойство тривиально. Рассмотрим второе свойство, пусть <tex>T \subseteq S, t \in S \setminus T, </tex> и <tex> s \in span(T \cup t) \setminus span(T) </tex>. Тогда <tex> span(T ) \subset span(T \cup s) \subseteq span(T \cup t) </tex>. Следовательно, по второму свойству, <tex>span(T \cup s) = span(T \cup t) </tex>, и следовательно, <tex> t \in span(T \cup s)</tex>.