Расширения: улучшенная версия алгоритма

(7.30) Если на каждом шаге выбирается узел с избыточным потоком на макси- мальной высоте, количество ненасыщающих операций проталкивания в процессе выполнения алгоритма не превышает 4n³.

Доказательство. Рассмотрим максимальную высоту // = ⅛^г) любо-

го узла с избыточным потоком во время выполнения алгоритма. В анализе будет использоваться максимальная высота Н вместо потенциальной функции ‘1’ из предыдущей границы O(n²m).

Максимальная высота H может увеличиться только из-за изменения меток (так как поток всегда проталкивается к узлам с меньшей высотой), поэтому общее возрастание H в алгоритме не может превышать 2n² согласно (7.26). Значение H начинается с 0 и остается неотрицательным, поэтому количество изменений H не превышает 4n².

Теперь рассмотрим поведение алгоритма в фазе времени, в которой H остается постоянной величиной. Утверждается, что каждый узел может иметь максимум одну ненасыщающую операцию push в этой фазе. Действительно, в этой фазе поток проталкивается от узлов на высоте H к узлам на высоте H - 1; и после ненасыщаю- щей операции push от v он должен получить поток от узла на высоте H + 1, прежде чем от него снова можно будет проталкивать поток.

Так как количество ненасыщающих операций push между изменениями H не превышает n, а H изменяется не более 4n² раз, общее количество ненасыщающих операций push не превышает 4n³. ■

В продолжение (7.30) интересно заметить, что по проведенным экспериментам вычислительным «узким местом» метода является количество операций relabel, и более эффективное время выполнения было получено для модификаций, ко- торые увеличивают метки быстрее, чем по единице. Это обстоятельство будет рассмотрено подробнее в упражнениях.