Устройство для определения кратчайших путей на графе

Союз Советскии Социалистицескии РеспубликОП ИСА ИЗОБРЕТ К АВТОРСКОМУ СВИД е кавт.с 61) Дополнительн 22) Заявлено 04.05 21) 51) М. Кл.еб 0667/12 рисоединением за Государственный комитет Совета Министров СССР оо делам изобретений и открытий, Холин 71) Заявите СТРОЙСТВО ДЛЯ ОПРЕДЕЛЕНИЯ КРАТЧАЙШИ ПУТЕЙ НА ГРАФЕ(5 Поставленная цель достигается тем, что в предложенное устройство введены источник тока, индикатор тока и блоки индикации по числу ветвей, соединенные согласно топологии исследуемого графа и подключенные к пжледовательно соединенным источнику тока и индикатору тока. Блоки индикации соединены с соответствующими моделями ветвей. Каждая модель ветви дополнительно содержит пороговый элемент, подключенный последователь-, но переменному резистору.Схема предлагаемого устройства для определе. ния кратчайших путей на графе представлена на чертеже,Оно содержит две различные электрические цепи, идентично соединенные согласно топологии исследуемого графа. Первая цепь, содержащая переменные резисторы 1, пороговый элемент 2, на который подается напряжение с ерительных резисторов 3, и регулируемый и к ЭДС 4, служит для определения ветвей исследуемой сети с изм сточним. ер ак симальным токВторая цепь со онгакты 5 порого 1 и но числу вет локом индикации родеиствия устроиства,1Изобретение относится к области специализиро.ваной вычислительной .техники 1 и может быть ис. пользовано при исследовании отдельных графов, проектировании и распределении каналов на сетях связи и информационных сетях и разработке эконо.- мических вариантов транспортных перевозок.Известно устройство для моделирования дву.направленной ветви сетевого графика, в котором в качестве основной модели ветви предлагаются ре гулируемые источники э,д,с, и диодный мост 1. 1 О Недостаток известного устройства состоит в том, что плавное изменение, порогового элемента с по.мощью диодного моста и источника напряжения в моделях ветвей графа приводит к значительному усложнению схемы моделирующего устройства. 1 нБлижайшим по технической сущности к данно. му изобретению является устройство, содержащее модели ветвей, соединенные согласно топологии исследуемого графа и подключенные к источнику напряжения, причем модель ветви содержит переменный резистор 12 .Недостаток такого устройства состоит в низком быстродействии.Целью изобретения является .повышение быстВСЕСЭЮЗНАЯ дт628 жит нормально разомкнутыеэлемента 2, блоки индика.графа, (в данном случае инадлежащим кратчайшему3пути, служат лампочки накаливания), источник тока 7 и индикатор тока 8, выполненный в виде реле индикации наличия кратчайшего пути, посредством контактов 9 отключающего источник э.д.с. 4 после завершения процесса определения кратчай.щего пути. Эта цепь служит для выделения и фиксации кратчайшего пути.Устройство работает следующим образом, На коммутационном табло из элементов ветви:резисторов 1, 3, пороговых элементов 2, контактов 5 и лампочки накаливания 6 собирается схема, по топологии аналогичная исследуемому графу.На переменных резисторах 1 устанавливают значе ния, пропорциональные длине ветви графа (расстоя. надю между вершинами, стоимости связывающей линии и т.п.) .К исследуемым точкам графа, между которыми определяется кратчайший путь (точки 10 - 11 и 2 - 13) подключают источник э.д.с, 4 и источник тока 7 соответственно. При линейном увеличении напряжения источника э.д.с, 4 от О до Е токи в ветвях увеличиваются пропорционально сопротивлениям ветвей Б; (длине ветви).В отдельных ветвях цепи ток достигает значе. ния У, при котором срабатывает пороговый эле. мент 2, замыкающий свой контакт 5 в соответствующей ей параллельной цепи до тех пор, пока из лампочек 6 и контактов 5 пороговых элементов 2 не будет создана электрическая цепь для источника тока 7. В результате ток течет не по всем ветвям, отмеченным пороговыми элементами 2, а только пц тем из них, которые создали сквозную цепь для источника тока 7. Лампочки в этих ветвях горят, отмечая кратчайший пут, между заданными точками 12 - 13, причем ток в этой цепи не зависит от числа последовательно включенных ламп (в цепи с источником тока величина тока не зависит от величины нагрузки). Наличие тока в цепи с лампами накаливания (2- 3) отмечается реле 8, которое отключает от цепи (1 О - ) источник э.п.с, 4, что предотвращает дальнейшее увеличение тока и по 4явление ложных цепей кратчайшего пути. Пороговые элементы 2 при этом остаются заблокированными.После кратковременного снятия общего напряжения питания (для разблокировки) схема возвра.щается в исходное состояние и готова к следующимизмерениям.Преимущество предлагаемого устройства состоит в том, что для определения кратчайшего пути1 О не требуется перебор и поставленная задача решается практически мгновенно,Кроме того, в предлагаемом устройстве использованы на всю схему один источник э.д.с. и одинисточник тока,Формула иэо бре тения20Устройство для определения кратчайших путейна графе, содержащее модели ветвей, соединенныесогласно топологии исследуемого графа и подключенные к источнику напряжения, причем модельветви содержит переменный резистор, о т л и ч а ющ е е с я тем, что, с целью повышения быстродействия, устройство содержит источник тока, индикатортока и блоки индикации по числу ветвей, соединен.ные согласно топологии исследуемого графа и поду ключенные к последовательно соединенным источнику тока и индикатору тока, блоки индикациисоединены с соответствующими моделямн ветвейпричем каждая модель ветви дополнительно содержит пороговый элемент, подключенный последова.яь тельно переменному резистору.Источники информации, принятые во вниманиепри экспертизе:1, Авторское свидетельство СССР 9344463,МКИ 606 6 7/48, 1970 г,2, Авторское свидетельство СССР К 329539,МКИ 6 Об 6 7/48, 1970 (прототип).553628 А. Власе Подпи Тираж 509ИИПИ Государственного комитетапо делам изобретений и113035, Москва, Ж, Раушс каз 19439 СССР Редактор Л, Утехина Составитель С, Громова ехред И, Асталош Корре Совета Министоткрытийкая наб., д. 4/5 тент ", г. Ужгород, ул, Проектная