25
правок
Изменения
м
→Покрытие
{{Теорема
|statement = Покрытие обладает следующими свойствами:
# <tex> AT, B U \subseteq XS;\ A U \subseteq span(BT) \ \Rightarrow \ span(AU) \subseteq span(BT) </tex># <tex> A T \subseteq XS,\ p t \in X S \setminus AT,\ q s \in span(A T \cup pt) \setminus span(AT) \ \Rightarrow \ p t \in span(A T \cup qs) </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>
