Изменения

Перейти к: навигация, поиск

Разрез, лемма о потоке через разрез

75 байт добавлено, 18:17, 21 декабря 2010
Поток через разрез
|proof =
Из закона слабой двойственности следует, что <tex>f(S_1,T_1)\le c(S_2,T_2)</tex> для любых двух разрезов <tex><S_1,T_1></tex> и <tex><S_2,T_2></tex> в сети <tex>G</tex> (так как <tex>f(S_1,T_1)=|f|=f(S_2,T_2)\le c(S_2,T_2)</tex>).
Значит, если расположить все величины потоков и разрезов на оси OX, то у потоков с разрезами может быть максимум 1 точка пересечения. [[Файл:flows_and_cuts.png|thumb|right|Потоки и разрезы]] Очевидно, что точка определяет максимальный поток среди всех потоков и минимальный разрез среди всех разрезов сети <tex>G</tex>.
}}
141
правка

Навигация