Главная > Математика > Теория графов. Алгоритмический подход
<< Предыдущий параграф
Следующий параграф >>
<< Предыдущий параграф Следующий параграф >>
Макеты страниц

6.3. Алгоритм оптимального потока для графов с выигрышами

Из трех вышеприведенных теорем сразу же вытекает алгоритм оптимальности, описанный ниже.

Шаг 1. Начать с произвольного допустимого потока (допустим, например, нулевой по каждой дуге поток).

Шаг 2, Найти в активный цикл по отношению к

Шаг 3. Пусть такая вершина в что аугментальный маршрут начинается в и кончается в (Заметим, что может совпадать с Начиная с вершины устроить циркуляцию потока по активному циклу и передать избыток потока из по аугментальному маршруту. Выбрать так, чтобы (вместе с существующим потоком В) инкрементальная пропускная способность цикла или аугментального маршрута уменьшилась до нуля.

Шаг 4. Обновить поток и возвращаться к шагу 2 до тех пор, пока все активные циклы не будут дезактивированы и больше не будет существовать никаких активных циклов; после чего перейти к шагу 5. (На этом этапе поток будет оптимальным потоком

Шаг 5. Найти аугментальный маршрут от с наибольшим выигрышем. Посылать поток по этому маршруту до тех пор, пока инкрементальная пропускная способность не уменьшится до нуля.

Шаг 6. Обновить поток и повторять шаг 5 до тех пор, пока или чистый выходной поток не примет требуемое значение (оптимального потока), или больше не будет существовать никаких аугментальных маршрутов; тогда полученный поток будет оптимально-максимальным потоком

Шаги вышеприведенного алгоритма очень просты, а сам метод эффективен. Шаги 2 и 5 можно выполнять и с помощью алгцритма кратчайшей цепи. А именно определим инкрементальный граф соответствующий графу с множеством вершин и множеством дуг таким, что

причем инкрементальная «стоимость

и пропускная способность

и

инкрементальная «стоимость»

и пропускная способность

Цикл в графе имеющий выигрыш, больший чем единица, соответствует тогда циклу с отрицательной «стоимостью» в графе В этом можно убедиться, прологарифмировав обе части соотношения (11.15), в котором в качестве маршрута надо взять цикл Тогда получим

где как и прежде, — множества прямых и обратных дуг цикла

Если то откуда следует, что стоимость цикла в т. е. Должна быть отрицательной. Обратно, если то стоимость цикла неотрицательна.

Таким образом, активные циклы в на шаге 2 вышеописанного алгоритма — могут быть определены посредством нахождения всех кратчайших (наименьшей «стоимости») цепей, идущих из вершин графа к конечной вершине (для чего можно воспользоваться методом из разд. 2.2.1 гл. 8, как это было объяснено в разд. 4 настоящей главы), и проверки циклов на отрицательную стоимость. Если, однако, поток циркулирующий по активному циклу на шаге 3 и передаваемый по аугментальному маршруту к не уменьшает до нуля пропускную способность самого цикла а вместо этого уменьшает до нуля пропускную способность аугментального маршрута, то при следующем выполнении шага 2 нужно только найти другой аугментальный маршрут, ведущий из вершины цикла в вершину Такой маршрут снова сделает цикл активным и можно будет перейти к шагу 3 и т. д. вплоть до того момента, когда цикл дезактивируется. Тогда на шаге 2 ищется некоторый другой активный цикл.

Шаг 5 вышеописанного алгоритма также можно выполнить с помощью метода разд. 2.2.1 гл. 8, так как он состоит просто в вычислении кратчайшей цепи от в графе Этот граф «освобождается» от циклов отрицательной стоимости, как только выполнены четыре предыдущие шага алгоритма.

<< Предыдущий параграф Следующий параграф >>
Оглавление