Изменения

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

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

369 байт добавлено, 20:57, 5 декабря 2015
Поток через разрез
Если <tex>f(S,T)=c(S,T)</tex>, то поток <tex>f</tex> — максимален, а разрез <tex>\langle S,T\rangle</tex> — минимален.
|proof =
[[Файл:Минимальный_разрез.png|мини|справа|300x100px|Потоки и разрезы]]
Из закона слабой двойственности следует, что <tex>f(S_1,T_1)\leqslant c(S_2,T_2)</tex> для любых двух разрезов <tex>\langle S_1,T_1\rangle</tex> и <tex>\langle S_2,T_2\rangle</tex> в сети <tex>G</tex>, так как <tex>f(S_1,T_1)=|f|=f(S_2,T_2)\leqslant c(S_2,T_2)</tex>.
Значит, если расположить все величины потоков и разрезов на оси OX, то у потоков с разрезами может быть максимум 1 точка пересечения.
[[Файл:flows_and_cuts.png|thumb|right|Потоки и разрезы]] Очевидно, что эта точка определяет максимальный поток среди всех потоков и минимальный разрез среди всех разрезов сети <tex>G</tex>.[[Файл:разрезы.png|мини|слева|500x200px| Среди всех разрезов сети разрез с минимальной пропускной способностью определяет максимальный поток в сети. ]][[Файл:таблица.png|мини|слева|500x200px|]]
}}
Анонимный участник

Навигация