272
правки
Изменения
Нет описания правки
{{Определение
|definition=
'''Алгоритм масштабирования потока ''' — алгоритм поиска максимального потока путём регулирования пропускной способности рёбер.Этот алгоритм работает , работающий в предположении, что все пропускные способности рёбер целые, так как они легко представимы в двоичном виде.
}}
|statement=
Сложность второй итерации алгоритма — <tex> O(E^2) </tex>.
|proof='''Полужирное начертание'''
[[Файл:Scaling.jpg|250px|thumb|right|Разрез <tex> \langle A, \overline{A} \rangle </tex>.]]
Докажем оценку для второго шага (для остальных доказательство аналогично).
