Изменения

Перейти к: навигация, поиск

Теорема Эдмондса-Лоулера

1 байт убрано, 22:54, 7 июня 2011
Нет описания правки
Докажем неравенство <tex>\max\limits_{I \in I_1 \cap I_2 } |I| \le \min\limits_{A \subseteq X} r_1(A) + r_2(X \setminus A)</tex> <br> <br>
Выберем произвольные <tex>I \in I_1 \cap I_2</tex>, <tex>A \subseteq X</tex> , тогда <br> <br>
<tex>|I| = |I \cap A| + |I \cap (X \setminus A)|</tex> <br> <br>
<tex>I \cap A</tex> и <tex>I \cap (X \setminus A)</tex> - независимые в обоих матроидах (как подмножества независимового <tex>I</tex>), значит <br> <br>
Анонимный участник

Навигация