Изменения

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

Теорема Менгера

1649 байт добавлено, 05:08, 22 октября 2011
Нет описания правки
{{В разработке}}
Теорема Менгера представляет собой группу теорем, связывающих такие понятия на графах как ''k-связность'' и ''количество непересекающихся путей'' относительно двух выделенных вершин. Возникают различные варианты очень похожих друг на друга по формулировке теорем в зависимости от того, рассматриваем ли мы ситуацию в ''ореинтированном'' или ''неореинтированном'' графе, и подразумеваем ли ''реберную связность'' и ''реберно непересекающиеся пути'' или же ''вершинную связность'' и ''вершинно непересекающиеся пути''.
// Здесь Для доказательства мы воспользуемся развитой [[Определение сети, потока|теорией потоков]]. Кроме базовых определений нам потребуются понятия [[Дополняющая сеть, дополняющий путь| остаточной сети]] (иначе - дополнительной сети), а также [[Теорема_Форда-Фалкерсона|теорема Форда-Фалкерсона]]. Кроме того потребуется лемма о целочисленности потока, которую сейчас и докажем:{{Лемма|about=о целочисленности потока|statement=      Если пропускные способности всех ребер целочисленные (сеть целочислена), то существует максимальный поток, целочисленный на каждом ребре.|proof=:Для доказательства достаточно рассмотреть [[Алгоритм Форда-Фалкерсона, реализация с помощью поиска в глубину|алгоритм Форда-Фалкерсона]] для поиска максимального потока. Алгоритм делает примерно следующее (подробней - читай в соответствующей статье): :''1.'' В начале берем какой-нибудь поток за начальный (например, нулевой). :''2.'' В остаточной сети этого потока находим какой-нибудь путь из источника к стоку и увеличиваем поток на пропускную способность этого пути. :''3.'' Повторяем пункт ''2'' до тех пор, пока наброскинаходится хоть какой-то путь в остаточной сети. :То, что получится в конце, будет максимальным потоком. В случае целочисленной сети достаточно в качестве начального приближения взять нулевой поток, и не трудно видеть, что на каждой итерации (в том числе и последней) этот поток будет оставаться целочисленным, что и докажет требуемое.}} Теперь сама теорема будет тривиальным следствием. Не ищите структурыВ начале сформулируем реберную версию для случая ореинтированного графа.
{{Теорема
|about=Менгера о реберной двойственностив ореинтированном графе
|statement=Между вершинами <tex>u</tex> и <tex>v\; \exists L</tex> реберно непересекающихся путей <tex>\Leftrightarrow</tex> после удаления <tex>\forall L-1</tex> ребер <tex>\exists</tex> путь из <tex>u</tex> в <tex>v</tex>.
|proof=
Для доказательства мы воспользуемся [[Определение сети, потока|теорией потоков]]Назначим каждому ребру пропускную способность 1. Нам потребуются понятия [[Дополняющая сеть, дополняющий путь| остаточной сети]] (иначе - дополнительной сети), а также [[Теорема_Форда-Фалкерсона|теорема Форда-Фалкерсона]]. Кроме того потребуется лемма о целочисленности потока, которую сейчас и докажем: }}{{Лемма|about=о целочисленности потока|statement=Если пропускные способности всех ребер целочисленные (сеть целочислена), то Тогда существует максимальный поток, целочисленный на каждом ребре.|proof=Для доказательства достаточно рассмотреть [[Алгоритм Форда-Фалкерсона, реализация с помощью поиска в глубину|алгоритм Форда-Фалкерсона]]. Алгоритм делает примерно следующее (подробней - читай в соответствующей статье): в начале берет какой-нибудь поток за начальный (например, нулевойпо лемме). Затем в остаточной сети этого потока находит какой-нибудь путь из источника к стоку и увеличивает поток на пропускную способность этого пути. Так он повторяет до тех пор, пока находится хоть какой-то путь в остаточной сети. То что получится будет максимальным потоком. В случае целочисленной сети достаточно в качестве начального приближения взять нулевой поток, и на каждой итерации (в том числе и последней) этот поток будет оставаться целочисленным, что и докажет требуемое.Рассмотрим минимальный
}}
==Литература==
Dmitriy D.
223
правки
Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Служебная:Сравнение_версий/11747»

Навигация