Изменения

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

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

11 байт добавлено, 18:14, 21 декабря 2010
м
Поток через разрез
Если <tex>f(S,T)=c(S,T)</tex>, то поток <tex>f</tex> - максимален, а разрез <tex><S,T></tex> - минимален.
|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 точка пересечения. Очевидно, что точка определяет максимальный поток среди всех потоков и минимальный разрез среди всех разрезов сети <tex>G</tex>.
}}
141
правка

Навигация