Устройство для определения минимального пути в графе
Похожие патенты | МПК / Метки | Текст | Заявка | Код ссылки
Номер патента: 1325517
Авторы: Михайленко, Озирский, Федотов
Текст
)4 0 06 О 7/1 фУ " с ОПИСАНИЕ ИЗОБРЕТЕНИЯ и л ОСУДАРСТВЕННЫЙ КОМИТЕТ СССРО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ АВТОРСКОМУ СВИДЕТЕЛЬСТВ(71) Киевский автомобильно-дорожный институт им.60-летия Великой Октябрь ской социалистической революции (72) Л.В.Федотов, В.И,МихайленкоС,В,Озирский(56) Авторское свидетельство СССР В 855672, кл. 6 06 6 7/122, 1979.Авторское свидетельство СССР У 12754 80, 19 85 .(54) УСТРОЙСТВО ДЛЯ ОПРЕДЕЛЕНИЯ МИНИМАЛЬНОГО ПУТИ В ГРАФЕ(57) Изобретение относится к вычислительной технике, может быть использовано для решения широкого круга экстремальных задач и позволяет определять минимальныи путь в графесо взвешенными вершинами, В составустройства входит источник 1 регулируемого напряжения, блок 2 индикации,модели 3 узлов, содержащие ключевыеэлементы, например газоразрядные лампы, количество которых равно весуузла, модели 5 ветвей, содержащиеключевые элементы 4, количество которых равно весу ветви, и диоды 6, определяющие направление ветви. Приповышении напряжения источника от нуля до некоторой пороговой величиныпроизойдет одновременное зажиганиегруппы газоразрядных ламп, суммарноенапряжение зажигания которых является, минимальным. При этом высветитсяпуть, соответствующий минимальному,Составитель А.МишинРедактор Н,Тупица Техред И,Попович Корректор Т.Колб Тираж 672 Подписное ВНИИПИ Государственного комитета СССР по делам изобретений и открытий 113035, Москва, Ж, Раушская наб д,4/5Заказ 3112/46 Производственно-полиграфическое предприятие, г,Ужгород, ул,Проектная,4 Изобретение относится к вычислительной технике и может быть использовано для решения широкого кругаэкстремальных транспортных задач,Цель изобретения - расширениефункциональных возможностей устройства за счет определения минимального пути в графе со взвешенными вершинами, 10На чертеже представлена функциональная схема устройства,В состав устройства для определения минимального пути в графе входитисточник 1 регулируемого напряжения,блок 2 индикации, модели 3 узлов,содержащие пороговые элементы 4,например газоразрядные лампы, количество которых равно весу узла, модели 5 ветвей, содержащие пороговые 20элементы 4, количество которых пропорционально равно весу ветви, и диоды 6, определяющие направление ветви графа.Устройство работает следующим 25образом. При включении источника 1 .напряжение между его похпосами начинает возрастать и в определенный момент времени происходит зажигание группы газоразрядных ламп 4, суммарное нап,ряжение зажигания которых является минимальным для данного подключения их к источнику 1. При этом высвечивается путь, соответствующии минимальному, Блок 2 фиксирует напряжение между полюсами источникаи оп-,ределяет в заданном масштабе среднеевремя пути по транспортной сети,Формула из обр етения Устройство для определения минимального пути в графе, содержащее источник регулируемого напряжения, блок индикации и модели ветвей, каждая из которых содержит соединенные последовательно пороговые элементы, выполненные в виде газоразрядных ламп, количество которых равно весу графа, причем блок индикации подключен параллельно источнику регулируе-. мого напряжения, о т л и ч а ю щ е - е с я тем, что, с целью расширения функциональных возможностей устройства за счет определения минимального пути в графе сО взвешенными вершинаьи, в него введены модели узлов, каждая из которых содержит соединенные последовательно пороговые элементы, выполненные в виде газоразрядных ламп, количество которых равно весу узла, а в каждую модель ветви введен диод, вкпюченный последовательно с пороговыми элементами, направление включения которого определяет направление ветви графа, причем выход источника регулируемого напряжения подключен к модели узла начала пути, опорный вход источника регулируемого напряжения подключен к модели узла конца пути, модели узлов и модели ветвей соединены согласно топологии графа.
СмотретьЗаявка
3930221, 17.06.1985
КИЕВСКИЙ АВТОМОБИЛЬНО-ДОРОЖНЫЙ ИНСТИТУТ ИМ. 60-ЛЕТИЯ ВЕЛИКОЙ ОКТЯБРЬСКОЙ СОЦИАЛИСТИЧЕСКОЙ РЕВОЛЮЦИИ
ФЕДОТОВ ЛЕВ ВАСИЛЬЕВИЧ, МИХАЙЛЕНКО ВЛАДИМИР ИВАНОВИЧ, ОЗИРСКИЙ СЕРГЕЙ ВАСИЛЬЕВИЧ
МПК / Метки
МПК: G06G 7/122
Метки: графе, минимального, пути
Опубликовано: 23.07.1987
Код ссылки
<a href="https://patents.su/2-1325517-ustrojjstvo-dlya-opredeleniya-minimalnogo-puti-v-grafe.html" target="_blank" rel="follow" title="База патентов СССР">Устройство для определения минимального пути в графе</a>
Устройство для определения критического пути в графе
Номер патента: 962968
Опубликовано: 30.09.1982
Авторы: Гайдуков, Кислинский, Крикунов, Мачулин, Титов
МПК: G06F 15/173
Метки: графе, критического, пути
...все узлы моделируемого графасформированы, При этом на выходе эле мента И 18 появляется высокий потенциал, который поступает на выход 23 зустройства и свидетельствует об окончании первого этапа вычислений, атакже через элемент НЕ 19 прекраща ет подачу счетных импульсов с генератора 16 через элемент И 17. Наэтом первый этап работы устройствазаканчивается.На втором этапЕ заносится только 20 информация в виде матрицы смежностимоделируемого графа, при этом в единичное состояние устанавливаютсятриггеры 3, моделируюшие ветви граФа, а также 13 и 13, соответствую щие конечной и начальной вершинам.После занесения исходной информациина вход 23 (начинается третий этапработы устройства) подается разрешающий сигнал, в Результате чего счетные импульсы...
Устройство для определения кратчайшего пути в графе
Номер патента: 1314354
Опубликовано: 30.05.1987
Авторы: Клишин, Лелис, Полищук
МПК: G06G 7/122
Метки: графе, кратчайшего, пути
...19 и 20 и выходы 21, 22 модели ветви. Устройство работает следующим образом.С помощью блоков 4 устанавливают в управляющих цепях тиристоров 7 токи, соответствующие напряжениям переключения тир исторов, пропорциональным весам узлов ветвей. Полюса источника 1 подключают к моделям начального и конечного узлов графа.При увеличении напряжения источника 1 от нуля до некоторой определенной величины происходит переключение тиристоров, принадлежащих кратчайшему пути.В этой цепи потечет ток, создавая падение напряжения на резисторах блоков 10, в результате чего будут отмечены узлы и вершины кратчайшего пути (элементы индикации, обеспечивающие выдачу сигналов о протекании тока, на чертеже не показаны).Устройство позволяет задавая одинаковыми веса...
Устройство для определения двух независимых кратчайших путей на графе
Номер патента: 1336041
Опубликовано: 07.09.1987
Авторы: Клишин, Лелис, Полищук
МПК: G06G 7/122
Метки: графе, двух, кратчайших, независимых, путей
...графа, модели 5 вершин графа. В состав каждой модели 3 входит пороговый элемент 6, элемент 7 индикации и обмотка 8 реле. Модель 5 содержит включенные последовательно контакты 9 реле моделей 3 тех ребер графа, которые выходят из данной вершины. Пороговый элемент 6 может быть. выполнен, например, на базе тиристора О, переменного резис тора 11 и источника 12 постоянного напряжения.Устройство работает следующим образом.В исходном состоянии напряжение на выходе источников 1 и 2 равно нулю. С помощью переменных резисторов 11 в моделях 3 и 4 ребер устанавливают токи в управляющих цепях тиристоров 10, соответству 1 ощие заданным напряжениям их переключения, пропорциональным весам ребер.При плавном увеличении выходного напряжения источника 1...
Устройство для исследования путей в графе
Номер патента: 1348850
Опубликовано: 30.10.1987
МПК: G06F 15/173
Метки: графе, исследования, путей
...что обусловливает появление единичного сигнала на выходе элемента НЕ 4 и переход триггера 5 в состояние "1",На втором этапе вновь приводят20 устройство в исходное состояние, но регистры 1 О не обнуляются, а в матрицу 1 заносят информацию о топологии инвертированного графа, т.е. данные матрицы исходного графа, но транспортированные относительно неглавной диагонали.Затем пускают устройство и в счетчиках 8 повторно фиксируются наиболее ранние времена выполнения вершин ин 30 вертированного графа, которые в прямом графе соответствуют величинам максимальных путей из вершин графа в его конечную вершину. Однако в регистры 10 содержимое счетчиков 8 уже не ,записывается, так как единичный потенциал с первого разряда информационного счетчика 14...
Устройство для определения кратчайшего пути на графе
Номер патента: 1817102
Опубликовано: 23.05.1993
Авторы: Дробахин, Кудрявцев, Шевчик
МПК: G06F 15/20
Метки: графе, кратчайшего, пути
...графа,составляющих кратчайший путь в графе.10 35 триггер, блок выбора максимального сигнала, аналого-цифровой преобразователь и блок формирования топологии графа, содержащий К узлов топологии графа, при этом, вход запуска устройства подключен к 40 45 50 15 20 25 ЗО Пришедший импульс поступает на вход поляризаторов 2 руппы, Гри этом на выходе К-го поляризатора группы появляется световой сигнал максимальной интенсивности, который преобразуется соответствующим фотоприемником 3-К группы в электрический. Этот сигнал через открытые ключи 5 группы поступает на входы блока 8 выбора максимального сигнала и проходит на входы аналого-цифрового преобразователя 9. Этот же сигнал, пройдя через элемент ИЛИ 6, обнуляет триггер 7, который закрывает...