Материал из Викиконспекты
|
|
| (не показано 12 промежуточных версий 4 участников) |
| Строка 1: |
Строка 1: |
| − | == Условие теоремы ==
| + | #перенаправление [[Алгоритм_построения_базы_в_пересечении_матроидов]] |
| − | {{Теорема
| |
| − | |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> <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>
| |
| − | | |
| − | | |
| − | Конструктивно построим <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>.
| |
| − | }}
| |
Текущая версия на 22:17, 7 июня 2015
