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

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 24: Строка 24:
 
Пусть <tex>r_1(A) > |I \cap A|</tex>. Обозначим <tex>(I \cap A) \cup \{u\}</tex> как <tex>A'</tex>. Заметим, что <tex>A' \in I_1</tex>.
 
Пусть <tex>r_1(A) > |I \cap A|</tex>. Обозначим <tex>(I \cap A) \cup \{u\}</tex> как <tex>A'</tex>. Заметим, что <tex>A' \in I_1</tex>.
 
Возможны 2 случая:
 
Возможны 2 случая:
# <tex>\overline{A} \cap I = \varnothing</tex>, тогда <tex>u \in S</tex>, что приводит к противоречию.
+
# <tex>A' \cap I = \varnothing</tex>, тогда <tex>u \in S</tex>, что приводит к противоречию.
 
# Можно добавлять из <tex>I \setminus A'</tex> в <tex>A'</tex>, пока <tex>|I| > |A'|</tex> (по аксиоме замены в <tex>M_1</tex>). Теперь <tex>A' = I \setminus \{z\}</tex>. <tex>I \setminus \{z\} \cup \{u\} \in I_1</tex>, следовательно, ребро <tex>zu \in G_I</tex>, что приводит к противоречию.
 
# Можно добавлять из <tex>I \setminus A'</tex> в <tex>A'</tex>, пока <tex>|I| > |A'|</tex> (по аксиоме замены в <tex>M_1</tex>). Теперь <tex>A' = I \setminus \{z\}</tex>. <tex>I \setminus \{z\} \cup \{u\} \in I_1</tex>, следовательно, ребро <tex>zu \in G_I</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> достигается равенство.
 
Следовательно, <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> достигается равенство.

Версия 23:52, 7 июня 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]B \subset A[/math], в [math]B[/math] существует единственное полное паросочетание. Тогда [math]A \oplus B[/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](I \cap A) \cup \{u\}[/math] как [math]A'[/math]. Заметим, что [math]A' \in I_1[/math]. Возможны 2 случая:

  1. [math]A' \cap I = \varnothing[/math], тогда [math]u \in S[/math], что приводит к противоречию.
  2. Можно добавлять из [math]I \setminus A'[/math] в [math]A'[/math], пока [math]|I| \gt |A'|[/math] (по аксиоме замены в [math]M_1[/math]). Теперь [math]A' = I \setminus \{z\}[/math]. [math]I \setminus \{z\} \cup \{u\} \in I_1[/math], следовательно, ребро [math]zu \in G_I[/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]