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

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

// Здесь пока наброски. Не ищите структуры.

Теорема (Менгера о реберной двойственности):

Между вершинами [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]

Для доказательства мы воспользуемся теорией потоков. Нам потребуются понятия остаточной сети (иначе - дополнительной сети), а также теорема Форда-Фалкерсона. Кроме того потребуется лемма о целочисленности потока, которую сейчас и докажем:

[math]\triangleleft[/math]

Лемма (о целочисленности потока):

Если пропускные способности всех ребер целочисленные (сеть целочислена), то существует максимальный поток, целочисленный на каждом ребре.

Доказательство:

[math]\triangleright[/math]

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

[math]\triangleleft[/math]

Литература

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