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

ОПИСАНИЕ ИЗОБРЕТЕНИЯ Союз Сфеетскик Сециаектическия Реслублик(22) Заявлено 291179 (21) 2844 б 29/18-24 (53) М. Кл. с присоединением заявки Но(23) Приоритет С 06 С 7/122 бкударствениый комитет СССР во аелам изобретеиий я открытий(54) УСТРОЙСТВО ДЛЯ ПОИСКА ДВУХ НЕЗАВИСИМЫХ КРАТЧАЙШИХ ПУТЕЙ НА ГРАФЕУстройство относится к аналоговому моделированию и предназначено для поиска кратчайших путей на графе.Известно устройство для определения кратчайших путей на графе, содержащее модели ветвей, индикаторы, источник напряжения и источник тока, причем каждая модель ветви состоит из переменного резистора и реле 13 .Однако известное устройство ие позволяет производить поиск двух независимых кратчайших путей на гра- фЕ.Наиболее близким к предлагаемому является устройство для определения кратчайших путей на графе, содержащее модели вЕтвей и источник напряжения, причем каждая модель ветви состоит из тиристора, резистора и диодов 21,Это устройство позволяет моделировать ветви графа с несимметричными весовыми коэффициентами, но не приспособлено для поиска двух неэависииях кратчайших путей на графе.Цель изобретения - расширение функциональных возможностей эа счет йолучения совокупности двух независюаас ратчайших путей.Поставленная цель достигается тем, что в устройство, содержащее первую группу моделей ветвей, соединенных согласно топологии графа,причем каждая модель ветви первойгруппы содержит пороговый элемент,дополнительно введены блок Управления, вторая группа моделей ветвей,соединенных согласно топологии графа, причем каждая модель ветви первой группы дополнительно содержитпоследовательно соединенные элементиндикации и обмотку реле, выход порогового элемента подключен ко входу элемента индикации, каждая модельветви второй группы содержит после довательно соединенные элемент индикации и пороговый элемент, причемвыход порогового элемента подключенк контакту реле, первый выход блокауправления соединен с начальным уэ лом первой модели графа, второйвыход блока управления подключен кначальному узлу второй модели графа,вход блока управления соединен сконечными узлами первой и второй мо 2 к дели графа, и второй модели соответствующей ветви, а также тем, чтоблок управления содержит четыре разделительных диода, два реле, два источника напряжения и выключатель, 30 причем катоды первого и второго раэделительных диодов объединены н подключены к первому выводу обмотки первого реле, второй вывод обмотки которого является первым выходом блока управления, катоды третьего и четвертого разделительных диодов объединены и подключены к первому выводу обмотки второго реле, второй вывод обмотки которого является вторым выходом блока управления, аноды первого и третьего разделительных диодов объединены и подключены к10 замыкающему контакту выключателя, подвижный контакт которого соединен с выходом первого источника напряжения, входы первого и второго источникбв напряжения объединены и явля ются входом блока управления, выход эторого источника напряжения соединен с подвижным контактом второго реле, замыкающий контакт которого подключен к подвижному контакту пер- Щ вого реле, замыкающий контакт которого соединен с анодом второго диода, анод четвертого диода подключен к размыкающему контакту первого реле.На чертеже приведена схема пред лагаемого устройства.Устройство содержит первую модель графа 1, предназначенную для определения и индикации первого (основного) кратчайшего пути, пороговый элемент 2 с регулируемой нелинейной 30 характеристикой, элемент 3 индикации, источник 4 напряжения, вторую модель графа 5, предназначенную для выявления и индикации второго (резервного) кратчайшего пути, источник б напряжения, блок 7 управления, реле 8, контакты 9 реле 8, пороговый элемент 10 с.регулируемой нелинейной характеристикой, элемент 11 индикации, реле 12, контакты 13 и реле 12, 4 О реле 14, контакты 15 реле 14, разделительные диоды 16-19, выключатель 20.Элементы 2 и 3 и реле 8 образуют модель ветви первой группы, а элементы 10 и 11 и контакты 9 - модель ветви второй группы.Устройство работает следующим об- разом.На пороговых элементах 2 и 10 первой 1 и второй 5 моделях графа устанавливают величины напряжения"пробоя", соответствующие "весам" ветвей исследуемого графа, после чего к исследуемым узловым точкам обоих моделей графа подключают источники напряжений 4 и 6. В исходном 55 состоянии выходное напряжение источника 4 напряжения равно нулю, и с помощью контакта 13 реле 12 он подключен к первой модели графа, Внутреннее сопротивление пороговых эле- ментов 2 и 10 очень велико, и цепь источника б напряжения разомкнута.При плавном увеличении выходного напряжения источника напряжения 4 по достижении определенной величины его выходного напряжения произойдет "пробой" пороговых элементов 2 ветвейпервой модели графа 1, для которыхФ "проб =о. Эти Ветви образуютпервый (основной) кратчайший путь.Величина сопротивления "пробитых"пороговых элементов 2 резко уменьшается. По ветвям, составляющим первый кратчайший путь проходит токисточника б напряжения, в результатечего элементы индикации 3 осуществляют индикацию первого (основного)кратчайшего пути, а реле 8, сработав,своими контактами 9 осуществляетразрыв соответствующих ветвей второймодели графа 5. Протекание тока черезреле 12 вызывает срабатывание последнего, и он своими контактами 13 переключает источник напряжения 4 отпервой модели графа 1 ко второй.При дальнейшем увеличении выход-.ного напряжения источника напряжения 4 происходит "пробой" пороговыхэлементов 10 второй модели графа,принадлежащих ветвям, составляющимвторой (резервный) кратчайший путь.Протекание тока источника напряжения6 через эти ветви обеспечивает индикацию элементами индикации 11 второго (резервного) кратчайшего пути.Срабатывает реле 14 и своими контактами 15 отключает источник напряжения 4. Ток источника б напряжения,протекая по ветвям обеих моделей графа, где "пробиты" пороговые устройства 2 и 10, обеспечивает индикациюс помощью элементов индикации 3 и11 одновременно обоих кратчайшихпутей.Преимущество предлагаемого устройства состоит в том, что оно позволяет автоматически производить поискдвух независимых кратчайших путейна графе,Формула изобретения1. Устройство для поиска двух независимых кратчайших путей на графе, содержащее первую группу моделей ветвей, соединенных согласно топологии графа, причем каждая модель ветви первой группы содержит пороговый элемент, о т л и ч а ю щ е ес я тем, что, с целью повышения быстродействия, оно дополнительно содержит блок управления, вторую группу моделей ветвей, соединенных согласно топологии графа, причем каждая модель ветви первой группы дополнительно содержит последовательно соединенные элемент индикации и обмотку реле, выход порогового элемента подключен ко входу элемента индикации, каждая модель ветви второй группы содержит последовательно соединенные элемент индикации и пороговый элемент, причем выход по851418 каз 6361/70 Тираж 745 Подписно ИП нал ППП "Патент", г.ужгород, ул.Проектная,рогового элемента подключен к контакту реле, первый выход блока управления соединен с начальным узлом первой модели графа, второй выход блока управления подключен к начальному узлу второй модели графа, вход блока управления соединен с конечными узлами первой и второй модели графа2. Устройство по п.1, о т л и ч а ю щ е е с я тем, что блок управления содержит четыре разделительных диода, два реле, два источника напряжения и выключатель, причем катоды первого и второго разделительныхдиодов объединены и подключены к первому выводу обмотки первого реле, второй вывод обмотки которого является первым выхоДом блока управления, катоды третьего и четвертого разделительных диодов объединены и подключены к первому выводу обмотки второго реле; второй вывод обмоткн которого является вторым выходом бло ка управления, аноды первого и третьего разделительных диодов объединеныи подключены к замыкающему контактувыключателя, подвижный контакт которого соединен с выходом первого источника напряжения, входы первогои второго источников напряжения объединены и являются входом блока управления, выход второго источника напряжения соединен с подвижным контактомвторого реле, замыкающий контакткоторого подключен к подвижному контакту первого реле, зааюкающяй контакт которого соединен с анодом второго диода, анод четвертого диодаподключен к раэмыкающему контакту 5 первого реле.Источники информации,принятые во внимание при экспертизе1, Авторское свидетельство СССР9553628, кл. 6 06 6 7/122, 1977.20 2. Авторское свидетельство СССР9552617, кл. С 06 6 7/122, 1977.