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