Устройство для определения минимального пути в графе

 

Изобретение относится к вычислительной технике, может быть использовано для решения широкого круга экстремальных задач и позволяет определять минимальный путь в графе со взвешенными вершинами. В состав устройства входит источник 1 регули-- руемого напряжения, блок 2 индикации, модели 3 узлов, содержащие ключевые элементы, например газоразрядные лампы , количество которых равно весу узла, модели 5 ветвей, содержащие ключевые элементы 4, количество которьш равно весу ветви, и диоды 6, определяюш 1е направление ветви. При повышении напряжения источника от нуля до некоторой пороговой величины произойдет одновременное зажигание группы газоразрядных ламп, суммарное напряжение зажигания которых является , минимальным. При этом высветится путь, соответствующий минимальному, 1 ил. (Л 00 ю ел ел

СОЮЗ СОВЕТСНИХ

СОЦИАЛИСТИЧЕСКИХ

РЕСПУБЛИН (51)4 6 06 G 7/122

ГОСУДАРСТВЕННЫЙ НОМИТЕТ СССР

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ

Ь,> "..

ОПИСАНИЕ ИЗОБРЕТЕНИЯ -":

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (21) 3930221/24-24 (22) 17.06.85 (46) 23.07.87. Бюл. У 27 (71) Киевский автомобильно-дорожный институт им.60-летия Великой Октябрьской социалистической революции (72) Л.В.Федотов, В.И,Михайленко и С.В.Озирский (53) 681,333 (088.81 (56) Авторское свидетельство СССР

9 855672, кл. G 06 G 7/122, 1979.

Авторское свидетельство СССР

1Ф 1275480, 1985. (54) УСТРОЙСТВО ДЛЯ ОПРЕДЕЛЕНИЯ МИHHMAJIbH0I 0 ПУТИ В ГРАФЕ (57) Изобретение относится к вычислительной технике, может быть использовано для решения широкого круга экстремальных задач и позволяет

„„SU„„1325517 А1 определять минимальный путь в графе со взвешенными вершинами. В состав устройства входит источник 1 регули-. руемого напряжения, блок 2 индикации, модели 3 узлов, содержащие ключевые элементы, например газоразрядные лампы, количество которых равно весу узла, модели 5 ветвей, содержащие ключевые элементы 4, количество которых равно весу ветви, и диоды 6, определяющие направление ветви. При повышении напряжения источника от нуля до некоторой пороговой величины произойдет одновременное зажигание группы газоразрядных ламп, суммарное напряжение зажигания которых являет- а е ся. минимальным. При этом высветится путь, соответствующий минимальному, С:

1325517

Составитель А.Мишин

Редактор Н,Тупица Техред И.Попович КоРРектоР Т.Колб

Тираж 672 Подписное

ВНИИПИ Государственного комитета СССР по делам изобретений и открытий

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

Заказ 3112/46

Производственно-полиграфическое предприятие, r.Óæãoðoä, ул.Проектная,4

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

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

На чертеже представлена функциональная схема устройства.

В состав устройства для определения минимального пути в графе входит источник 1 регулируемого напряжения, блок 2 индикации, модели 3 узлов, содержащие пороговые элементы 4, например газоразрядные лампы, количество которых равно весу узла, моде ли 5 ветвей, содержащие пороговые 20 элементы 4, количества которых пропорционально равно весу ветви, и диоды 6, определяющие направление ветви графа.

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

При включении источника 1 .напряжение между его похпосами начинает возрастать и в определенный момент времени происходит зажигание группы газоразрядных ламп 4, суммарное нап,ряжение зажигания которых является минимальным для данного подключения их к источнику 1. При этом высвечивается путь, соответствующии минимальному. Блок 2 фиксирует напряжение между полюсами источника . и QII ределяет в заданном масштабе среднее время пути по транспортной сети.

Формула изобретения

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