Глава 22, Потоки в сетях. 22.5.Разработайте класс EDGE,представляющий пропускные способности и потоки в виде вещественных чисел в промежутке от 0 до 1

22.5. Разработайте класс EDGE, представляющий пропускные способности и потоки в виде вещественных чисел в промежутке от 0 до 1, выраженных d цифрами после де­сятичной точки, где d есть фиксированная константа.

> 22.6. Напишите программу, которая строит транспортную сеть путем считывания из
стандартного ввода ребер (пар целых чисел в интервале от 0 до V— 1) с целочислен­
ными значениями пропускных способностей. При этом предполагается, что верхняя
граница пропускной способности М не превосходит значения 2²⁰.

22.7. Распространите полученное вами решение упражнения 22.6 на использование символических имен вместо чисел при обращении к вершинам (см. программу 17.10).

> 22.8. Отыщите пример крупной транспортной сети, которую можно было бы исполь­
зовать как среду для тестирования алгоритмов обработки потоков на реалистичных
данных. Возможны варианты транспортных сетей (автомобильные перевозки, желез­
нодорожный транспорт, авиация), сетей связи (телефонные и компьютерные сети пе­
редачи данных) или распределительных сетей. Если неизвестны пропускные способ­
ности, придумайте подходящую модель, назначающую пропускные способности
каналов. Напишите программу, использующую интерфейс программы 22.2 для реали­
зации транспортных сетей с вашими данными, возможно, с применением решения
упражнения 22.7. При необходимости, разработайте дополнительные приватные фун­
кции для удаления данных, в соответствии с описанием упражнений 17.33-17.35.

22.9. Напишите программу генератора случайных сетей для разреженных сетей с про­
пускными способностями, принимающими значение в диапазоне от 0 до 2²⁰, на осно­
вании программы 17.7. Воспользуйтесь специальными классами для пропускных спо­
собностей и разработайте две реализации, одна из которых генерирует равномерно
распределенные пропускные способности, а другая генерирует пропускные способ­
ности в соответствии с распределением Гаусса. Разработайте клиентские программы,
которые генерируют случайные сети для обоих типов распределений весов с тщатель­
но подобранным заданными значениями У и ребер Е, чтобы можно было использовать
их для прогона эмпирических тестов на графах, полученных на основе различных рас­
пределений весов ребер.

22.10. Напишите программу генератора случайных сетей для насыщенных сетей с про­
пускными способностями ребер в диапазоне от 0 до 2²⁰ на базе программы 17.8 и ге­
нераторов пропускных способностей ребер, описанных в упражнении 22.9. Напиши­
те клиентские программы генерации случайных сетей для обоих распределения весов
с тщательно подобранными заданными значениями V и ребер Е, чтобы можно было
использовать их для прогона эмпирических тестов на графах, построенных на базе этих
моделей.

• 22.11. Напишите программу, которая генерирует на плоскости V случайных точек, за­тем постройте транспортную сеть с ребрами (в обоих направлениях), соединяющими все пары точек, расположенных на расстоянии, не превышающем d одна от другой (см. программу 3.20), устанавливая пропускную способность каждого ребра с помо­щью одной из случайных моделей, описанных в упражнении 22.9. Определите, как выбрать d таким, чтобы ожидаемое число ребер было равным Е.

> 22.12. Внесите изменения в программу 22.1, которые позволили бы ей для каждого
ребра выполнять проверку, что величина потока меньше его пропускной способнос­
ти.

Часть 5. Алгоритмы на графах

> 22.13. Найти все максимальные потоки в сети, показанной на рис. 22.11. Дайте представление каждого из них в виде цикла.

22.14. Разработайте функцию, которая считыва­
ет величины потоков и циклы (по одному в стро­
ке, в формате, изображенном на рис. 22.8) и
строит сеть, имеющую соответствующий поток.

22.15. Разработайте клиентскую функцию, кото­
рая находит представление потока сети в виде
циклов, используя метод, описанный в доказа­
тельстве свойства 22.2, и распечатывает величины
потоков и циклы (по одному в строке, в форма­
те, представленном на рис. 22.8).

о 22.16. Разработайте функцию, которая удаляет циклы из st-потока сети.

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

РИСУНОК 22.11. ТРАНСПОРТНАЯ СЕТЬ С ЦИКЛАМИ

Представленная на этом рисунке транспортная сеть подобна сети, изображенной на рис. 22.10, за исключением того, что направление двух ребер заменены на обратные, вследствие чего появляются два цикла. Эта транспортная сеть также является предметом исследований в нескольких упраж­нениях в данной главе.

о 22.18. Предположим, что поток представляет собой товары, которые перевозят на гру­зовых машинах между городами, при этом под потоком в ребре u-v понимается ко­личество товара, которое надлежит доставить из города и в город v в течение дня. На­пишите клиентскую функцию, которая распечатывает распорядок дня для водителей грузовиков, уведомляя их о том, где что взять, в каком количестве и в каком месте разгрузиться. Предполагается, что не существует предельных значений загрузки гру­зовиков, и ни одно транспортное средство не покинет заданный распределительный пункт, пока на него не поступит весь товар.