223
правки
Изменения
м
Нет описания правки
{{В разработке}}
// Здесь пока наброски. Не ищите структуры.
{{Теорема
|about=Менгера о реберной двойственности
|statement=Между вершинами <tex>u</tex> и <tex>v\; \exists L</tex> реберно непересекающихся путей <tex>\Leftrightarrow</tex> после удаления <tex>\forall L-1</tex> ребер <tex>\exists</tex> путь из <tex>u</tex> в <tex>v</tex>.
|proof=
Для доказательства мы воспользуемся [[Определение сети, потока|теорией потоков]]. Нам потребуются понятия [[Дополняющая сеть, дополняющий путь| остаточной сети]] (иначе - дополнительной сети), а также [[Теорема_Форда-Фалкерсона|теорема Форда-Фалкерсона]]. Кроме того потребуется лемма о целочисленности потока, которую сейчас и докажем:
}}
{{Лемма
|about=о целочисленности потока
|statement=Если пропускные способности всех ребер целочисленные (сеть целочислена), то существует максимальный поток, целочисленный на каждом ребре.
|proof=Для доказательства достаточно рассмотреть [[Алгоритм Форда-Фалкерсона, реализация с помощью поиска в глубину|алгоритм Форда-Фалкерсона]]. Алгоритм делает примерно следующее (подробней - читай в соответствующей статье): в начале берет какой-нибудь поток за начальный (например, нулевой). Затем в остаточной сети этого потока находит какой-нибудь путь из источника к стоку и увеличивает поток на пропускную способность этого пути. Так он повторяет до тех пор, пока находится хоть какой-то путь в остаточной сети. То что получится будет максимальным потоком. В случае целочисленной сети достаточно в качестве начального приближения взять нулевой поток, и на каждой итерации (в том числе и последней) этот поток будет оставаться целочисленным, что и докажет требуемое.
}}
==Литература==
* Ловас Л., Пламмер М. '''Прикладные задачи теории графов. Теория паросочетаний в математике, физике, химии''' 1998. 656 с. ISBN 5-03-002517-0 (глава 2.4 стр. 117)
[[Категория:Связность в графах]]
