Доказательство теоремы Эдмондса-Лоулера — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Новая страница: «== Условие теоремы == {{Теорема |about= Эдмондса - Лоулера |statement= Пусть <tex>M_1=\langle X, I_1\rangle</tex>, <tex>M_2=…»)
 
(не показано 9 промежуточных версий 2 участников)
Строка 1: Строка 1:
== Условие теоремы ==
 
 
{{Теорема
 
{{Теорема
 
|about=
 
|about=
Строка 7: Строка 6:
 
Где <tex>r_1</tex> и <tex>r_2</tex> — ранговые функции в первом и втором матроиде соответственно.
 
Где <tex>r_1</tex> и <tex>r_2</tex> — ранговые функции в первом и втором матроиде соответственно.
 
|proof=
 
|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>.
+
Неравенство <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>.
 +
 
 +
{{Лемма
 +
|about=1
 +
|statement = <tex>A</tex> — независимое множество в матроиде <tex>M=\langle X, I\rangle</tex>. <tex>B \subset X</tex>, <tex>|B|=|A|</tex> и в подграфе графа замен <tex>G_M</tex>, индуцированном <tex>A \oplus B</tex>, существует единственное полное паросочетание. Тогда <tex>B</tex> — независимое в матроиде <tex>M</tex>.
 +
|proof=
 +
[[Файл:El_lemma2.png|thumb|right|Граф <tex>G</tex>]]
 +
Обозначим граф (неориентированный), индуцированный <tex>A \oplus B</tex> за <tex>G</tex>. Обозначим вершины из <tex>A \setminus B</tex> за <tex>y_i</tex>, из <tex>B \setminus A</tex> за <tex>z_i</tex>. Перенумеруем вершины так, чтобы рёбра из паросочетания соединяли вершины с одинаковыми индексами, и <tex>\forall i,j: i < j</tex> не существовало бы ребра между вершинами <tex>y_i</tex> и <tex>z_j</tex> (возможность первого следует из существования полного паросочетания, второго — из его единственности).
 +
 
 +
Пусть <tex>B</tex> — не независимо, значит, <tex>\exists</tex> цикл <tex>C \subset B</tex>. Обозначим <tex>i = \min k: z_k \in C</tex>.
 +
 
 +
<tex>\forall j > i \quad y_iz_j \notin G(A) \Rightarrow A \setminus y_i \cup z_j \notin I \Rightarrow C \setminus z_i \subseteq \langle A \setminus y_i \rangle</tex>.
 +
 
 +
Так как <tex>C</tex> — цикл, то <tex>C \subseteq \langle C \setminus z_i \rangle \subseteq \langle A \setminus y_i \rangle</tex>. Это означает, что <tex>z_i \in \langle A \setminus y_i \rangle</tex>, и, следовательно, <tex> A \setminus y_i \cup z_i \notin I</tex>, что приводит к противоречию с существованием ребра <tex>y_i z_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>. По лемме 1 и [[Лемма о единственном паросочетании в подграфе замен, индуцированном кратчайшим путем|лемме о единственном паросочетании]] <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>.
 +
 
 +
Будем таким образом увеличивать <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>z \in A \setminus (I \cap A)</tex>, такое, что <tex>(I \cap A) \cup \{z\} \in I_1</tex>. Если <tex>I \cup \{z\} \in I_1</tex>, то <tex>z \in S</tex> и из <tex>S</tex> есть путь в <tex>A</tex>. Значит, <tex>I \cup \{z\} \notin I_1</tex>. Отсюда следует, что существует <tex>y \in I \setminus A</tex>, такое что <tex>I \setminus \{y\} \cup \{z\} \in I_1</tex>. Но тогда ребро <tex>yz</tex> имеется в графе, что противоречит отсутствию пути из <tex>S</tex> в <tex>T</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> достигается равенство.
 +
 
 +
Построен пример равенства, значит, теорема доказана.  
 
}}
 
}}

Версия 21:20, 14 июня 2011

Теорема (Эдмондса - Лоулера):
Пусть [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]\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]S = \left\{x|I \cup \{x\} \in I_1\right\}[/math], [math]T = \left\{x|I \cup \{x\} \in I_2\right\}[/math]. Если [math]S \cap T \ne \varnothing[/math], добавим их пересечение в [math]I[/math].

Лемма (1):
[math]A[/math] — независимое множество в матроиде [math]M=\langle X, I\rangle[/math]. [math]B \subset X[/math], [math]|B|=|A|[/math] и в подграфе графа замен [math]G_M[/math], индуцированном [math]A \oplus B[/math], существует единственное полное паросочетание. Тогда [math]B[/math] — независимое в матроиде [math]M[/math].
Доказательство:
[math]\triangleright[/math]
Граф [math]G[/math]

Обозначим граф (неориентированный), индуцированный [math]A \oplus B[/math] за [math]G[/math]. Обозначим вершины из [math]A \setminus B[/math] за [math]y_i[/math], из [math]B \setminus A[/math] за [math]z_i[/math]. Перенумеруем вершины так, чтобы рёбра из паросочетания соединяли вершины с одинаковыми индексами, и [math]\forall i,j: i \lt j[/math] не существовало бы ребра между вершинами [math]y_i[/math] и [math]z_j[/math] (возможность первого следует из существования полного паросочетания, второго — из его единственности).

Пусть [math]B[/math] — не независимо, значит, [math]\exists[/math] цикл [math]C \subset B[/math]. Обозначим [math]i = \min k: z_k \in C[/math].

[math]\forall j \gt i \quad y_iz_j \notin G(A) \Rightarrow A \setminus y_i \cup z_j \notin I \Rightarrow C \setminus z_i \subseteq \langle A \setminus y_i \rangle[/math].

Так как [math]C[/math] — цикл, то [math]C \subseteq \langle C \setminus z_i \rangle \subseteq \langle A \setminus y_i \rangle[/math]. Это означает, что [math]z_i \in \langle A \setminus y_i \rangle[/math], и, следовательно, [math] A \setminus y_i \cup z_i \notin I[/math], что приводит к противоречию с существованием ребра [math]y_i z_i[/math].
[math]\triangleleft[/math]

Построим граф замен [math]G_I[/math]. Добавим вершину [math]z[/math], не влияющую на независимость в первом матроиде — из неё будут вести рёбра во все вершины множества [math]S[/math]. Пусть [math]p[/math] — кратчайший путь из [math]S[/math] в [math]T[/math], [math]p_1[/math] — путь [math]p[/math] с добавленным в начало ребром из [math]z[/math]. По лемме 1 и лемме о единственном паросочетании [math]I \oplus p_1 \in I_2[/math]. Теперь добавим вершину [math]u[/math], не влияющую на независимость во втором матроиде — в неё будут вести рёбра из всех вершин множества [math]T[/math]. Тогда [math]p_2[/math] (путь [math]p[/math] с добавленным ребром в [math]u[/math]) — кратчайший путь из [math]S[/math] в [math]u[/math]. Аналогично, [math]I \oplus p_2 \in I_1[/math]. Отсюда следует, что [math]I \oplus p \in I_1 \cap I_2[/math], причём [math]|I \oplus p| = |I| + 1[/math].

Будем таким образом увеличивать [math]I[/math], пока существует путь [math]p[/math]. Рассмотрим момент, когда такого пути не нашлось. Введём обозначение: [math]A = \{u|u \rightsquigarrow T\}[/math]. Докажем, что [math]r_1(A) = |I \cap A|[/math] от противного. Пусть [math]r_1(A) \gt |I \cap A|[/math], тогда существует [math]z \in A \setminus (I \cap A)[/math], такое, что [math](I \cap A) \cup \{z\} \in I_1[/math]. Если [math]I \cup \{z\} \in I_1[/math], то [math]z \in S[/math] и из [math]S[/math] есть путь в [math]A[/math]. Значит, [math]I \cup \{z\} \notin I_1[/math]. Отсюда следует, что существует [math]y \in I \setminus A[/math], такое что [math]I \setminus \{y\} \cup \{z\} \in I_1[/math]. Но тогда ребро [math]yz[/math] имеется в графе, что противоречит отсутствию пути из [math]S[/math] в [math]T[/math].

Следовательно, [math]r_1(A) = |I \cap A|[/math]. Аналогично, [math]r_2(\overline A) = |I \cap \overline A|[/math]. Отсюда [math]r_1(A) + r_2(\overline A) = |I|[/math], то есть при найденных [math]I[/math] и [math]A[/math] достигается равенство.

Построен пример равенства, значит, теорема доказана.
[math]\triangleleft[/math]