223
правки
Изменения
м
Нет описания правки
|statement=Если в сети, где все пропускные способности ребер равны 1, существует целочисленный поток величиной <tex>L</tex> то существует и <tex>L</tex> реберно непересекающихся путей.
|proof=
: Считаем, что <tex>u</tex> - источник, <tex>v</tex> - сток.:В начале поймем, что если поток не нулевой, то существует маршрут из <tex>u</tex> в <tex>v</tex> лежащий только на ребрах с потоком равным 1. В самом деле, если бы такого маршрута не существовало, то можно было бы выделить множество вершин до которых такие маршруты из вершины <tex>u</tex> существуют, не включающее <tex>v</tex>, и по нему построить разрез. Поток через такой разрез, очевидно равен нулю, видим противоречие (т.к. <tex>f(U,V)=|f|</tex>, смотри [[Разрез, лемма о потоке через разрез|первую лемму]]).
:Итак, найдем какой-нибудь маршрут из <tex>u</tex> в <tex>v</tex> лежащий только на ребрах где поток равен 1. Удалив все ребра находящиеся в этом маршруте и оставив все остальное неизменным, придем к целочисленному потоку величиной <tex>L-1</tex>. Ясно, что можно повторить тоже самое еще <tex>L-1</tex> раз, и, таким образом мы выделим <tex>L</tex> реберно непересекающихся маршрутов.
:<tex>\Leftarrow</tex>
:Как и прежде, пусть <tex>u</tex> - источник, а <tex>v</tex> - сток.
:Назначим каждому ребру пропускную способность 1. Тогда существует максимальный поток, целочисленный на каждом ребре (по лемме).
:По теореме Форда-Фалкерсона для такого потока существует разрез с пропускной способностью равной потоку. Удалим в этом разрезе <tex>L-1</tex> ребер, и тогда раз <tex>u</tex> и <tex>v</tex> находятся в разных частях разреза, и <tex>\exists</tex> путь из <tex>u</tex> в <tex>v</tex>, то в разрезе останется хотя бы еще одно ребро. Значит пропускная способность разреза и вместе с ним величина потока <tex>\geqslant L</tex>. А так как поток целочисленный, то это и означает, что <tex>\exists L</tex> реберно непересекающихся путей.
