![]() Главная страница Случайная страница КАТЕГОРИИ: АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Глава 22, Потоки в сетях. 22.5.Разработайте класс EDGE,представляющий пропускные способности и потоки в виде вещественных чисел в промежутке от 0 до 1
> 22.6. Напишите программу, которая строит транспортную сеть путем считывания из 22.7. Распространите полученное вами решение упражнения 22.6 на использование символических имен вместо чисел при обращении к вершинам (см. программу 17.10). > 22.8. Отыщите пример крупной транспортной сети, которую можно было бы исполь 22.9. Напишите программу генератора случайных сетей для разреженных сетей с про 22.10. Напишите программу генератора случайных сетей для насыщенных сетей с про • 22.11. Напишите программу, которая генерирует на плоскости V случайных точек, затем постройте транспортную сеть с ребрами (в обоих направлениях), соединяющими все пары точек, расположенных на расстоянии, не превышающем d одна от другой (см. программу 3.20), устанавливая пропускную способность каждого ребра с помощью одной из случайных моделей, описанных в упражнении 22.9. Определите, как выбрать d таким, чтобы ожидаемое число ребер было равным Е. > 22.12. Внесите изменения в программу 22.1, которые позволили бы ей для каждого Часть 5. Алгоритмы на графах
> 22.13. Найти все максимальные потоки в сети, показанной на рис. 22.11. Дайте представление каждого из них в виде цикла. 22.14. Разработайте функцию, которая считыва 22.15. Разработайте клиентскую функцию, кото о 22.16. Разработайте функцию, которая удаляет циклы из st-потока сети. о 22.17. Напишите программу, которая назначает целочисленные потоки каждому ребру в любом заданном орграфе, который не содержит ни истоков, ни стоков, так, что этот орграф является транспортной сетью, представляющей собой циркуляцию. РИСУНОК 22.11. ТРАНСПОРТНАЯ СЕТЬ С ЦИКЛАМИ Представленная на этом рисунке транспортная сеть подобна сети, изображенной на рис. 22.10, за исключением того, что направление двух ребер заменены на обратные, вследствие чего появляются два цикла. Эта транспортная сеть также является предметом исследований в нескольких упражнениях в данной главе. о 22.18. Предположим, что поток представляет собой товары, которые перевозят на грузовых машинах между городами, при этом под потоком в ребре u-v понимается количество товара, которое надлежит доставить из города и в город v в течение дня. Напишите клиентскую функцию, которая распечатывает распорядок дня для водителей грузовиков, уведомляя их о том, где что взять, в каком количестве и в каком месте разгрузиться. Предполагается, что не существует предельных значений загрузки грузовиков, и ни одно транспортное средство не покинет заданный распределительный пункт, пока на него не поступит весь товар.
|