Решение задач, связанных с потоками в сетях довольно часто встречается в исследованиях операций, computer science и инженерном деле. Теорию потоков рассматривают в различных приложениях, которые возникают в реальных задачах.
К указанному классу задач, например, относятся следующие. В задачах транспортного типа осуществляется поиск пути, имеющего минимальную длину, проводится поиск циклов, имеющих отрицательный вес (неоптимальные перевозки) и др. Существуют задачи, связанные с определением существования потока – это задачи о максимальном потоке а также задачи поиска минимального разреза.
В данной работе для сети, которая задана матрицей пропускных способностей дуг, требуется определить максимально возможное количество информации, которая передается между источником и приемником.
Указанная задача относится к задаче о максимальном потоке и в ней необходимо найти такое множество потоков по дугам, чтобы величина потока в сети была максимальной при условии отсутствия превышения пропускных способностей дуг. При реализации алгоритма поиска максимального потока была разработана программа в среде Delphi. Работа программы проходит в режиме диалога с пользователем и используется модульный принцип. Область использования программы – любые задачи, которые связаны с определением потоков в сетях. В созданной для решения задачи программе определена константа nm = 35 – максимальное число вершин сети.
Для использования в процедурах определены следующие пользовательские типы: matrixnm – двумерный целочисленный массив размерности nm×nm; masnm – одномерный целочисленный массив размерности nm; gpointn – тип – запись: координаты узла сети с полями: x, y – абсцисса и ордината вершины, целочисленные значения; rebro – массив множеств номеров узлов, тип versh; versh – тип множество, включающее в себя элементы от 1 до 100.
Исходя из того, какие задачи, решаются разработчиками, и от использования ими методов проектирования модульная программа может иметь одну из следующих основных структур: монолитно–модульную. модульно–последовательную, модульно–иерархическую, модульно–хаотическую. Если используется монолитно–модульная структура, то она имеет в себе большой программный модуль, который реализует большую часть программных функций. Для такой части существует небольшое число обращений к другим программным модулям небольшого размера. Такая программа имеет определенные сложности понимания, проверки, сопровождения. В модульно–последовательную структуру включаются несколько программных модулей, которые последовательно передают друг другу управление. В этом случае структура проста и наглядна, но и задачи, которые решаются – довольно просты. В модульно–иерархическую структуру включаются программные модули, которые располагаются на нескольких уровнях иерархии. Модули верхних уровней проводят управление работой модулей нижних уровней. От вышестоящего модуля передается управление модулю более низкого уровня, а когда тот закончит работу, он возвращает управление вызвавшему его модулю. Подобная структура достаточно проста и позволяет решать очень сложные задачи. Программа построена по модульно–иерархической структуре. Связь модулей осуществляют через простой параметр – данные и через общий блок данных. Меню в программе имеет иерархическую структуру. Движение внутри уровней производится клавишами управления курсором ↑¯ или при помощи мыши. Выбор делают только нажатием клавиши Enter или щелчком мыши.