Теорема Менгера
Версия от 11:42, 19 октября 2011; Dmitriy D. (обсуждение | вклад)
Эта статья находится в разработке!
// Здесь пока наброски. Не ищите структуры.
Теорема (Менгера о реберной двойственности): |
Между вершинами и реберно непересекающихся путей после удаления ребер путь из в . |
Доказательство: |
Для доказательства мы воспользуемся теорией потоков. Нам потребуются понятия остаточной сети (иначе - дополнительной сети), а также теорема Форда-Фалкерсона. Кроме того потребуется лемма о целочисленности потока, которую сейчас и докажем: |
Лемма (о целочисленности потока): |
Если пропускные способности всех ребер целочисленные (сеть целочислена), то существует максимальный поток, целочисленный на каждом ребре. |
Доказательство: |
Для доказательства достаточно рассмотреть алгоритм Форда-Фалкерсона. Алгоритм делает примерно следующее (подробней - читай в соответствующей статье): в начале берет какой-нибудь поток за начальный (например, нулевой). Затем в остаточной сети этого потока находит какой-нибудь путь из источника к стоку и увеличивает поток на пропускную способность этого пути. Так он повторяет до тех пор, пока находится хоть какой-то путь в остаточной сети. То что получится будет максимальным потоком. В случае целочисленной сети достаточно в качестве начального приближения взять нулевой поток, и на каждой итерации (в том числе и последней) этот поток будет оставаться целочисленным, что и докажет требуемое. |
Литература
- Ловас Л., Пламмер М. Прикладные задачи теории графов. Теория паросочетаний в математике, физике, химии 1998. 656 с. ISBN 5-03-002517-0 (глава 2.4 стр. 117)