25
правок
Изменения
м
→Покрытие
# <tex> T \subseteq S,\ t \in S \setminus T,\ s \in span(T \cup t) \setminus span(T) \ \Rightarrow \ t \in span(T \cup s) </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}) <= \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>.
