Изменения
Нет описания правки
Из закона слабой двойственности следует, что <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 точка пересечения.
Очевидно, что эта точка определяет максимальный поток среди всех потоков и минимальный разрез среди всех разрезов сети <tex>G</tex>. }} [[Файл:разрезы.png|мини|слева|600x300px| Среди всех разрезов сети разрез с минимальной пропускной способностью определяет максимальный поток в сети. ]][[Файл {| class="wikitable" style="text-align:таблица.pngcenter" width="75%"|мини|слева|500x200px+ style="caption-side:bottom; "|''Минимальны разрез — 1 с пропускной способностью 60.]]''| Разрез|"Разрезанные" ребра | Пропускная способность|-| style="text-align:left;" | 1| style="text-align:right;" | (1,2),(1,3),(1,4)| style="text-align:right;" | 10+30+20=60|-| style="text-align:left;" | 2| style="text-align:right;" | (1,3),(1,4),(2,3),(2,5)| style="text-align:right;" | 30+10+40+30=110|-| style="text-align:left;" | 3| style="text-align:right;" | (2,5),(3,5),(4,5)| style="text-align:right;" | 30+20+20=70} |}
== Источники информации ==
