Изменения

Перейти к: навигация, поиск

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

1797 байт добавлено, 21:20, 14 июня 2011
Нет описания правки
{{Лемма
|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>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) \cup \{u\}</tex> как <tex>A'</tex>. Заметим, такое, что <tex>(I \cap A' ) \cup \{z\} \in I_1</tex>.Возможны 2 случая:# Если <tex>A' I \cup \{z\cap I = } \varnothingin I_1</tex>, тогда то <tex>u z \in S</tex>, что приводит к противоречию.# Можно добавлять и из <tex>I \setminus A'S</tex> есть путь в <tex>A'</tex>. Значит, пока <tex>|I| > |A'|\cup \{z\} \notin I_1</tex> (по аксиоме замены в <tex>M_1</tex>). Теперь Отсюда следует, что существует <tex>A' = y \in I \setminus \{z\}A</tex>. , такое что <tex>I \setminus \{zy\} \cup \{uz\} \in I_1</tex>, следовательно, . Но тогда ребро <tex>zu \in G_Iyz</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> достигается равенство.
Построен пример равенства, значит, теорема доказана.
}}
53
правки

Навигация