Изменения

==Подготовка к доказательству==Для доказательства мы будем пользоваться развитой раннее [[Определение сети, потока|теорией потоков]]. Кроме базовых определений нам потребуется понятие [[Дополняющая сеть, дополняющий путь| остаточной сети]] (иначе {{---}} дополнительной сети), а также [[Теорема_Форда-Фалкерсона|теорема Форда-Фалкерсона]]. Кроме того, потребуется лемма о целочисленности потока, которую сейчас и докажем:{{Лемма|about=о целочисленности потока|statement=&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Если пропускные способности всех ребер целочисленные (сеть целочислена), то существует максимальный поток, целочисленный на каждом ребре.|proof=:Для доказательства достаточно рассмотреть [[Алгоритм Форда-Фалкерсона, реализация с помощью поиска в глубину|алгоритм Форда-Фалкерсона]] для поиска максимального потока. Алгоритм делает примерно следующее (подробней {{---}} читай в соответствующей статье): :# В начале берем какой-нибудь поток за начальный (например, нулевой).:# В остаточной сети этого потока находим какой-нибудь путь из источника к стоку и увеличиваем поток на пропускную способность этого пути.:# Повторяем пункт <tex>2</tex> до тех пор, пока находится хоть какой-то путь в остаточной сети. :То, что получится в конце, будет максимальным потоком. В случае целочисленной сети достаточно в качестве начального приближения взять нулевой поток, и не трудно видеть, что на каждой итерации (в том числе и последней) этот поток будет оставаться целочисленным, что и докажет требуемое.}} И, наконец, сделаем немного более осознанным в общем-то и так интуитивно понятное утверждение:{{Утверждение|statement=Если в сети, где все пропускные способности ребер равны <tex>1</ Здесь пока наброскиtex>, существует целочисленный поток величиной <tex>L</tex> то существует и <tex>L</tex> реберно непересекающихся путей.|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> реберно непересекающихся маршрутов.}} ==Теорема==Теперь сама теорема будет тривиальным следствием. Не ищите структурыВ начале сформулируем и докажем реберную версию для случая ориентированного графа.

|about=Менгера о реберной двойственностив ориентированном графе|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> реберно непересекающихся путей.

 {{ЛеммаТеорема|about=Менгера о целочисленности потокавершинной двойственности в ориентированном графе|statement=Если пропускные способности всех ребер целочисленные Между вершинами <tex>u</tex> и <tex>v</tex> существует <tex>L</tex> вершинно непересекающихся путей тогда и только тогда, когда после удаления любых <tex>(сеть целочисленаL-1), то </tex> вершин существует максимальный поток, целочисленный на каждом ребрепуть из <tex>u</tex> в <tex>v</tex>.|proof=Для доказательства достаточно рассмотреть  :Разобьем каждую вершину на две таким образом: :[[Алгоритм ФордаФайл:Menger-Фалкерсона, реализация с помощью поиска в глубину|алгоритм Форда-Фалкерсонаvertex.JPG]]. Алгоритм делает примерно следующее  :''(подробней - читай все входящие ребра заходят в соответствующей статьелевую вершину, исходящие выходят из правой. между двумя новыми вершинами добавляем ребро)'' : в начале берет какой-нибудь поток за начальный (напримерТеперь задача практически сведена к первой теореме.:Необходимо лишь отметить, нулевой). Затем что если в остаточной сети этого потока находит какой-нибудь путь из источника к стоку и увеличивает поток на пропускную способность этого старом графе пути. Так он повторяет до тех порвершинно пересекаются, пока находится хоть какой-то путь в остаточной сетиновом графе пути необходимо реберно пересекаются и наоборот. То что получится будет максимальным потоком. В случае целочисленной сети достаточно :Кроме того, предложение "удалить в качестве начального приближения взять нулевой поток, и исходном графе любые <tex>L</tex> вершин" можно заменять на каждой итерации "в новом графе можно удалить любые <tex>L</tex> ребер" (в том числе достаточно выбирать вершины на концах этих ребер). Можно заменять и последней) этот поток будет оставаться целочисленнымобратно, если учесть, что и докажет требуемоеможно удалять ребра между парой вершин, которые раньше были одним целым.

<includeonly>Теоремы для неориентированного графа формулируются идентично, а их доказательства сводятся к своим ориентированным двойникам путем замены каждого ребра на две дуги: [[Файл: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)