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

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

Внимание! Вы не авторизовались на сайте. Ваш IP-адрес будет публично видимым, если вы будете вносить любые правки. Если вы войдёте или создадите учётную запись, правки вместо этого будут связаны с вашим именем пользователя, а также у вас появятся другие преимущества.

Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия Ваш текст
Строка 31: Строка 31:
 
Будем таким образом увеличивать <tex>I</tex>, пока существует путь <tex>p</tex>. Рассмотрим момент, когда такого пути не нашлось.
 
Будем таким образом увеличивать <tex>I</tex>, пока существует путь <tex>p</tex>. Рассмотрим момент, когда такого пути не нашлось.
 
Введём обозначение: <tex>A = \{u|u \rightsquigarrow T\}</tex>. Докажем, что <tex>r_1(A) = |I \cap A|</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>(I \cap A) \cup \{u\}</tex> как <tex>A'</tex>. Заметим, что <tex>A' \in I_1</tex>.
 
+
Возможны 2 случая:
 +
# <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>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> достигается равенство.
  
 
Построен пример равенства, значит, теорема доказана.  
 
Построен пример равенства, значит, теорема доказана.  
 
}}
 
}}

Пожалуйста, учтите, что любой ваш вклад в проект «Викиконспекты» может быть отредактирован или удалён другими участниками. Если вы не хотите, чтобы кто-либо изменял ваши тексты, не помещайте их сюда.
Вы также подтверждаете, что являетесь автором вносимых дополнений, или скопировали их из источника, допускающего свободное распространение и изменение своего содержимого (см. Викиконспекты:Авторские права). НЕ РАЗМЕЩАЙТЕ БЕЗ РАЗРЕШЕНИЯ ОХРАНЯЕМЫЕ АВТОРСКИМ ПРАВОМ МАТЕРИАЛЫ!

Чтобы изменить эту страницу, пожалуйста, ответьте на приведённый ниже вопрос (подробнее):

Отменить | Справка по редактированию (в новом окне)

Шаблоны, используемые на этой странице: