Устройство для определения параметров графов

 

Изобретение относится к вычислительной технике и может быть использовано для нахождения параметров графов. Цель изобретения - расширение функциональных возможностей устройства за счет нахождения кратчайших путей, из начальной в конечную вершину графа. Поставленная цель достигается тем, что устройство содержит формирователь импульсов, с первого по третий регистры, с первого по третий ключи, первый элемент ИЛИ, со второго по шестой элементы ИЛИ, счетчик, схему сравнения, первый регистр , с первого по девятнадцатый элементы задержки, с первого по пятый блоки моделирования вершин.I ил. (Л 00 ю СП 4 QD С

СОЮЗ СОВЕТСКИХ

СОЦИАЛИСТИЧЕСКИХ

РЕСПУБЛИК

„„SU„„132549 цц 4 G 06 Р 15/20 ф Е

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

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

ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССР

Il0 ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ (21) 4031646/24-24 (22) 03.03.86 (46) 23.07.87. Бюл. Ф 27 (72) 10.М.Коптев, M.Õ.Îâ÷èííèêîâ, .В.И.Штолин и С.А.Жданов ,(53) 681 .325 (088. 8) (56) Авторское свидетельство СССР

У 717777, кл. G 06 Р 15/20, 1977.

Голованов О.Н. и др. Некоторые вопросы построения гибридных вычислителей. — В кн. Неоднородные вычислительные системы. Киев: Наукова думка, 1975, с.113 ° (54) УСТРОЙСТВО ДЛЯ ОПРЕДЕЛЕНИЯ ПАРА МЕТРОВ ГРАФОВ (57) Изобретение относится к вычислительной технике и может быть использовано для нахождения параметров графов. Цель изобретения — расширение функциональных возможностей устройства за счет нахождения кратчайших путей из начальной в конечную вершину графа. Поставленная цель достигается тем, что устройство содержит формирователь импульсов, с первого по третий регистры, с первого по третий ключи, первый элемент ИЛИ, со второго по шестой элементы ИЛИ, счетчик, схему сравнения, первый регистр, с первого по девятнадцатый элементы задержки, с первого по пятый блоки моделирования вершин.1 ил.

1325498 2

Изобретение относится к вычисли- вход триггера 13 и устанавливает его тельной технике и мажет быть исполь- в единичное состояние. Аналогично зовано для нахождения параметров се- перебрасывается в такое же состояние тевых структур, описываемых графами. триггер 13 модели 10, Сигналы с вы5

Цель изобретения — расширение ходов триггеров 13 поступают на вхофункциональных возможностей устрой- ды записи регистров 14 (которые осства эа счет нахождения кратчайших, таются в нулевом состоянии) и на вхопутей из начальной в конечную верши- ды элементов эадержки 9, 9, а ну графа. 10 также 9гь ° 9rA1 9rK моделей Beòâeé, На чертеже представлена функцио- исходящих иэ узлов Б и Г соответстнальная схема устройства. вени о.

Устройство содержит формирователь Первым, согласно условиям примера, 1 импульсов, с первого по третий ре- в узел В приходит импульс иэ узла Б. гистры 2Е, 2» 2, с первого по тре- 15 Пройдя через элемент ИЛИ 12, он устий ключй 3 „ 3, Зр, первый элемент танавливает в единичное состояние

ИЛИ 4, с второго по шестой элементы триггер 13, единичный сигнал с выИЛИ. 5E 5 8 56 5A 5, счетчик 6, хода которого поступает на вход эаписхему .7 сравнения, первый регистр 8, си регистра 14. В это время на Б-м с первого по девятнадцатый элементы 20 разрядном входе регистра 14 (т.е.вхозадержки 9 16, 9, 96, 9, 9 85, де, соответствующем узлу Б) еще при9, 9, 9 9, 9, 95К 9, сутствует сигнал, поступающий в узел

9де, 9gK, 9, 9дг, 91-, 9Г,. 9гв, с В из узла Б через элемент 9 запервого по пятый блоки I Q . I O I O держки, поскольку в устройстве эти

10 ° IOr моделирования вершин в о 25 элементы выдаютимпульсы достаточной я вершин, вход

11 наименьшего числа ветвей продолжительности, задержанные на эаS исходящих иэ кача ьного узла данное времяотносительно переднего и входящих в конечный узел, при этом Фронта перепада напряжения, поступаюкаждый блок моделирования вершин со- lllel"o c выхода триггера 13. Поэтому держит первый элемент ИЛИ 12, триг- 3Q регистр 14 модели 10 g запоминает 1 гер 13, регистр 14, ключи 15, второй в Б-м Разряде, что указывает по ка. элемент ИЛИ 16. кой ветви (в данном случае — по ветВ исходном статическом состоянии ви 9 ) пришел в узел В первый имрегистра 2, счетчик 6 и триггеры 13 пульс. Единичный потенциал с Б-го . обнулены, в регистр 8 занесено число 35 разрядного выхода регистра 14 постуМ, равное наименьшему иэ чисел Н и О, пает на управляющий вход ключа 15 где Н вЂ” число исходящих иэ начально- и открывает его.

Ф

ro узла ветвей, а Π— число входящих Затем в узел В поступает импульс в конечный узел ветвей. С помощью из угла Г через элемент 9 задержэлементов 9 задержки формируются ве- 40 ки однако он проходит лишь через личины задержки, пропорциональные ве- элемент ИЛИ l2, не оказывая влияния сам ветвей. Ключи 3 открыты единич- на триггер 13, находящийся в единич. ным, а. ключи 15 закрыты нулевым по- ном состоянии, и не эаписываясь в ретенциалами на их управляющих входах. гистр ввиду непоступления импульса

Работу устройства рассмотрим на 45 на его вход записи. примере графа с узлами А (начальный), В узел E первым приходит импульс

К (онечнь й), Б,В ° I ä,E (промежуточ- из Узла В, а в узел Л вЂ” импульс иэ ные) и величинами задержки 1,3,2,4, Узла Г; поэтому в модели 10 Е единич3,1,3,2,4,2,3,4 секунд в ветвях соот- .ный сигнал записывается в B-й разряд ветственно (А,Б),(А,Г),(Б,В),(Б,Е), 5п Регистра 14 а в модели 10 — в Г-й с

А-в -й (В, Г), (B,E), (B,Ä), (д, Г), (ДЕ), разряд регистра 14, при этом откры{е, к) 1 (д. К) э (Гф к), ваются соответствующие ключи 15.

После подачи пускового сигнала на Через 6 с импульс формирователя пусковой вход устройства формирова- 1, пройдя через элементы .задержки тель 1 выдает импульс, распространяю- 55 9 5, 95, 9 5Е, 9 е и модели 10 щийся по моделям 9 и 10 ветвей и уз- 10 и IOg, с выхода элемента 9 зайК за лов. Пройдя через элемент 9 за- держки поступает, во-первых,.через держки,.импульс поступает в узел Б, элемент ИЛИ 4 на вход счетчика 6,ко"де проходит через элемент ИЛИ 12 на торый увеличивает свое содержимое

5498 регистра 8, поэтому на инверсном выходе схемы 7 сравнения появляется нулевой потенциал, поступающий на управляющие входы ключей 3, которые закрываются. Тем самым содержимое регистра 2 не изменяется.

132 на 1, во-вторых, через элемент ИЛИ 5 на вход Е-го разряда регистра 2 в-третьих, через открытый ключ 3 — на вход записи регистра 2, который записывает 1 в E-й разряд. Кроме того с выхода ключа 3 импульс через элемент ИЛИ 16 моделй 10 поступает на информационные входы ключей 15, из которых, как указь»валось, открыт лишь ключ 15 . С его выхода импульс проходит, во-первых, через элемент

ИЛИ 5 на вход Д-ro разряда регистБ ра 2, где и записывается 1 ввиду поступления импульса на вход записи этого регистра с выхода ключа 3 (имE пульс на входе записи присутствует во время подачи единичных сигналов на все соответствующие разрядные входы регистра 2 ).

Далее импульс с выхода ключа 15> модели 1ОЕ проходит в узел В на вход элемента ИЛИ 16, с выхода которого импульс поступает на информационные входы ключей 15, из которых, как указывалось, QTKpblT JIHI»»b K»I»DR 1 5 5 е С

его выхода импульс проходит, во-первых, через элемент ИЛИ 55 на входы

Б-х разрядов всех регистров 2, но 1 записывается лишь в Б-й разряд регистра 2, так как только на его входе записи присутствует импульс. Во-вторых, импульс с выхода ключа 156 модели 1О поступает на вход элемента

ИЛИ 16 модели 10, но это значения не имеет, так как все ключи 15 в модели 105 закрыты.

Таким образом, через 6 с в регистре 2 Е единицы записываются в Б-й, В-й, Е-й разряды, указывая, что первый кратчайший путь из узла А в узел

К проходит через эти узлы. Ветви, через которые проходит этот путь, -.указывают 1, записанные в разрядах регистров 14 моделей 10, 10 11, IOE. Величина этого пути при необходимости ,определяется известным образом путем замера временного интервала между моментами появления импульса на выходе формирователя 1 и, элемента задержки

9екАналогично через 7 с в Г-й разряд регистра 2 записывается l, указывающая, что второй кратчайший путь проходит через узел Г. При этом при поступлении второго импульса на вход счетчика 6 его содержимое (код числа 2) становится равным содержимому

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

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

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

fg

f5

iQ

ЗО

5О

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

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

7 )32549 ключен к входу записи второго регистра и к седьмому входу четвертого бло- 15

25 моделирования вершин подключен к вто- 35

45

55 по третий, выход четвертого элемента ИЛИ подключен к третьим информационным входам регистров с первого по третий, выход шестого элемента

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

ИЛИ первого блока моделирования вершин, четвертый вход первого блока рому входу первого элемента ИЛИ первого блока моделирования вершин и к первому информационному входу регистра первого блока моделирования вершин, пятый вход первого блока моделирования вершин подключен к третьему входу первого элемента ИЛИ первого блока моделирования вершин и к второму информационному входу регистра первого блока моделирования вершин, выход триггера первого блока моделирования вершин подключен к входу записи регистра первого блока моделирования вершин и к первому выходу первого блока моделирования вершин, выходы первого и второго ключей первого блока моделирования вершин подключены соответственно к второму и третьему выходам первого блока мо делирования вершин, выход первого элемента ИЛИ первого блока моделирования вершин подключен к счетному входу триггера первого блока модели8 8 рования вершин, первый и второй выходы регистра первого блока моделирования вершин подключены к информа ционным входам соответствЕнно первого и второго ключей первого блока моделирования вершин, выход второго элемента ИЛИ первого блока моделирования вершин подключен к управляющим входам первого и второго ключей первого блока моделирования вершин,причем в пятом блоке моделирования вершин первый, второй и третий входы подключены соответственно к первому входу первого элемента ИЛИ пятого блока моделирования вершин, к первому входу второго элемента ИЛИ пятого блока моделирования вершин и к второму входу второго элемента ИЛИ пятого блока моделирования вершин,четвертый вход пятого блока моделирования вершин подключен к второму входу первого элемента ИЛИ пятого блока моделирования вершин и к первому информационному входу регистра пятого блока моделирования вершин, пятый вход пятого блока моделирования вершин подключен к третьему входу первого элемента ИЛИ пятого блока моделирования вершин и к второму информаЗ0 ционному входу регистра пятого блока моделирования вершин, шестой вход пятого блока моделирования вершин подключен к третьему входу второго элемента ИЛИ пятого блока моделирования вершин, первый и второй вьжоды пятого блока моделирования вершин подключены соответственно к выходам. первого и второго ключей пятого блока моделирования вершин, выход триггера пятого блока моделирования вершин подключен к входу записи регистра пятого блока моделирования вершин и к третьему выходу пятого блока моделирования вершин, выход первого элемента ИЛИ пятого блока моделирования вершин подключен к счетному входу триггера пятого блока моделирования вершин, первый и второй выходы регистра пятого блока моделирования вершин подключены к информа ционным входам соответственно первого и второго ключей пятого блока моделирования вершин, выход второго элемента ИЛИ пятого блока моделирования вершин подключен к управляющим входам первого и второго ключей пятого блока моделирования вершин, при этом второй и четвертый блоки модели"

1325498

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

ИЛИ второго блока моделирования вершин, четвертый вход второгб блока моделирования вершин подключен к первому входу первого элемента ИЛИ второго блока моделирования вершин и к первому информационному входу регистра второго блока моделирования вершин, пятый вход второго блока моделирования вершин подключен к второму информационному входу .регистра второго блока моделирования вершин и к второму входу первого элемента KIN второго блока моделирования вершин, шестой вход второго блока моделирования вершин подключен к третьему информационному входу регистра второго блока моделирования вершин и к третьему входу первого элемента. ИЛИ второго блока моделирования вершин, седьмой и восьмой входы второго блока моделирования верпан подключены соответс-..âåííî к четвертому входу второго элемента ИЛИ второго блока моделирования вершин и к входу записи регистра второго блока моделирования вершин, с первого по третий выходы второго блока моделирования вершин подключены соответственно к выходам соответственно с первого по третий ключей второго блока моделирования вершин, выход триггера второго блока моделирования вершин подключен к четвертому выходу второго блока моделирования вершин, выход первого элемента ИЛИ второго блока моделирования вершин подключен к счетному входу триггера второго блока моделирования вершин„ с перваго по третий выходы регистра второго блока моделирования вершин подключены соответственно к информационным входам ключей с первого Tro третий второго блока моделирования вершин, выход второго элемента ИЛИ второго блока моделирования вершин подключен к управляющим входам ключей с первого по третий второго блока моделирования вершин, причем в четвертом блоке моделирования вершин с. первого по третий входы подключены соответственно к входам с первого по третий втомоделирования вершин и к второму информационному входу регистра четвер15 того блока моделирования вершин, шестой вход четвертого блока моделирава-! ния вершин подключен к третьему вхо25

40

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

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

Редактор А.Ворович Техред И.Попович Корректор И Муска

3112/46 Тираж 672 Подписное

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

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

Заказ

Производственно-полиграфическое предприятие, r.Óæãîðoä, ул.Проектная, 4

11 . 132549 подключен к первому входу первого элемента ИЛИ третьего блока моделирования вершин и к первому информационному входу регистра третьего

5 блока моделирования вершин, шестой вход третьего блока моделирования вершин подключен к второму входу первого элемента ИЛИ третьего блока моделирования вершин и к второму информационному входу регистра третьего блока моделирования вершин, седьмой вход третьего блока моделирования вершин подключен к третьему входу первого элемента KIN третьего блока моделирования вершин и к третьему информационному входу регистра третьего блока моделирования вершин, восьмой вход третьего блока моделирования вершин подключен к четвертому входу первого элемента

ИЛИ третьего блока моделирования вершин и к четвертому информационному входу регистра третьего блока моделирования вершин, выход триггера 25

12 третьего блока моделирования вершин подключен к первому выходу третьего блока моделирования вершин и к входу записи регистра третьего блока моделирования вершин, выходы с второго по пятый третьего блока моделирования вершин подключены соответственно к выходам ключей с первого по четвертый третьего блока моделирования вершин, выход первого элемента ИЛИ третьего блока моделирования вершин подключен к счетному входу триггера третьего блока моделирования вершин, выходы с первого по четвертый регистра третьего блока моделирования вершин подключены к информационным входам ключей соответственно с первого по четвертый третьего блока моделирования вершин, выход второго элементЫ

ИЛИ третьего блока моделирования вершин подключен к управляющим входам ключей с первого по четвертый третьего блока моделирования вершин.