Изменения
Нет описания правки
\min\limits_{u \in F, (u,v)
{{Теорема
|about=
Эдмондса - Лоулера
|statement= Пусть <tex>M_1=<X, I_1></tex>, <tex>M_2=<X, I_2></tex> - матроиды. Тогда <br>
<tex>\max_max\limits_{I \in I_1 \cap I_2 } |I| = \min_min\limits_{A \subseteq X} r_1(A) + r_2(X \setminus A)</tex>
Где <tex>r_1</tex> и <tex>r_2</tex> - ранговые функции в первом и втором матроиде соответственно.
|proof=
Докажем неравенство <tex>\max_max\limits_{I \in I_1 \cap I_2 } |I| \le \min_min\limits_{A \subseteq X} r_1(A) + r_2(X \setminus A)</tex> <br>
Выберем произвольные <tex>I \in I_1 \cap I_2</tex>, <tex>A \subseteq X</tex> <br>
<tex>|I| = |I \cap A| + |I \cap (X \setminus A)|</tex> <br>
<tex>|I| \le r_1(A) + r_2(X \setminus A)</tex> <br>
В силу произвольности <tex>I</tex> и <tex>A</tex> получаем <br>
<tex>\max_max\limits_{I \in I_1 \cap I_2 } |I| \le \min_min\limits_{A \subseteq X} r_1(A) + r_2(X \setminus A)</tex>
}}
