Изменения
Нет описания правки
{{Определение
|definition = Пусть <tex>M =\; \langle X,I \rangle</tex> {{---}} матроид. Тогда '''покрытие''' (англ. ''span'') множества <tex>A \subseteq X</tex> {{---}} это множество <tex> span_M(A) = \mathcal {f} x \in X \; |\; r(A) = r(A \cup x) \mathcal {g}</tex>
}}
Далее <tex>span_M </tex> будет указываться, как <tex>span</tex>
{{Определение
|definition = <tex> span(A) = A \cup \mathcal {f} x \in X \setminus A \; |\; \forall S \subseteq A,\ S \in I,\ |S| = r(A) :\ S \cup x \notin I \mathcal {g} </tex>
}}
|statement=Для множества <tex> A \subseteq X </tex> выполнено <tex> span(A) \subseteq \langle A \rangle. </tex>
|proof=Покажем, что следующее определение замыкания равносильно тому, которое [[Оператор замыкания для матроидов | было дано]] ранее:
: <tex>\langle A \rangle = A \cup \mathcal {f} x \in X \setminus A \; |\; \exists H \subseteq A, \; H \in I , \; |H| = r(A) :\ H \cup x \notin I \mathcal {g}</tex>
По сравнению со старым определением появилось два ограничения, нужно убедится в том, что они не существены. Сначала рассмотрим <tex> |H| = r(A). </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>span</tex> удовлетворяет свойствам и определена, как:
:<tex> L = \mathcal {f} I \subseteq S \; |\; \forall s \in I : s \notin span(I \setminus {s}) \mathcal {g} </tex>
Сперва посмотрим на следующее:
:если <tex> I \in L </tex>, тогда <tex>span(I) = I \cup \mathcal {f} t \; | \; I \cup {t} \in L \mathcal {g} </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 = \mathcal {f} i \mathcal {g}</tex> и <tex>J \setminus I = \mathcal {f} {j_1, j_2} \mathcal {g}</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 \mathcal {f} x \; | \; I \cup {x} \notin L \mathcal {g} = 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>.
}}
# <tex> A, B \in \mathcal L \ \; \Rightarrow \ A \cap B \in \mathcal L </tex>
# Если <tex> F \in \mathcal L,\ p \in X \setminus 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>. 1 Первое свойство следует из <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>. Поэтому, по 2 второму свойству покрывающего множества для <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> удовлетворяет свойствам покрытого множества. 1 Первое свойство тривиально. Рассмотрим 2 второе свойство, пусть <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>. Следовательно, по 2 второму свойству, <tex>span(T \cup s) = span(T \cup t) </tex>, и следовательно, <tex> t \in span(T \cup s)</tex>.
}}
