Теорема Эдмондса - Лоулера, формулировка, док-во в простую сторону
Теорема (Эдмондса - Лоулера): |
Пусть , - матроиды. Тогда Где и - ранговые функции в первом и втором матроиде соответственно. |
Доказательство: |
Докажем неравенство |
Теорема (Эдмондса - Лоулера): |
Пусть [math]M_1= \langle X, I_1 \rangle [/math], [math]M_2= \langle X, I_2 \rangle [/math] - матроиды. Тогда [math]\max\limits_{I \in I_1 \cap I_2 } |I| = \min\limits_{A \subseteq X} r_1(A) + r_2(X \setminus A)[/math] Где [math]r_1[/math] и [math]r_2[/math] - ранговые функции в первом и втором матроиде соответственно. |
Доказательство: |
[math]\triangleright[/math] |
Докажем неравенство [math]\max\limits_{I \in I_1 \cap I_2 } |I| \le \min\limits_{A \subseteq X} r_1(A) + r_2(X \setminus A)[/math] |
[math]\triangleleft[/math] |