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

 

Доносе

> цо-то

АНИЕ нц 5526l7

ОПИС

Сова ьсеетских

Социалистических

Республик

ИЗОБРЕТЕНИЯ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (61) Дополнительное к авт. свид-ву (22) Заявлено 04.05.75 (21) 2130380/24 (51) М. Кл 2 б 06G 7/122 с присоединением заявки № (23) Приоритет

Опубликовано 30.03.77. Бюллетень № 12

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

Семта Министрае СССР (53) УДК 681.14(088.8) пе делам изобретеиий и открытий

Дата опубликования описания 11.04.77 (72) Автор изобретения

А. В. Холин (71) Заявитель (54) УСТРОЙСТВО ДЛЯ ОПРЕДЕЛЕНИЯ КРАТЧАЙШИХ

ПУТЕЙ НА ГРАФЕ

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

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

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

Ueab изобретения — упрощение устройства.

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

На фиг. 1 показана принципиальная схема модели двунаправленной ветви; на фиг, 2— общая схема устройства, представляющая собой соединенные модели ветвей Mij согласно топологии исследуемого графа.

Схема модели ветви содержит тиристоры 1

5 и 1, элемент 2 управления тиристорами, диоды 3 и 3, шунтирующие один из тиристоров в зависимости от направления тока, протекающего в ветви Ц, резистор 4, сопротивление которого используется для индикации кратчай10 шего пути, а также источник 5 напряжения.

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

2. С помощью потенциометров элемент 2 уп15 равления тиристорами устанавливает ток в управляющей цепи тиристора, соответствующий заданному напряжению переключения, пропорциональному «весу» данной ветви.

К исследуемым узлам графа, между кото20 рыми определяется кратчайший путь, подключается регулируемый источник ЭДС Е.

При увеличении напряжения источника от 0 до Е „в какой-то момент времени произойдет переключение тиристоров, принадлежа25 о щих цепи, для которой U;=min. В этой

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

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

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

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

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

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

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

552617

Составитель С. Громова

Техред А. Камышникова Корректор Л. Денискина

Редактор И. Грузова

Типография, пр. Сапунова, 2

Заказ 676/20 Изд. Ке 318 Тираж 899 Подписное

ЦНИИПИ Государственного комитета Совета Министров СССР по делам изобретений и открытий

113035, Москва, Я-35, Раушская наб., д. 4/5