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

1

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

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

Однако такие устройства не позволяют решать задачу о максимальном динамическом потоке в сети.

Цель изобретения - расширение круга решаемых задач.

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

Блок-схема устройства приведена на чертеже.

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

блоки определения потока 4, ветвей 5 и динамического потока 6.

Устройство работает следующим образом. Время, за которое определяется поток, записывается в блок 5, который осуш,ествляет запуск модели 2, определяюш;ей величину кратчайшего пути. Величина максимального динамического потока за время, меньшее кратчайшего пути, равна нулю. Модели ветвей.

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

кратчайший путь от начала сети до конца выбранной модели ветви и кратчайший путь от конца этой модели ветви до конца сети. На подмножестве моделей ветвей с резервом времени 0 модель 3 определяет максимальный поток, величина которого из блока 4 определения потока переписывается в блок 6 определения динамического потока. Далее, изменив величину кратчайшего пути в блоке 5, устройство вновь определяет подмножество моделей ветвей в модели задачи о кратчайшем пути с резервом времени 0, а на нем - величину максимального потока, которая запоминается в блоке определения динамического потока и т. д. Решение останавливается, когда величина кратчайшего пути

станет равной заданному времени определения максимального динамического потока.

Предмет изобретения

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

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

определения потока, блока определения ветвей и генератора импульсов.