Главная страница Случайная страница
КАТЕГОРИИ:
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника
Упражнения. 22.105.Расширьте класс допустимых потоков из упражнения 22.44, обеспечив манипулирование стоимостями
|
|
22.105. Расширьте класс допустимых потоков из упражнения 22.44, обеспечив манипулирование стоимостями. Воспользуйтесь классом MINCOST для решения задачи о допустимых потоках минимальной стоимости.
> 22.106. Пусть дана некоторая транспортная сеть, рёбра которой не обладают макси
мальной пропускной способностью и максимальной стоимостью. Дайте более точную
верхнюю границу, чем ЕСМ, для стоимости максимального потока.
22.107. Докажите, что если все пропускные способности и стоимости суть целые чис
ла, то задача о минимальной стоимости имеет решение, в рамках которого все пото
ки имеют целочисленные значения.
22.108. Реализуйте функцию negcyc() для программы 22.9, воспользовавшись для этой
цели алгоритмом Беллмана-Форда (см. упражнение 21.134).
> 22.109. Внесите изменения в программу 22.9, допускающие инициализацию потоком
в фиктивном ребре вместо вычисления потока.
o22.H0. Дайте все возможные последовательности аугментальных циклов, которые могли бы быть показаны на рис. 22.41.
Часть 5. Алгоритмы на графах
о 22.111. Дайте все возможные последовательности аугментальных циклов, которые могли бы быть показаны на рис. 22.42.
о 22.112. Покажите в стиле рис. 22.41 поток и остаточные сети после каждого наращивания в случае использования реализации программы 22.9 с алгоритмом вычеркивания циклов для отыскания потока минимальной стоимости в транспортной сети, изображенной на рис. 22.10, в которой ребрам 0-2 и 0-3 назначена стоимость 2, ребрам 2-5 и 3-5 - стоимость 3, ребру 1-4 - стоимость 4, а всем остальным ребрам - стоимость 1. Предполагается, что максимальный поток вычисляется с помощью алгоритма построения кратчайшего аугментального пути.
22.113. Выполните упражнение 22.112 в предположении, что в программу внесены из
менения, позволяющие начинать вычисления в ситуации, когда максимальный поток
протекает в фиктивном ребре из истока в сток, как показано на рис. 22.42.
22.114. Дополните полученные вами решения упражнений 22.6 и 22.7 вычислениями
стоимостей в транспортных сетях.
22.115. Дополните полученные вами решения упражнений 22.9-22.11 вычислениями
стоимостей в сетях. Назначьте каждому ребру стоимость, приблизительно пропорци
ональную эвклидовому расстоянию между вершинами, которые это ребро соединяет.