Студопедия

Главная страница Случайная страница

КАТЕГОРИИ:

АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника






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






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

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

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

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

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

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

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

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

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






mylektsii.ru - Мои Лекции - 2015-2018 год. (0.006 сек.)Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав Пожаловаться на материал