|
|
| (не показаны 3 промежуточные версии 2 участников) |
| Строка 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=
| |
| − | [[Файл:El_graph2.png|thumb|140px|right|Граф замен, кратчайший путь]] | |
| − | [[Файл:El_graph.png|thumb|140px|right|Завершение алгоритма]]
| |
| − | <div>
| |
| − | Докажем неравенство <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>I \in I_1 \cap I_2</tex>, <tex>A \subseteq X</tex>, тогда
| |
| − | | |
| − | <tex>|I| = |I \cap A| + |I \cap (X \setminus A)|</tex>
| |
| − | | |
| − | <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>
| |
| − | | |
| − | Но <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>
| |
| − | | |
| − | В силу произвольности <tex>I</tex> и <tex>A</tex> получаем
| |
| − | | |
| − | <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>.
| |
| − | | |
| − | Обозначим <tex>S = \left\{x|I \cup \{x\} \in I_1\right\}</tex>, <tex>T = \left\{x|I \cup \{x\} \in I_2\right\}</tex>. Если <tex>S \cap T \ne \varnothing</tex>, добавим их пересечение в <tex>I</tex>.
| |
| − | | |
| − | Построим [[Граф замен для двух матроидов|граф замен]] <tex>G_I</tex>. Добавим вершину <tex>z</tex>, не влияющую на независимость в первом матроиде — из неё будут вести рёбра во все вершины множества <tex>S</tex>. Пусть <tex>p</tex> — кратчайший путь из <tex>S</tex> в <tex>T</tex>, <tex>p_1</tex> — путь <tex>p</tex> с добавленным в начало ребром из <tex>z</tex>. По [[Лемма о единственном паросочетании в графе замен|лемме о единственном паросочетании]] и [[Лемма о единственном паросочетании в подграфе замен, индуцированном кратчайшим путем|лемме о единственном паросочетании, индуцированном кратчайшем путём]] <tex>I \oplus p_1 \in I_2</tex>. Теперь добавим вершину <tex>u</tex>, не влияющую на независимость во втором матроиде — в неё будут вести рёбра из всех вершин множества <tex>T</tex>. Тогда <tex>p_2</tex> (путь <tex>p</tex> с добавленным ребром в <tex>u</tex>) — кратчайший путь из <tex>S</tex> в <tex>u</tex>. Аналогично, <tex>I \oplus p_2 \in I_1</tex>. Отсюда следует, что <tex>I \oplus p \in I_1 \cap I_2</tex>, причём <tex>|I \oplus p| = |I| + 1</tex>.</div>
| |
| − | | |
| − | Будем таким образом увеличивать <tex>I</tex>, пока существует путь <tex>p</tex>. Рассмотрим момент, когда такого пути не нашлось.
| |
| − | Введём обозначение: <tex>A = \{u|u \rightsquigarrow T\}</tex>.
| |
| − | | |
| − | Докажем, что <tex>r_1(A) = |I \cap A|</tex> от противного.
| |
| − | Пусть <tex>r_1(A) > |I \cap A|</tex>, тогда существует <tex>w \in A \setminus (I \cap A)</tex>, такое, что <tex>(I \cap A) \cup \{w\} \in I_1</tex>. Если <tex>I \cup \{w\} \in I_1</tex>, то <tex>w \in S</tex> и из <tex>S</tex> есть путь в <tex>A</tex>. Значит, <tex>I \cup \{w\} \notin I_1</tex>. Отсюда следует, что существует <tex>y \in I \setminus A</tex>, такое что <tex>I \setminus \{y\} \cup \{w\} \in I_1</tex>. Но тогда ребро <tex>yw</tex> имеется в графе, то есть из <tex>y</tex> существует путь в <tex>T</tex>, что противоречит условию <tex>y \in I \setminus A</tex>.
| |
| − | | |
| − | Следовательно, <tex>r_1(A) = |I \cap A|</tex>. Аналогично, <tex>r_2(\overline A) = |I \cap \overline A|</tex>. Отсюда <tex>r_1(A) + r_2(\overline A) = |I|</tex>, то есть при найденных <tex>I</tex> и <tex>A</tex> достигается равенство.
| |
| − | | |
| − | Построен пример равенства, значит, теорема доказана.
| |
| − | }}
| |
| − | | |
| − | == Источник ==
| |
| − | ''Chandra Chekuri'' — [http://www.cs.illinois.edu/class/sp10/cs598csc/Lectures/Lecture17.pdf '''Combinatorial Optimization'''], c. 2-4
| |
