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

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

Теорема Менгера представляет собой группу теорем, связывающих такие понятия на графах как 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]

Назначим каждому ребру пропускную способность 1. Тогда существует максимальный поток целочисленный на каждом ребре(по лемме). Рассмотрим минимальный

[math]\triangleleft[/math]

Литература

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