Теорема Менгера — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 3: Строка 3:
  
 
==Подготовка к доказательству==
 
==Подготовка к доказательству==
Для доказательства мы воспользуемся развитой [[Определение сети, потока|теорией потоков]]. Кроме базовых определений нам потребуются понятия [[Дополняющая сеть, дополняющий путь| остаточной сети]] (иначе - дополнительной сети), а также [[Теорема_Форда-Фалкерсона|теорема Форда-Фалкерсона]]. Кроме того потребуется лемма о целочисленности потока, которую сейчас и докажем:
+
Для доказательства мы будем ползьоваться развитой раннее [[Определение сети, потока|теорией потоков]]. Кроме базовых определений нам потребуется понятие [[Дополняющая сеть, дополняющий путь| остаточной сети]] (иначе - дополнительной сети), а также [[Теорема_Форда-Фалкерсона|теорема Форда-Фалкерсона]]. Кроме того потребуется лемма о целочисленности потока, которую сейчас и докажем:
 
{{Лемма
 
{{Лемма
 
|about=о целочисленности потока
 
|about=о целочисленности потока

Версия 06:58, 22 октября 2011

Эта статья находится в разработке!

Теорема Менгера представляет собой группу теорем, связывающих такие понятия на графах как k-связность и количество непересекающихся путей относительно двух выделенных вершин. Возникают различные варианты очень похожих друг на друга по формулировке теорем в зависимости от того, рассматриваем ли мы ситуацию в ориентированном или неориентированном графе, и подразумеваем ли реберную связность и реберно непересекающиеся пути или же вершинную связность и вершинно непересекающиеся пути.

Подготовка к доказательству

Для доказательства мы будем ползьоваться развитой раннее теорией потоков. Кроме базовых определений нам потребуется понятие остаточной сети (иначе - дополнительной сети), а также теорема Форда-Фалкерсона. Кроме того потребуется лемма о целочисленности потока, которую сейчас и докажем:

Лемма (о целочисленности потока):
      Если пропускные способности всех ребер целочисленные (сеть целочислена), то существует максимальный поток, целочисленный на каждом ребре.
Доказательство:
[math]\triangleright[/math]
Для доказательства достаточно рассмотреть алгоритм Форда-Фалкерсона для поиска максимального потока. Алгоритм делает примерно следующее (подробней - читай в соответствующей статье):
1. В начале берем какой-нибудь поток за начальный (например, нулевой).
2. В остаточной сети этого потока находим какой-нибудь путь из источника к стоку и увеличиваем поток на пропускную способность этого пути.
3. Повторяем пункт 2 до тех пор, пока находится хоть какой-то путь в остаточной сети.
То, что получится в конце, будет максимальным потоком. В случае целочисленной сети достаточно в качестве начального приближения взять нулевой поток, и не трудно видеть, что на каждой итерации (в том числе и последней) этот поток будет оставаться целочисленным, что и докажет требуемое.
[math]\triangleleft[/math]

Теорема

Теперь сама теорема будет тривиальным следствием. В начале сформулируем реберную версию для случая ориентированного графа.

Теорема (Менгера о реберной двойственности в ориентированном графе):
Между вершинами [math]u[/math] и [math]v\; \exists L[/math] реберно непересекающихся путей [math]\Leftrightarrow[/math] после удаления [math]\forall L-1[/math] ребер [math]\exists[/math] путь из [math]u[/math] в [math]v[/math].
Доказательство:
[math]\triangleright[/math]
Назначим каждому ребру пропускную способность 1. Тогда существует максимальный поток целочисленный на каждом ребре(по лемме). Рассмотрим минимальный
[math]\triangleleft[/math]

Литература

  • Ловас Л., Пламмер М. Прикладные задачи теории графов. Теория паросочетаний в математике, физике, химии 1998. 656 с. ISBN 5-03-002517-0 (глава 2.4 стр. 117)