Устройство для определения кратчайших путей на графе Советский патент 1977 года по МПК G06G7/122 

1

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

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

Известно также наиболее близкое по технической сущности к изобретению устройство, содержащее модели ветвей, соединенные согласно топологии исследуемого графа 2. Недостатком его является сложность, обусловленная наличием в каждой модели ветви источников ЭДС, гальванически не связанных друг с другом.

Цель изобретения - упрощение устройства.

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

На фиг. 1 показана принципиальная схема .модели двунаправленной ветви; на фиг. 2 -

общая схема устройства, представляющая собой соединенные модели ветвей Mij согласно топологии исследуемого графа.

Схема модели ветви содержит тиристоры 1 и Г, элемент 2 управления тиристорами, диоды 3 и 3, шунтирующие один из тиристоров в зависимости от направления тока, протекающего в ветви ij, резистор 4, сопротивление которого используется для индикации кратчайщего пути, а также источник 5 напряжения. Работает устройство следующим образом. Из моделей ветвей собирается схема топологии, аналогичная исследуемому графу фиг. 2. С помощью потенциометров элемент 2 управления тиристорами устанавливает ток в управляющей цепи тиристора, соответствующий заданному напряжению переключения, пропорциональному «весу данной ветви.

К исследуемым узлам графа, между которыми определяется кратчайший путь, подключается регулируемый источник ЭДС Е. Нри увеличении напряжения источника от О до Етах в какой-то момент времени произойдет переключение тиристоров, принадлежа2 . В этой

щих цепи, для которой

цепи потечет ток, создающий падение напряжения на сопротивлении резистора 4, в ре30 зультате чего будут отмечены ветви графа.

принадлежащие кратчайшему пути (элементы индикации на схеме не показаны).

Применение в качестве порогового устройства тиристора, а также схемы, позволяющей моделировать двунаправленные ветви графа как с симметричными, так и с несимметричными весовыми коэффициентами, использование одного источника ЭДС для всех моделей ветви упрощает устройство.

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

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

соединенные согласно топологии исследуемого графа, отличающ-ёеся тем, что, с целью упрощения устройства, оно содержит источник напряжения, а модель ветви содержит тиристор с элементом управления, резистор, соединенный последовательно с тиристором, и диоды, подключенные параллельно тиристору, а элемент управления тиристором подключен к источнику напряжения.

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

1.Авт. св. № 231903, кл. G ОбО 7/48, 1970.

2.Авт. св. № 344463, кл. G 06Q 7/48, 1970 (прототип).

iPui.2