Теорема Эдмондса - Лоулера, формулировка, док-во в простую сторону — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Новая страница: «{{Теорема |about= Эдмондса - Лоулера |statement= Пусть <tex>M_1=<X, I_1></tex>, <tex>M_2=<X, I_2></tex> - матроиды. Тогда <br…»)
 
Строка 3: Строка 3:
 
Эдмондса - Лоулера
 
Эдмондса - Лоулера
 
|statement= Пусть <tex>M_1=<X, I_1></tex>, <tex>M_2=<X, I_2></tex> - матроиды. Тогда <br>
 
|statement= Пусть <tex>M_1=<X, I_1></tex>, <tex>M_2=<X, I_2></tex> - матроиды. Тогда <br>
<tex>\max_{I \in I_1 \cap I_2 } = \min_{A \subseteq X} r_1(A) + r_2(X \setminus A)</tex>
+
<tex>\max_{I \in I_1 \cap I_2 } |I| = \min_{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_{I \in I_1 \cap I_2 } |I| \le \min_{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 \setminus A|</tex> <br>
 +
<tex>I \cap A</tex> и <tex>I \setminus A</tex> - независимые в обоих матроидах (как подмножества независимового <tex>I</tex>), значит
 +
<tex>|I| = r_1(I \cap A) + r_2(I \setminus A)</tex> <br>
 +
Но <tex>r_1(I \cap A) \le r_1(A)</tex> и <tex>r_2(I \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_{I \in I_1 \cap I_2 } |I| \le \min_{A \subseteq X} r_1(A) + r_2(X \setminus A)</tex>
 
}}
 
}}

Версия 21:01, 8 мая 2011

Теорема (Эдмондса - Лоулера):
Пусть [math]M_1=\lt X, I_1\gt [/math], [math]M_2=\lt X, I_2\gt [/math] - матроиды. Тогда

[math]\max_{I \in I_1 \cap I_2 } |I| = \min_{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_{I \in I_1 \cap I_2 } |I| \le \min_{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 \setminus A|[/math]
[math]I \cap A[/math] и [math]I \setminus A[/math] - независимые в обоих матроидах (как подмножества независимового [math]I[/math]), значит [math]|I| = r_1(I \cap A) + r_2(I \setminus A)[/math]
Но [math]r_1(I \cap A) \le r_1(A)[/math] и [math]r_2(I \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_{I \in I_1 \cap I_2 } |I| \le \min_{A \subseteq X} r_1(A) + r_2(X \setminus A)[/math]
[math]\triangleleft[/math]