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

2014-01-13T05:13:45Z

93.92.200.160: Исправление опечаток, пунктуации, улучшение читаемости

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

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

Кроме того, потребуется лемма о целочисленности потока, которую сейчас и докажем:
{{Лемма
|about=о целочисленности потока
|statement=      Если пропускные способности всех ребер целочисленные (сеть целочислена), то существует максимальный поток, целочисленный на каждом ребре.
|proof=
:Для доказательства достаточно рассмотреть [[Алгоритм Форда-Фалкерсона, реализация с помощью поиска в глубину|алгоритм Форда-Фалкерсона]] для поиска максимального потока. Алгоритм делает примерно следующее (подробней - читай в соответствующей статье):

:''1.'' В начале берем какой-нибудь поток за начальный (например, нулевой).

:''2.'' В остаточной сети этого потока находим какой-нибудь путь из источника к стоку и увеличиваем поток на пропускную способность этого пути.

:''3.'' Повторяем пункт ''2'' до тех пор, пока находится хоть какой-то путь в остаточной сети.

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

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

:Итак, найдем какой-нибудь маршрут из <tex>u</tex> в <tex>v</tex> лежащий только на ребрах где поток равен 1. Удалив все ребра находящиеся в этом маршруте и оставив все остальное неизменным, придем к целочисленному потоку величиной <tex>L-1</tex>. Ясно, что можно повторить тоже самое еще <tex>L-1</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=
:<tex>\Leftarrow</tex>

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

:<tex>\Rightarrow</tex>
:<tex>\exists L</tex> реберно непересекающихся путей, а значит, удалив любые <tex>L-1</tex> ребер хотя бы один путь останется не тронутым (принцип Дирихле). Это и означает, что существует путь из <tex>u</tex> в <tex>v</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>

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

[[Категория:Алгоритмы и структуры данных]]
[[Категория:Связность в графах]]

Викиконспекты - Вклад участника [ru]

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