272
правки
Изменения
→Алгоритм
== Алгоритм ==
Алгоритм масштабирования [[Определение_сети,_потока#.D0.9E.D0.BF.D1.80.D0.B5.D0.B4.D0.B5.D0.BB.D0.B5.D0.BD.D0.B8.D0.B5_.D0.BF.D0.BE.D1.82.D0.BE.D0.BA.D0.B0|потока]] {{---}} алгоритм поиска максимального потока, основывающийся на предположении, что [[Определение_сети,_потока#.D0.9E.D0.BF.D1.80.D0.B5.D0.B4.D0.B5.D0.BB.D0.B5.D0.BD.D0.B8.D0.B5_.D1.81.D0.B5.D1.82.D0.B8|пропускные способности]] всех ребер выражаются целыми числами. Время работы алгоритма составляет <tex> O(E^2 \log U) </tex>, что может быть много меньше времени работы [[Дискретная_математика,_алгоритмы_и_структуры_данных#.D0.97.D0.B0.D0.B4.D0.B0.D1.87.D0.B0_.D0.BE_.D0.BC.D0.B0.D0.BA.D1.81.D0.B8.D0.BC.D0.B0.D0.BB.D1.8C.D0.BD.D0.BE.D0.BC_.D0.BF.D0.BE.D1.82.D0.BE.D0.BA.D0.B5|аналогичных алгоритмов]] поиска максимального потока.
Пусть дана [[Определение_сети,_потока#.D0.9E.D0.BF.D1.80.D0.B5.D0.B4.D0.B5.D0.BB.D0.B5.D0.BD.D0.B8.D0.B5_.D1.81.D0.B5.D1.82.D0.B8|сеть]] <tex> G </tex>, все ребра которой имеют целочисленную пропускную способность. Обозначим за <tex> U </tex> максимальную пропускную способность: <tex> U = \max\limits_{(u, v) \in E} c(u, v) </tex>.
