Устройство для моделирования задачи максимального потока сети
ОПИСАНИЕ
ИЗОБРЕТЕНИЯ
К АВтоИСК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 определения потока, блока определения ветвей и генератора импульсов.