Изменения

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

Для доказательства мы будем пользоваться развитой раннее [[Определение сети, потока|теорией потоков]]. Кроме базовых определений нам потребуется понятие [[Дополняющая сеть, дополняющий путь| остаточной сети]] (иначе {{- --}} дополнительной сети), а также [[Теорема_Форда-Фалкерсона|теорема Форда-Фалкерсона]].

Кроме того , потребуется лемма о целочисленности потока, которую сейчас и докажем:

:Для доказательства достаточно рассмотреть [[Алгоритм Форда-Фалкерсона, реализация с помощью поиска в глубину|алгоритм Форда-Фалкерсона]] для поиска максимального потока. Алгоритм делает примерно следующее (подробней {{- --}} читай в соответствующей статье):

:''1.'' # В начале берем какой-нибудь поток за начальный (например, нулевой).:# В остаточной сети этого потока находим какой-нибудь путь из источника к стоку и увеличиваем поток на пропускную способность этого пути.:# Повторяем пункт <tex>2</tex> до тех пор, пока находится хоть какой-то путь в остаточной сети.

:''2То, что получится в конце, будет максимальным потоком.'' В остаточной случае целочисленной сети этого потока находим какой-нибудь путь из источника к стоку достаточно в качестве начального приближения взять нулевой поток, и увеличиваем не трудно видеть, что на каждой итерации (в том числе и последней) этот поток на пропускную способность этого путибудет оставаться целочисленным, что и докажет требуемое.}}

И, наконец, сделаем немного более осознанным в общем-то и так интуитивно понятное утверждение:''3{{Утверждение|statement=Если в сети, где все пропускные способности ребер равны <tex>1</tex>, существует целочисленный поток величиной <tex>L</tex> то существует и <tex>L</tex> реберно непересекающихся путей.'' Повторяем пункт ''2'' до тех пор|proof=: Считаем, что <tex>u</tex> {{---}} источник, пока находится хоть какой<tex>v</tex> {{---}} сток.: В начале поймем, что если поток не нулевой, то путь существует маршрут из <tex>u</tex> в остаточной сети<tex>v</tex> лежащий только на ребрах с потоком равным <tex>1</tex>. В самом деле, если бы такого маршрута не существовало, то можно было бы выделить множество вершин до которых такие маршруты из вершины <tex>u</tex> существуют, не включающее <tex>v</tex>, и по нему построить разрез. Поток через такой разрез, очевидно равен нулю, видим противоречие (т.к. <tex>f(U,V)=|f|</tex>, смотри [[Разрез, лемма о потоке через разрез|первую лемму]]).

:ТоИтак, что получится найдем какой-нибудь маршрут из <tex>u</tex> в конце, будет максимальным потоком<tex>v</tex> лежащий только на ребрах где поток равен <tex>1</tex>. В случае целочисленной сети достаточно Удалив все ребра находящиеся в качестве начального приближения взять нулевой потокэтом маршруте и оставив все остальное неизменным, и не трудно видетьпридем к целочисленному потоку величиной <tex>L-1</tex>. Ясно, что на каждой итерации (в том числе можно повторить тоже самое еще <tex>L-1</tex> раз, и последней) этот поток будет оставаться целочисленным, что и докажет требуемоетаким образом мы выделим <tex>L</tex> реберно непересекающихся маршрутов.

|statement=Между вершинами <tex>u</tex> и <tex>v\; \exists L</tex> реберно непересекающихся путей существует <tex>\LeftrightarrowL</tex> реберно непересекающихся путей тогда и только тогда, когда после удаления любых <tex>\forall (L-1)</tex> ребер <tex>\exists</tex> существует путь из <tex>u</tex> в <tex>v</tex>.

:<tex>\Leftarrow</tex> :Как и прежде, пусть <tex>u</tex> {{---}} источник, а <tex>v</tex> {{---}} сток. :Назначим каждому ребру пропускную способность <tex>1</tex>. Тогда существует максимальный поток, целочисленный на каждом ребре (по лемме). :По теореме Форда-Фалкерсона для такого потока существует разрез с пропускной способностью равной потоку. Удалим в этом разрезе <tex>L-1</tex> ребер, и тогда, раз <tex>u</tex> и <tex>v</tex> находятся в разных частях разреза и, существует путь из <tex>u</tex> в <tex>v</tex>, то в разрезе останется хотя бы еще одно ребро. Это значит, что пропускная способность разреза и вместе с ним величина потока не меньше <tex>L</tex>. А так как поток целочисленный, то это и означает, что найдется <tex> L</tex> реберно непересекающихся путей.

:Назначим каждому ребру пропускную способность 1. Тогда существует максимальный поток, целочисленный на каждом ребре(по лемме). <tex>\Rightarrow</tex> :По теореме Форда-Фалкерсона для такого потока существует разрез с пропускной способностью равной потоку. По условию «после удаления Существует <tex>\forall L-1</tex> (и в частности техреберно непересекающихся путей, а значит, что находятся в нашем разрезе) ребер все еще будет удалив любые <tex>\existsL-1</tex> ребер хотя бы один путь останется не тронутым (принцип Дирихле). Это и означает, что существует путь из <tex>u</tex> в <tex>v</tex>», значит пропускная способность разреза и вместе с ним величина потока <tex>\geqslant L</tex>. А так как поток целочисленный, то это и означает, что <tex>\exists L</tex> реберно непересекающихся путей.}}

:{{Теорема|about=Менгера о вершинной двойственности в ориентированном графе|statement=Между вершинами <tex>u</tex>\Rightarrowи <tex>v</tex>:существует <tex>\exists L</tex> реберно вершинно непересекающихся путейтогда и только тогда, а значит удалив когда после удаления любых <tex>(L-1</tex> ребер хотя бы один путь останется останется не тронутым (принцип Дирихле). Это и означает <tex>\exists</tex> вершин существует путь из <tex>u</tex> в <tex>v</tex>.}}|proof=

==Примечание==:''Если (все входящие ребра заходят в сетилевую вершину, где все пропускные способности равны 1 существует целочисленный поток величиной <tex>L</tex> то существует и <tex>L</tex> реберно непересекающихся путейисходящие выходят из правой.между двумя новыми вершинами добавляем ребро)''

Поясним это: найдем какой-нибудь маршрут из <tex>u</tex> Теперь задача практически сведена к первой теореме.:Необходимо лишь отметить, что если в <tex>v</tex> лежащий только на ребрах где поток равен 1. Такой маршут обязательно существуетстаром графе пути вершинно пересекаются, пока величина потока больше 0 (иначе сразу получаем противоречие: рассмотрим множество вершин достижимых по ненулевым ребрам из стока то в новом графе пути необходимо реберно пересекаются и построим по нему разрезнаоборот. Пропускная способность разреза равна 0:Кроме того, значит и поток должен быть равен 0). Удалив все ребра находящиеся предложение "удалить в этом маршруте и оставив все остальное неизменным, придем к потоку величиной исходном графе любые <tex>L-1</tex>. Ясно, что вершин" можно заменять на "в новом графе можно повторить тоже самое еще удалить любые <tex>L-1</tex> разребер" (достаточно выбирать вершины на концах этих ребер). Можно заменять и обратно, если учесть, ичто можно удалять ребра между парой вершин, таким образом мы выделим <tex>Lкоторые раньше были одним целым.}}</texincludeonly> реберно непересекающихся маршрутовТеоремы для неориентированного графа формулируются идентично, что и требуется.а их доказательства сводятся к своим ориентированным двойникам путем замены каждого ребра на две дуги:

[[Файл:Menger_undirected.JPG‎]]</includeonly> ==Смотри См. также==

* [[wikipedia:Menger's theorem | Wikipedia {{---}} Menger's theorem ]] ==ЛитератураИсточники информации==* Ловас Л., Пламмер М. {{---}} '''Прикладные задачи теории графов. Теория паросочетаний в математике, физике, химии''' (глава 2.4 стр. 117) {{---}} 1998. {{---}} 656 с. {{---}} ISBN 5-03-002517-0 * Харари Ф. '''Теория графов.''' глава 5 — М.: Мир, 1973. (глава 2Изд. 3, М.: КомКнига, 2006.4 стр— 296 с. 117)