![]() Главная страница Случайная страница КАТЕГОРИИ: АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Упражнения. 22.105.Расширьте класс допустимых потоков из упражнения 22.44, обеспечив манипулирование стоимостями
22.105. Расширьте класс допустимых потоков из упражнения 22.44, обеспечив манипулирование стоимостями. Воспользуйтесь классом MINCOST для решения задачи о допустимых потоках минимальной стоимости. > 22.106. Пусть дана некоторая транспортная сеть, рёбра которой не обладают макси 22.107. Докажите, что если все пропускные способности и стоимости суть целые чис 22.108. Реализуйте функцию negcyc() для программы 22.9, воспользовавшись для этой > 22.109. Внесите изменения в программу 22.9, допускающие инициализацию потоком o22.H0. Дайте все возможные последовательности аугментальных циклов, которые могли бы быть показаны на рис. 22.41. Часть 5. Алгоритмы на графах
о 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.114. Дополните полученные вами решения упражнений 22.6 и 22.7 вычислениями 22.115. Дополните полученные вами решения упражнений 22.9-22.11 вычислениями
|