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

Материал из Викиконспекты
Перейти к: навигация, поиск

Условие теоремы

Теорема (Эдмондса - Лоулера):
Пусть [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} \left(r_1(A) + r_2(X \setminus A)\right)[/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]I \in I_1 \cap I_2[/math], [math]A \subseteq X[/math] , тогда

[math]|I| = |I \cap A| + |I \cap (X \setminus A)|[/math]

[math]I \cap A[/math] и [math]I \cap (X \setminus A)[/math] - независимые в обоих матроидах (как подмножества независимового [math]I[/math]), значит

[math]|I| = r_1(I \cap A) + r_2(I \cap (X \setminus A))[/math]

Но [math]r_1(I \cap A) \le r_1(A)[/math] и [math]r_2(I \cap (X \setminus A)) \le r_2(X \setminus A)[/math], значит

[math]|I| \le r_1(A) + r_2(X \setminus A)[/math]

В силу произвольности [math]I[/math] и [math]A[/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]\forall M_1, M_2[/math] такие [math]I \in I_1 \cap I_2[/math] и [math]A \subseteq X[/math], что [math]|I| = r_1(A) + r_2(X \setminus A)[/math].
[math]\triangleleft[/math]