УСТРОЙСТВО для МОДЕЛИРОВАНИЯ ЗАДАЧИ О МАКСИМАЛЬНОМ ДИНАМИЧЕСКОМ ПОТОКЕ Советский патент 1973 года по МПК G06F15/173 

1

Изобретение относится к области вычислительной техники.

Известны устройства для моделирования задачи о максимальном динамическом потоке, содерл аш,ие генератор импульсов, выход которого соединен со входами модели задачи кратчайшего нути, блока онределения динамического потока и блока определения ветвей, соединенного двусторонними связями с моделью задачи кратчайшего пути и блоком определения динамического нотока. Все эти устройства требуют применения модели о максимальном потоке.

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

Па чертеже нрнведена блок-схема устройства.

Устройство содержит генератор нмнульсов /, модели задач кратчайшего нути 2 и 3, блок определення динамического потока 4 и блок онределепия ветвей 5.

Устройство для моделирования задачи о максимальном дннамическом потоке работает следующим образом. Устройство представляет связанные между собой две сети - «сеть времени и «транснортную сеть. Па «сети

времени, начиная с времени ее кратчайшего пути, определяются последовательно на каждый следуюн;ий момент времени пути задайной продолжительности. Соответственно для каждого момента времени на нодмножестве ветвей сети, попавших в путь заданной продолжительности, на «транспортной сети определяется станионарный ноток. Если на какойлибо момент времени нового нути не образуется, на «транспортной сети повторяется предыдугний стационарный поток. Сумма всех стационарных потоков за время, в течение которого определяется динамический ноток, и онределит его.

Л одель задачи кратчайшего путн 2, предназначенная для моделирования «сети времени, содержит соединенные менсду собой согласно топологии исследуемой сети модели

ветвей (на чертеже не показаны), в которые записывается информация, соответствующая длинам ветвей. Модель задачи кратчайшего пути 3, нредназначенная для моделирования «транспортной сети, содержит соединенные

между собой согласно топологии двойствеиной сети модели ветвей (на чертеже не показаны), в которые записывается информация, соответствующая пропускным снособностям ветвей. В блоке определения ветвей 5 занисывается время, за которое определяется поток. 3 Предмет изобретения Устройство для моделирования задачи о максимальном динамическом потоке, содержащее генератор импульсов, выход которого соединен со входами модели задачи кратчайшего пути, блока определения динамического потока и блока определения ветвей, соединенного двусторонними связями с моделью задачи кратчайшего пути и блоком определения динамического потока, отличающееся тем, что, с целью упрощения устройства, оно содержит вторую модель задачи кратчайшего пути, соединенную с блоком определения ветвей и блоком онределения динамического потока и подключенную к генератору импульсов.