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

 

ОПИСАНИЕ

ИЗОБРЕТЕНИЯ

К АВТОРСКОМУ, СВИ ЕТЕЛЬСТВУ

Союз Сееетскик

Сецналнстнческня

Реслублнк (ii>851418 (61) Дополнительное к ввт. свмд-ву (22) Заявлено 291179 (21) 2844б 29/18-24 с присоединением заявки М (23) Приоритет

Опубликовано 300781. Бюллетень М 28

Дата опубликования описания 300781 я)м. к .э

G Об С 7/122

Гоеударственный комитет

СССР во делан изобретений я открытий (53) УДК б81. ззз (088.8) (72) Авторы изобретения

Б.В.Волкодаев и A.B.Õoëèí (7! ) Заявитель (54 ) УСТРОЙСТВО ДЛЯ ПОИСКА ДВУХ НЕЗАВИСИМЬ)Х

КРАТЧАЙШИХ ПУТЕЙ HA ГРАФЕ

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

Известно устройство для определения кратчайших путей на графе, содержащее модели ветвей, индикаторы, источник напряжения и источник тока, причем каждая модель ветви состоит из переменного. резистора и реле P1) .

Однако известное устройство ие позволяет производить поиск двух независимых кратчайших путей íà rpaфЕ.

Наиболее близким к предлагаемому является устройство для определения кратчайших путей на графе, содержащее модели вЕтвей и источник напряжения, причем каждая модель ветви состоит из тиристора, резистора и диодов E2), Это устройство позволяет моделировать ветви графа с несимметричными весовыми коэффициентами, но не приспособлено для поиска двух независиьих кратчайших путей на графе.

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

Поставленная цель достигается тем, что в устройство. содержащее первую группу моделей ветвей, соединенных согласно топологии графа, причем каждая модель ветви первой группы содержит пороговый элемент, дополнительно введены блок Управления, вторая группа моделей ветвей, соединенных согласно топологии графа, причем каждая модель ветви первой группы дополнительно содержит последовательно соединенные элемент индикации и обмотку реле, выход порогового элемента подключен ко входу элемента индикации, каждая модель ветви второй группы содержит после1S довательно соединенные элемент индикации и пороговый элемент, причем выход порогового элемента подключен к контакту реле, первый выход блока управления соединен с начальным уэ20 лом первой модели графа, второй выход блока управления подключен к начальному узлу второй модели графа, вход блока управления соединен с конечными узлами первой и второй модели графа, и второй модели соответствующей ветви, а также тем, что блок управления содержит четыре разделительных диода, два реле, два источника напряжения и выключатель, 30 причем катоды первого и второго раз851418 делительных диодов объединены н подключены к первому выводу обмотки первого реле, второй нывод обмотки которого является первым выходом блока управления, катоды третьего и четвертого разделительных диодов объединены и подключены к первому выводу обмотки второго реле, второй вывод обмотки которого является вторым выходом блока управления, аноды первого и третьего разделительных диодов объединены и подключены к 10 замыкающему контакту выключателя, подвижный контакт которого соединен с выходом первого источника напряжения, входы первого и второго источникбв напряжения объединены и явля- 15 ются входом блока управления, выход второго источника напряжения соединен с подвижным контактом второго реле, замыкающий контакт которого подключен к подвижному контакту пер- Щ ного реле, замыкающий контакт которого соединен с анодом второго диода, анод четвертого диода подключен к размыкающему контакту первого реле.

На чертеже приведена схема пред- 25 лагаемого устройства.

Устройство содержит первую модель графа 1, предназначенную для определения и индикации первого (основного) кратчайшего пути, пороговый элемент 2 с регулируемой нелинейной 30 характеристикой, элемент 3 индикации, источник 4 напряжения, вторую модель графа 5, предназначенную для выявления H индикации второго (резервного) кратчайшего пути, источник 6 напряжения, блок 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 очень велико, и цепь источника 6 напряжения разомкнута.

При плавном увеличении выходного напряжения источника напряжения 4 по достижении определенной величины его выходного напряжения произойдет "пробой" пороговых элементов 2 ветвей первой модели графа 1, для которых ф О„„р 6с„,= io. Эти Ветви образуют первый (основной) кратчайший путь.

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

При дальнейшем увеличении выход- . ного напряжения источника напряжения 4 происходит "пробой" пороговых элементов 10 второй модели графа, принадлежащих ветвям, составляющим второй (резервный) кратчайший путь.

Протекание тока источника напряжения

6 через эти ветви обеспечивает индикацию элементами индикации 11 второго (резервного) кратчайшего пути.

Срабатывает реле 14 и своими контактами 15 отключает источник напряжения 4. Ток источника 6 напряжения, протекая по ветням обеих моделей графа, где "пробиты" пороговые устройства 2 и 10, обеспечивает индикацию с помощью элементов индикации 3 и

11 одновременно обоих кратчайших путей .

Преимущество предлагаемого устройства состоит в том, что оно позволяет автоматически производить поиск двух независимых кратчайших путей на графе.

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

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

2. Устройство по п.1, о т л и ч а ю щ е е с я тем, что блок управления содержит четыре разделительных диода, два реле, два источника напряжения и выключатель, причем катоды первого и второго разделительных диодов объединены и подключены к первому выводу обмотки первого реле,. второй вывод обмотки которого является первым выхоДом блока управления, катоды третьего и четвертого разделительных диодов объединены и подключены к первому выводу обмотки второго реле; второй вывод обмотки которого является вторым выходом блоI

ВНИИПИ Заказ 6361/70 Тираж 745 Подписное

Филиал ППП "Патент", г.ужгород, ул.Проектная, 4

7 !

I !

16

1

1 ! !

L ка управления, аноды первого и третьего разделительных диодов объединены и подключены к замыкающему контакту выключателя, подвижный контакт которого соединен с выходом первого источника напряжения, входы первого и второго источников напряжения объединены и являются входом блока управ ления, выход второго источника напря< жения соединен с подвижным контактом второго реле, замыкающий контакт которого подключен к подвижному контакту первого реле, замыкающий контакт которого соединен с анодом второго диода, анод четвертого диода подключен к раэмыкающему контакту

15 первого реле.

Источники информации, принятые во внимание при экспертизе

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

9553628, кл. G 06 G 7/122, 1977.

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

9552617, кл. С 06 G 7/122, 1977. (прототип).