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

 

ОПИСАНИЕ

ИЗОБРЕТЕНИЯ

К АВтоИСК0МЬ СВИДИтЕЛЬСтВЬ

375655

Союз Советскит

Социалистическиз

Республик

Зависимое от авт. свидетельства №

Заявлено 3 .111.1971 (№ 164077i6/18-24) с присоединением заявки № 1640814/18-24

Приоритет

Опубликовано 23.1I I.1973. Бюллетень № 16

Дата опубликования описания 5Х1.1973

М. Кл. G 06g 7/48

Комитет по делам изобретений и открытий при Совете Министров

СССР

УДК 6813 3 3:16(088.8) Авторы изобретения

В. В. Васильев, А. Г. Додонов и В. В. Федотов

Заявитель

Киевский ордена Трудового Красного Знамени институт инженеров гражданской авиации

УСТРОЙСТВО ДЛЯ МОДЕЛИРОВАНИЯ ЗАДАЧИ

МАКСИМАЛЬНОГО ПОТОКА СЕТИ

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

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

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

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

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

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

Устройство работает следующим образом.

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

15 кратчайший путь от начала сети до конца выбранной модели ветви и кратчайший путь от конца этой модели ветви до конца сети.

На подмножестве моделей ветвей с резервом времени )0 модель 8 определяет макси20 мальный поток, величина которого из блока

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

5, устройство вновь определяет подмножест25 во моделей ветвей в модели задачи о кратчайшем пути с резервом времени )0, а на нем — величину макоимального потока, которая запоминается в блоке определения динамического потока и т. д. Решение останав30 ливается, когда величина кратчайшего пути

375655

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

Составитель Г. Сорокин

Техред Т. Курилко

Редактор И. Грузова

Корректор Е. Михеева

Заказ 1622/17 Изд. № 1371 Тираж 647 Подписное

ЦНИИПИ Комитета по делам изобретений и открытий при Совете Министров СССР

Москва, Ж-35, Раушская наб., д. 4/5

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

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

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

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