Изменения

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

Алгоритм масштабирования потока

270 байт добавлено, 11:00, 6 марта 2012
Оценка времени работы
Количество дополняющих путей с масштабом <tex> 2^k </tex> не превосходит <tex> 2E </tex>.
|proof=
Каждый дополняющий путь имеет пропускную способность не меньше <tex> 2^k </tex>.На предыдущей итерации дополняющий поток ограничен значением <tex> 2^{k + 1} E </tex> по предыдущей лемме. Следовательно, количество дополняющих путей не превосходит <tex> 2E </tex>.
}}
{{Лемма
|about=
32
|statement=
Общее количество увеличивающих путей не превышает <tex> O(E \log U) </tex>.
|proof=
На некоторой итерации алгоритма каждый дополняющий путь имеет пропускную способность не меньше <tex> 2^k </tex>.
Дополняющий поток на предыдущей итерации ограничен значением <tex> 2^{k + 1} E </tex>. Следовательно, на каждой итерации количество дополняющих путей не превосходит <tex> 2E </tex>.
 
Следует из предыдущей леммы и факта, что количество итераций {{---}} <tex> O(\log U) </tex>.
}}
272
правки

Навигация