Всеооюзная пат?г^о-тсш"кная'б!'1блиот1'на

О П И С А Н И Е 305484

ИЗОБРЕТЕН ИЯ

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

Фовз Советоких

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

Республик

Зависимое от авт. свидетельства №

3 аявлено 08,Х11,1969 (№ 1383901/18-24) с присоединением заявки №

Приоритет

Опубликовано 04.V1.1971. Бюллетень № 18

Дата опубликования описания 28.IX.1971

МПК G 06g 7/34 комитет по лолам изобретений и открытий прн Совете Министров

СССР

УДК 681.333;16(088.8) Авторы изобретения

В. В. Васильев, А. Г. Додонов и А. И. Левина

Институт кибернетики АН Украинской ССР

Заявитель

УСТРОЙСТВО ДЛЯ МОДЕЛИРОВАНИЯ ЭКСТРЕМАЛЬНЫХ

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

Изобретение относится к области вычислительной техники.

Известны устройства для моделирования экстремальных путей на графе, содержащие соединенные в соответствии с топологией гра- 5 фа модели ветвей на счетчиках, триггерах, логических схемах «НЕ», «И», «ИЛИ» и инверторах.

Все известные устройства имеют ограниченные функциональные возможности. 10

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

В предлагаемом устройстве это достигается тем что в нем выход счетчика в каждой модели ветви соединен с одним из входов 15 схемы «И», выход которой соединен с единичным входом триггера, подключенного единичным выходом к одному из входов второй схемы «И» и единичному входу второго триггера, нулевой выход которого соединен с од- 20 ним из входов третьей схемы «И», подключенной вторым входом к шине управления решением задачи о длиннейшем пути; выход третьей схемы «И» соединен со входом инвертора, выход которого соединен с выход- 25 ным полюсом модели ветви; единичный выход второго триггера соединен со входом четвертои схемы «И», подкл оченнои втор м входом к шине управления решением задачи о кратчаишем пути, а выходом к одному из llo- 30 люсов диода, другой полюс которого соединен с выходным полюсом модели ветви; выходной полюс модели ветви соединен со входом инвертора, выход которого соединен со входами второй и пятой схем «И», причем выход второй схемы «И» подключен к индикаторному выходу модели ветви, а выход инвертора подключен к ее входному полюсу", второй вход пятой схемы «И» соединен с шиной тактового питания, а ее выход подключен к нулевому входу первого триггера.

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

Устройство содержит модели ветвей на инверторах 1 — 8, двухвходовых схемах «И» 4—

8, счетчике 9, триггерах 10, 11, диоде 12.

Устройство работает следующим образом.

Модели ветвей соединяются между собой полюсами 13 и 14 в соответствии с топологией графа.

В счетчик 9 модели ветви предварительно заносится число импульсов, дополняющее длину ветви до полной емкости счетчика. 1 риггеры 10 и 11 находятся первоначально в нулевом состоянии, и на полюсах 18 и 14 нулевой потенциал. В некоторый момент времени на полюсе 13 модели ветви появится сигнал разрешения отсчета числа импульсов, pBBkl0I о числу. ихIII) ;IüI:ÎÂ ъ1аксимальнои емкости счетчика 9. тот сигнал откроет схему 5 совпадения и в счетчик 9 начнут поступать

305484

io

15 импульсы тактовой серии через полюс 16. При появлении на выходе счетчика 9 импульса переполнения триггеры 10 и 11 установятся в единичное состояние. Сигнал с единичного выхода триггера 10 поступает на один из входов схемы 4 совпадения.

Сигнал с нулевого выхода триггера 11 поступает на один из входов схемы 6 совпадения, второй вход 16 которой управляется сигналами с шины управления решением задачи о длиннейшем пути. Сигнал с вьгхода этой схемы совпадения поступает на вход схемы совпадения, которая образуется соединением инверторов 2 полюсами 14 моделей ветвей, сходящихся в одной из вершин графа.

Сигнал с единичного выхода триггера 11 поступает на один из входов другой схемы б совпадения, второй вход 17 которой управляется сигналами с. шины управления решением задачи о кратчайшем пути. Сигнал с выхода этой смемьг 4 совмадения поступает на вход схемьг ИЛИ» ; которая образуется соединецием диада 12.g, цолгосом 14 модели ветви.

В случае решения задачи о длиннсйшем пути на вход 16 подается разрешающий потенциал, а на вход 17 решением задачи о кратчайшем пути — запрещающий.

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

Если же на выходном полюсе 14 модели ветви еще не появился разрешающий сигнал, то инвертор 8 дает разрешающий сигнал на схемы совпадения 7 и 8. На второй вход 18 схемы 8 совпадения поступают сдвинутые импульсы тактового генератора, т. е. все установившееся в единичное состояние до появления на полюсе 14 разрешающего потенциала триггеры 10 будут установлсны в нулевое состояние выходным сигналом схем 8 совпадения.

Те же триггеры 10, которые установились в единичное состояние, с появлением сигнала на полюсе 14 останутся в единичном состоянии, так как будет снят разрешаюгций потенциал со входа схемы 8. Таким образом, состояния триггеров 10 моделей ветвей будут индицировать дерево длиннейших путей с корнем в начальной вершине. гю

25 зо

35 о

При решении задачи о кратчайшем пути разрешающий потенциал подается на вход 17 модели ветви, а запрещающий — на вход 16.

В этом случае, как только триггеры 10 и

11 одной из моделей ветвей, входящих в одну вершину графа, установятся в единичное состояние, на полгосе 14 появится разрешающий потенциал. Тем самы я будет снят разрешающий потенциал со входов схем совпадения б и 8, и триггеры 10 и 11 остальных моделей ветвей не установятся в единичное состояние. Таким образом, в этом случае находящиеся в единичном состоянии триггеры

10 моделей ветвей будут индицировать дерево кратчайших путей с корнем в начальной вершине.

Предмет изобретения

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

«И», подключенной вторым входом к шине управления решением задачи о длиннейшем пути; выход третьей схемы «И» соединен со входом инвертора, вьгход которого соединен с выходным полюсом модели ветви; единичный выход второго триггера соединен со входом четвертой схемы «И», подключенной вторым входом к шине управления решением задачи о кратчайшем пути, а выходом к одному из полюсов диода, другой полюс которого соединен с выходным полюсом модели ветви; выходной полюс модели ветви соединен со входом инвертор а, выход которого соединен со входами второй и пятой схем «И», причем выход второй схемы «И» подключен к индикаторному выходу модели ветви, а выход инвертора подключен к ее входному полюсу; второй вход пятой схемы «И» соединен с шиной тактового питания, а ее выход подключен к нулевому входу первого триггера.

305484

Корректор Т. A. Китаева

Редактор Ю. Полякова

Заказ 2511/12 Тираж 473 Подписное

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

Москва, Ж-35, Раушская наб., д. 4г5

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

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

Техред 3. Н. Тараненко

i > — И