Изменения

|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>

|proof ='''Необходимое условие'''. Пусть <tex> span </tex> будет функцией покрытия матроида <tex> M = (S, L) </tex> с ранговой функцией <tex> r </tex>. Покажем, что <tex> s \in span(T)</tex>. Пусть <tex>U \subseteq span(T)</tex> и <tex>s \in span(U)</tex>. Предположим, что <tex> s </tex> не принадлежит <tex>T</tex>. Тогда по [[ Ранговая_функция, полумодулярность | полумодулярность ранговой функции]] мы имеем:: <tex> r(T \cup {s}) <= r(T \cup U \cup {s}) <= 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 {t}) \Rightarrow 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(T \cup {s}) </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>. (1) Действительно, если <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 \in span(I \setminus {s}) </tex>, так как <tex> I \in L </tex>. Таким образом по 3 свойству доказывается (для <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} \in L</tex>, т.е. <tex> J \cup {i} \setminus {j_2} \in L</tex>, и так по (1) применяется к <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 \in span(i) </tex>(как и <tex> J \in L</tex>) и поэтому, (1) применяется к <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} \in L \mathcal {g} = span(I) \subseteq(T) </tex>Таким образом, мы показали, что <tex> span(T) \subseteq span(I)</tex> т.е. по 1 свойству <tex> T \subseteq span(I)</tex>. Теперь выберем <tex> t \in T \setminus I</tex>. Мы знаем <tex>I \cup t \notin L</tex>, т.к. <tex> I </tex> максимально по включению, и, следовательно, по (1) получаем, что <tex> t \in span(I) </tex>.