Изменения
Новая страница: «== Условие теоремы == {{Теорема |about= Эдмондса - Лоулера |statement= Пусть <tex>M_1=\langle X, I_1\rangle</tex>, <tex>M_2=…»
== Условие теоремы ==
{{Теорема
|about=
Эдмондса - Лоулера
|statement= Пусть <tex>M_1=\langle X, I_1\rangle</tex>, <tex>M_2=\langle X, I_2\rangle</tex> — матроиды. Тогда <br>
<tex>\max\limits_{I \in I_1 \cap I_2 } |I| = \min\limits_{A \subseteq X} \left(r_1(A) + r_2(X \setminus A)\right)</tex>.
Где <tex>r_1</tex> и <tex>r_2</tex> — ранговые функции в первом и втором матроиде соответственно.
|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> (т.е. в простую сторону) известно.
Конструктивно построим <tex>\forall M_1, M_2</tex> такие <tex>I \in I_1 \cap I_2</tex> и <tex>A \subseteq X</tex>, что <tex>|I| = r_1(A) + r_2(X \setminus A)</tex>.
}}
{{Теорема
|about=
Эдмондса - Лоулера
|statement= Пусть <tex>M_1=\langle X, I_1\rangle</tex>, <tex>M_2=\langle X, I_2\rangle</tex> — матроиды. Тогда <br>
<tex>\max\limits_{I \in I_1 \cap I_2 } |I| = \min\limits_{A \subseteq X} \left(r_1(A) + r_2(X \setminus A)\right)</tex>.
Где <tex>r_1</tex> и <tex>r_2</tex> — ранговые функции в первом и втором матроиде соответственно.
|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> (т.е. в простую сторону) известно.
Конструктивно построим <tex>\forall M_1, M_2</tex> такие <tex>I \in I_1 \cap I_2</tex> и <tex>A \subseteq X</tex>, что <tex>|I| = r_1(A) + r_2(X \setminus A)</tex>.
}}
