Глава 22, Потоки в сетях. Возможно, наиболее простой структурой данных для хранения активных вершин яв­ляется очередь FIFO

Возможно, наиболее простой структурой данных для хранения активных вершин яв­ляется очередь FIFO. На рис. 22.28 показано, как работает этот алгоритм на демонстра­ционном примере сети. Из рисунка видно, что последовательность активных вершин удоб­но разбить на последовательность этапов, при этом этап составляют все вершины, которые находились в очереди после того, как все вершины, входившие в состав предыдущего этапа, были обработаны. Такого рода разбиение помогает нам ограничить общее время выполнения алгоритма.

Свойство 22.13. Время выполнения реализации алгоритма выталкивания превосходя­щего потока на базе очереди FIFO пропорционально V²E.

Доказательство: Мы ограничим число этапов, воспользовавшись для этой цели потен­циальной функцией. Рассуждения, используемые для доказательства, представляют со­бой простой пример применения мощных средств анализа алгоритмов, а используе­мые структуры данных будут более подробно изучаться в части 8.

Определим числовое значение величины ф равным 0, если в сети нет активных вер­шин, и равным максимальной высоте активных вершин в противном случае, затем рассмотрим, как отражается выполнение каждого этапа на величине ф. Пусть h_o(s) есть начальная высота истока. Вначале ф = h_o(s); по завершении ф = 0.

Прежде всего, отметим, что число этапов, на которых высота некоторых вершин воз­растает, не превосходит значения 2V² — h_o(s), поскольку высота каждой из V вершин, согласно свойству 22.11, может быть увеличена максимум до значения 2V. Поскольку ф может возрастать только тогда, когда увеличивается высота некоторых вершин, чис­ло этапов, когда ф возрастает, не может быть больше, чем 2V² - h_o(s).

Если, однако, на каком-либо этапе высота ни одной из вершин не будет увеличена, то значение ф должно быть уменьшено, по меньшей мере, на 1, поскольку результат этапа заключается в том, чтобы протолкнуть весь избыточный поток из каждой актив­ной вершины в вершины с меньшей высотой.

Принимая во внимание все эти факты, приходим к заключению, что число этапов не должно быть больше 4V²: значение ф в начале есть h_o(s) и может быть увеличено мак­симум 2 V² - h_o(s) раз, т.е., оно может быть уменьшено максимум 2V² раз. Худший слу­чай каждого этапа возникает тогда, когда все вершины находятся в очереди и все их ребра подвергаются проверке, что соответствует граничному значению, установленно­му для общего времени выполнения.

Эта граница плотная. На рис. 22.29 изображено семейство транспортных сетей, для которых число этапов, использованных алгоритмом выталкивания избыточного потока пропорционально V². ■

Поскольку предлагаемые нами реализации поддерживают неявное представление ос­таточной сети, они проверяют ребра, исходящие из вершины, даже если эти ребра не со­держатся в остаточной сети (чтобы проверить, находятся они там или нет). Можно по­казать, что границу V²E, устанавливаемую свойством 22.13, можно уменьшить до V³ для реализаций за счет поддержки явного представления остаточной сети. Несмотря на то что эта теоретическая граница есть наименьшая из тех, с которыми нам приходилось стал­киваться при решении задачи вычисления максимального потока, это достижение, по-видимому, не заслуживает нашего внимания, особенно в случае разреженных графов, с которыми мы часто имеем дело на практике (см. 22.63-22.65).