Теорема Эдмондса - Лоулера, формулировка, док-во в простую сторону — различия между версиями
(Новая страница: «{{Теорема |about= Эдмондса - Лоулера |statement= Пусть <tex>M_1=<X, I_1></tex>, <tex>M_2=<X, I_2></tex> - матроиды. Тогда <br…») |
м (rollbackEdits.php mass rollback) |
||
(не показано 5 промежуточных версий 2 участников) | |||
Строка 2: | Строка 2: | ||
|about= | |about= | ||
Эдмондса - Лоулера | Эдмондса - Лоулера | ||
− | |statement= Пусть <tex>M_1= | + | |statement= Пусть <tex>M_1= \langle X, I_1 \rangle </tex>, <tex>M_2= \langle X, I_2 \rangle </tex> - матроиды. Тогда <br> |
− | <tex>\ | + | <tex>\max\limits_{I \in I_1 \cap I_2 } |I| = \min\limits_{A \subseteq X} r_1(A) + r_2(X \setminus A)</tex> |
Где <tex>r_1</tex> и <tex>r_2</tex> - ранговые функции в первом и втором матроиде соответственно. | Где <tex>r_1</tex> и <tex>r_2</tex> - ранговые функции в первом и втором матроиде соответственно. | ||
|proof= | |proof= | ||
− | + | Докажем неравенство <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> | |
+ | Выберем произвольные <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 \cap A</tex> и <tex>I \cap (X \setminus A)</tex> - независимые в обоих матроидах (как подмножества независимового <tex>I</tex>), значит | ||
+ | <tex>|I| = r_1(I \cap A) + r_2(I \cap (X \setminus A))</tex> <br> | ||
+ | Но <tex>r_1(I \cap A) \le r_1(A)</tex> и <tex>r_2(I \cap (X \setminus A)) \le r_2(X \setminus A)</tex>, значит | ||
+ | <tex>|I| \le r_1(A) + r_2(X \setminus A)</tex> <br> | ||
+ | В силу произвольности <tex>I</tex> и <tex>A</tex> получаем <br> | ||
+ | <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> | ||
}} | }} |
Текущая версия на 19:28, 4 сентября 2022
Теорема (Эдмондса - Лоулера): |
Пусть , - матроиды. Тогда Где и - ранговые функции в первом и втором матроиде соответственно. |
Доказательство: |
Докажем неравенство |