Устройство для поиска двух независимыхКРАТчАйшиХ пуТЕй HA гРАфЕ Советский патент 1981 года по МПК G06G7/122 

1

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

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

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

Наиболее близким к предлагаемому является устройство для определения кратчс1йших путей на графе, содержащее модели ветвей и источник напряжения, причем каходая модель ветви состоит из тиристора, резистора и диодоп D.

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

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

Поставленная цель достигается тем, что в устройство, содержащее

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

10 последовательно соединенные элемент индикации и обмотку реле, выход порогового элемента подключен ко входу элемента индикации, каждая модель ветви второй группы содержит после15довательно соединенные элемент индикации и пороговый элемент, причем выход порогового элемента подключен к контакту реле, первый выход блока управления соединен с начальным узлом первой модели графа, второй выход блока управления подключен к начальному узлу второй модели графа, вход блока управления соединен с конечными узлами первой и второй мо25дели графа, и второй модели соответствующей ветви, а также тем, что блок управления содержит четыре разделительных диода, два реле, два источника напряжения и выключатель,

30 причем катоды первого и второго разделительных диодов объединены и подключены к первому выводу обмотки первого реле, второй вывод обмотки которого является первым выходом блока управления, катоды третьего и четвертого разделительных диодов объединены и подключены к первому выводу обмотки второго реле, второй вывод обмотки которого является вторым выходом блока управления, ано ды первого и третьего разделительных диодов объединены и подключены к замыкающему контакту выключателя, подвижный контакт которого соединен с выходом первого источника напряжения, входы первого и второго источников напряжения объединены и являются входом блока управления, выход второго источника напряжения соединен с подвижным контактом второго реле, замыкающий контакт которого подключен к подвижному контакту пер вого реле, за1.1ыкающий контакт которого соединен с анодом второго диод анод четвертого диода подключен к размыкающему контакту первого реле. На чертеже приведена схема предлагаемого устройства. Устройство содержит первую модел графа 1, предназначенную для опреде ления и индикации первого (основного) кратчайшего пути, пороговый эле мент 2 с регулируемой нелинейной характеристикой, элемент 3 индикаци источник 4 напряжения, вторую модел графа 5, предназначенную для выявле ния и индикации второго (резервного кратчайшего пути, источник 6 напряжения, блок 7 управления, реле 8, контакты 9 реле 8, пороговый элемент 10 с регулируемой нелинейной характеристикой, элемент 11 индикации, реле 12, контакты 13 и реле 12 реле 14, контакты 15 реле 14, разде лительные диоды 16-19, в ыключатель 2 Элементы 2 и 3 и реле 8 образуют модель ветви первой группы, а элементы 10 и 11 и контакты 9 - модель ветви второй группы. Устройство работает следующим об разом. На пороговых элементах 2 и 10 первой 1 и второй 5 моделях графа устанавливают величины напряжения пробоя, соответствующие весам ветвей исследуемого графа, после чего к исследуемым узловым точкам обоих моделей графа подключают исто ники напряжений 4 и 6. В исходном состоянии выходное напряжение источ ника 4 напряжения равно нулю, и с помощью контакта 13 реле 12 он подключен к первой модели графа. Внутреннее сопротивление пороговых элементов 2 и 10 очень велико, и цепь источника б напряжения разомкнута. При плавном увеличении выходного напряжения источника напряжения 4 п достижении определенной величины ег выходного напряжения произойдет пробой пороговых элементов 2 ветвей первой модели графа 1, для которых iПробей - - Эти ветви образуют Ьервый (основной) кратчайший путь. Величина сопротивления пробитых пороговых элементов 2 резко уменьшается. По ветвям, составляющим первый кратчайший путь проходит ток источника 6 напряжения, в результате чего элементы индикации 3 осуществляют индикацию первого (основного) кратчайшего пути, а .реле 8, сработав, своими контактами 9 осуществляет разрыв соответствующих ветвей второй модели графа 5. Протекание тока через реле 12 вызывает срабатывание последнего, и он своими контактами 13 переключает источник напряжения -4 от первой модели графа 1 ко второй. При дальнейшем увеличении выходного напряжения источника напряжения 4 происходит пробой пороговых элементов 10 второй модели графа, принадлежащих ветвям, составляющим второй (резервный) кратчайший путь. Протекание тока источника напряжения 6 через эти ветви обеспечивает индикацию элементами индикации 11 второго (резервного) кратчайшего пути. Срабатывает реле 14 и своими контактами 15 отключает источник напряжения 4. Ток источника 6 напряжения, протекая по ветвям обеих моделей графа, где пробиты пороговые устройства 2 и 10, обеспечивает индикацию с помощью элементов, индикации 3 и 11 одновременно обоих кратчайших путей. Преимущество предлагаемого устройства состоит в том, что оно позволяет автоматически производить поиск двух независимых кратчайших путей на графе. Формула изобретения 1. Устройство для поиска двух независимых кратчайших путей на графе, содержащее первую группу моделей ветвей, соединенных согласно топологии графа, причем каждая модель ветви первой группы содержит пороговый элемент, отличающе ес я тем, что, с целью повышения быстродействия, оно дополнительно содержит блок управления, вторую группу моделей ветвей, соединенных согласно топологии графа, причем каждая модель ветви первой группы дополнительно содержит последовательно соединенные элемент индикации и обмотку реле, выход порогового элемента подключен ко входу элемента индикации, каждая модель ветви вторрй группы содержит последовательно соединенные элемент индикации и пороговый элемент, причем выход порогового элемента подключен к контакту реле, первый выход блока управления соединен с начальным узлом первой модели графа, второй выход блока управления подключен к начгшьному узлу в±орой модели графа, вход блока управления соединен с конечными узлами первой и второй модели графа ,2. Устройство по п.1, отличающееся тем, что блок управления содержит четыре разделительных диода, два реле, два источника напряжения и выключатель, причем катоды первого и второго разделительных диодов объединены и подключены к первому выводу обмотки первого реле,второй вывод обмотки которого является первым выходом блока управления, катоды третьего и четвертого разделительных диодов объединены и подключены к первому выводу обмотКи второго реле, второй вывод обмотки которого является вторым выходом блока управления, аноды первого и третьего разделительных диодов объединены и подключены к замыкающему контакту выключателя, подвижный контакт которого соединен с выходом первогр исе точника напряжения, входы первого и второго источников напряжения объединены и являются входом блока управ ления, выход второго источника ндпря жения соединен с подвижным контактом второго реле, замыкающий контакт

0 которого подключен к подвижному контакту первого реле; замыкающий контакт которого соединен с анодом второго диода, анод четвертого диода подключен к размыкающему контакту

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

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

1.Авторское свидетел зство СССР №553628, кл. G 06 G 7/122, 1977.

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

0 №552617, кл. G 06 G 7/122, 1977 (прототип).