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

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 4: Строка 4:
 
==Подготовка к доказательству==
 
==Подготовка к доказательству==
 
Для доказательства мы будем пользоваться развитой раннее [[Определение сети, потока|теорией потоков]]. Кроме базовых определений нам потребуется понятие [[Дополняющая сеть, дополняющий путь| остаточной сети]] (иначе - дополнительной сети), а также [[Теорема_Форда-Фалкерсона|теорема Форда-Фалкерсона]].
 
Для доказательства мы будем пользоваться развитой раннее [[Определение сети, потока|теорией потоков]]. Кроме базовых определений нам потребуется понятие [[Дополняющая сеть, дополняющий путь| остаточной сети]] (иначе - дополнительной сети), а также [[Теорема_Форда-Фалкерсона|теорема Форда-Фалкерсона]].
 
//что-то про разрез .. [[Разрез, лемма о потоке через разрез]]
 
  
 
Кроме того потребуется лемма о целочисленности потока, которую сейчас и докажем:
 
Кроме того потребуется лемма о целочисленности потока, которую сейчас и докажем:
Строка 33: Строка 31:
  
 
:Назначим каждому ребру пропускную способность 1. Тогда существует максимальный поток, целочисленный на каждом ребре(по лемме).  
 
:Назначим каждому ребру пропускную способность 1. Тогда существует максимальный поток, целочисленный на каждом ребре(по лемме).  
:По теореме Форда-Фалкерсона для такого потока существует разрез с пропускной способностью равной потоку (и этот разрез минимален среди всех возможных разрезов). По условию «после удаления <tex>\forall L-1</tex> (и в частности тех, что находятся в нашем разрезе) ребер все еще <tex>\exists</tex> путь из <tex>u</tex> в <tex>v</tex>», значит пропускная способность разреза <tex>\geqslant L = |f|</tex>. А так как поток целочисленный, то это и означает, что <tex>\exists L</tex> реберно непересекающихся путей (чуть позже дадим аккуратное объяснение этому).
+
:По теореме Форда-Фалкерсона для такого потока существует разрез с пропускной способностью равной потоку. По условию «после удаления <tex>\forall L-1</tex> (и в частности тех, что находятся в нашем разрезе) ребер все еще будет <tex>\exists</tex> путь из <tex>u</tex> в <tex>v</tex>», значит пропускная способность разреза и вместе с ним величина потока <tex>\geqslant L</tex>. А так как поток целочисленный, то это и означает, что <tex>\exists L</tex> реберно непересекающихся путей (чуть позже дадим аккуратное объяснение этому).
  
 
:<tex>\Rightarrow</tex>
 
:<tex>\Rightarrow</tex>
Строка 39: Строка 37:
 
}}
 
}}
  
 +
// Логично переместить в раздел "подготовка к доказательству"
 
Небольшой комментарий к доказательству <tex>\Leftarrow</tex>:
 
Небольшой комментарий к доказательству <tex>\Leftarrow</tex>:
  
 
''Если в сети, где все пропускные способности равны 1 существует целочисленный поток величиной <tex>L</tex> то существует и <tex>L</tex> реберно непересекающихся путей.''
 
''Если в сети, где все пропускные способности равны 1 существует целочисленный поток величиной <tex>L</tex> то существует и <tex>L</tex> реберно непересекающихся путей.''
  
Поясним это: найдем какой-нибудь маршрут из <tex>u</tex> в <tex>v</tex> лежащий только на ребрах где поток равен 1. Такой маршут обязательно существует, пока величина потока больше 0 (нетрудно показать, что иначе придем к противоречию). Удалив все ребра находящиеся в этом маршруте и оставив все остальное неизменным, придем к потоку величиной <tex>L-1</tex>. Ясно, что можно повторить тоже самое еще <tex>L-1</tex> раз, и, таким образом мы неизбежно выделим <tex>L</tex> реберно непересекающихся маршрутов, что и требуется.
+
Поясним это: найдем какой-нибудь маршрут из <tex>u</tex> в <tex>v</tex> лежащий только на ребрах где поток равен 1. Такой маршут обязательно существует, пока величина потока больше 0 (иначе легко получается противоречие: рассмотрим множество вершин достижимых по ненулевым ребрам из стока и построим по нему разрез. Пропускная способность разреза равна 0, значит и поток должен быть не больше 0). Удалив все ребра находящиеся в этом маршруте и оставив все остальное неизменным, придем к потоку величиной <tex>L-1</tex>. Ясно, что можно повторить тоже самое еще <tex>L-1</tex> раз, и, таким образом мы неизбежно выделим <tex>L</tex> реберно непересекающихся маршрутов, что и требуется.
  
 
//все остальные теоремы
 
//все остальные теоремы

Версия 00:19, 23 октября 2011

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

Теорема Менгера представляет собой группу теорем, связывающих такие понятия на графах как k-связность и количество непересекающихся путей относительно двух выделенных вершин. Возникают различные варианты очень похожих друг на друга по формулировке теорем в зависимости от того, рассматриваем ли мы ситуацию в ориентированном или неориентированном графе, и подразумеваем ли реберную k-связность и реберно непересекающиеся пути или же вершинную 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]
[math]\Leftarrow[/math]
Назначим каждому ребру пропускную способность 1. Тогда существует максимальный поток, целочисленный на каждом ребре(по лемме).
По теореме Форда-Фалкерсона для такого потока существует разрез с пропускной способностью равной потоку. По условию «после удаления [math]\forall L-1[/math] (и в частности тех, что находятся в нашем разрезе) ребер все еще будет [math]\exists[/math] путь из [math]u[/math] в [math]v[/math]», значит пропускная способность разреза и вместе с ним величина потока [math]\geqslant L[/math]. А так как поток целочисленный, то это и означает, что [math]\exists L[/math] реберно непересекающихся путей (чуть позже дадим аккуратное объяснение этому).
[math]\Rightarrow[/math]
[math]\exists L[/math] реберно непересекающихся путей, а значит удалив любых [math]L-1[/math] ребер хотя бы один путь останется останется не тронутым (принцип Дирихле). Это и означает [math]\exists[/math] путь из [math]u[/math] в [math]v[/math].
[math]\triangleleft[/math]

// Логично переместить в раздел "подготовка к доказательству" Небольшой комментарий к доказательству [math]\Leftarrow[/math]:

Если в сети, где все пропускные способности равны 1 существует целочисленный поток величиной [math]L[/math] то существует и [math]L[/math] реберно непересекающихся путей.

Поясним это: найдем какой-нибудь маршрут из [math]u[/math] в [math]v[/math] лежащий только на ребрах где поток равен 1. Такой маршут обязательно существует, пока величина потока больше 0 (иначе легко получается противоречие: рассмотрим множество вершин достижимых по ненулевым ребрам из стока и построим по нему разрез. Пропускная способность разреза равна 0, значит и поток должен быть не больше 0). Удалив все ребра находящиеся в этом маршруте и оставив все остальное неизменным, придем к потоку величиной [math]L-1[/math]. Ясно, что можно повторить тоже самое еще [math]L-1[/math] раз, и, таким образом мы неизбежно выделим [math]L[/math] реберно непересекающихся маршрутов, что и требуется.

//все остальные теоремы

Смотри также

Литература

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