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

 

1. УСТРОЙСТВО ДЛЯ ОПРЕДЕЛЕНИЯ ХАРАКТЕРИСТИК СВЯЗНОСТИ ОРИЕНТИРОВАННОГО ГРАФА, содержащее первую матричную модель графа, состоящую из пхп формирователей дуг, по числу столбцов первой матричной модели графа первую группу п-входовых элементов ИЛИ, по числу строк первой матричной модели графа вторую группу п-входовых элементов ИЛИ, элемент п И-ИЛИ, вторую матричную модель графа, состоящую из пхп формирователейдуг , по числу столбцов второй матричной модели графа третью группу п-входовых элементов ИЛИ, по числу строк четвертую группу п-входовых элементов ИЛИ, группу из п элементов И, блок регистрации и блок управления, состоящий из двух дешифраторов, счетчика по mod п, двух триггеров, первого элемента И и генератора импульсов , выход которого соединен с первым входом первого элемента И и со. счетным входом счетчика по mod п, разрядные выходы которого соединены с разрядными входами первого дешифратора , первые выходы формирователей дуг каждор строки первой матричной модели графа соединены с одноименнь1ми входами п-входового элемента ИЛИ второй группы соответствующей строки, выходы п-входовых элементов ИЛИ второй группы подключены к первой группе входов элемента п И-ИЛИ, вторые входы формирователей дуг каждого столбца первой матричной модели графа соединены с одноименными входами п-входовых элементов ИЛИ первой группы соответствующего столбца, первые выходы формирователей дуг каждого столбца второй матричной модели графа подключены к одноименным входам п-входового элемента ИЛИ третьей группы, выходы п элементов И группы соединены с первой группой входов i блока регистрации, отличающееся тем, что, с целью рас (Л щирения его функциональных возможностей , в него введены п хп-входовый элемент ИЛИ, коммутатор, (п+1) групп из К элементов И, блок формирования последовательности BepinHH графа, а в блок управления введены элемент (п+1).И-ИЛИ, элемент 2И-ИЛИ, элесо 00 ел менты И, элементы ИЛИ, реверсивный счетчик, разрядные выходы которого соединены с первыми входами К элесо ментов И (п+1)-ой группы, с первой О) группой входов второго элемента И, с разрядными входами второго дешифратора , (п+О-е выходы которого подключены к первой группе входов блока формирования последовательности вершин графа и к первой группе входов элемента И-ИЛИ блока управления , выход которого соединен с нулевым входом первого триггера, единичный выход которого подключен к первому входу блока формирования последовательности вершин графа и к

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

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

РЕСПУБЛИК

„„SU„, 11335

4(51) G 06 F 15/20

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

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ (21) 3632491/24-24 (22) 05.08.83 (46) 07.01.85. Вюл. N - 1 (72) Г.А. Ерошко и Н.Г. Коробка (53) 681.333(088.8) (56) 1. Авторское свидетельство СССР

В 842842, кл. С 06 Р 7/122, 1981.

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

Р 991434, кл. G 06 F 15/20, 1981 (прототип). (54)(57) 1. УСТРОЙСТВО ДЛЯ ОПРЕДЕЛЕНИЯ ХАРАКТЕРИСТИК СВЯЗНОСТИ ОРИЕНТИРОВАННОГО ГРАФА, содержащее первую матричную модель графа, состоящую из п хи формирователей дуг, по числу столбцов первой матричной модели графа первую группу п-входовых элементов ИЛИ, по числу строк первой матричной модели графа вторую группу и-входовых элементов ИЛИ, элемент и И-ИЛИ, вторую матричную модель гра- фа, состоящую из и хи формирователейдуг, по числу столбцов второй матричной модели графа третью группу и-входовых элементов ИЛИ, по числу строк четвертую группу и-входовых элементов ИЛИ, группу из и элементов И, блок регистрации и блок управления, состоящий из двух дешифраторов, счетчика по mod n, двух триггеров, первого элемента И и генератора импульсов, выход которого соединен с первым входом первого элемента И и со счетным входом счетчика по mod и, разрядные выходы которого соединены с разрядными входами первого дешифратора, первые выходы формирователей дуг каждой строки первой матричной модели графа соединены с одноименными входами п-входового элемента ИЛИ второй группы соответствующей строки, выходы и-входовых элементов ИЛИ второй группы подключены к первой группе входов элемента и И-ИЛИ, вторые входы формирователей дуг каждого столбца первой матричной модели графа соединены с одноименными входами п-входовых элементов ИЛИ первой группы соответствующего столбца, первые выходы формирователей дуг каждого столбца второй матричной модели графа подключены к одноименным входам и-входового элемента ИЛИ третьей группы, выходы п элементов И группы соединены с первой группой входов блока регистрации, о т л и ч а ю— щ е е с я тем, что, с целью расширения его функциональных возможностей, в него введены п хи-входовый элемент ИЛИ, коммутатор, (и+1) групп из К элементов И, блок формирования последовательности вершин графа, а в блок управления введены элемент (и+1).И-ИЛИ, элемент 2И-ИЛИ, элементы И, элементы ИЛИ, реверсивный счетчик, разрядные выходы которого соединены с первыми входами К элементов И (и+1)-ой группы, с первой группой входов второго элемента И, с разрядными входами второго дешифратора, (и+1)-е выходы которого подключены к первой группе входов блока формирования последовательности вершин графа и к первой группе входов элемента И-ИЛИ блока управления, выход которого соединен с нулевым входом первого триггера, еди- ничный выход которого подключен к первому входу блока формирования последовательности вершин графа и к

3596

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

К элементов И (и+1)-й группы и к единичным входам первого и второго триггеров, единичный выход которого соединен с вторым входом блока формирования последовательности вершин графа, с первыми входами формирователей. дуг второй матричной модели графа, с вторым входом первого элемента И, с первым входом первого элемента И элемента 2И-ИЛИ и с первым входом шестого элемента И, выход которого подключен к вычитающему входу реверсивного счетчика, суммирующий вход которого соединен с выходом элемента

2И-ИЛИ, первый вход второго элемента

И которого соединен с вторым входом четвертого элемента И и подключен к инверсному выходу второго триггера,,соединенному с вторыми входами формирователей дуг второй матричной модели графа и с первыми входами К элементов И и групп, выход второго элемента ИЛИ подключен к второму входу шестого элемента И и к второму входу первого элемента И элемента 2И-ИЛИ, второй вход второго элемента И которого соединен с третьим входом шестого элемента И и подключен к (и+1)-у выходу первого дешифратора, и выходов которого соединены с второй группой входов блока формирования последовательности вершин графа, с первыми входами формирователей дуг одноименного столбца первой матричной модели графа и с третьими входами формирователей дуг одноименного столбца второй матричной модели графа, вторые выходы фор-. мирователей дуг каждого столбца второй матричной модели графа соединены с одноименным входом и-входового элемента ИЛИ четвертой группы, выходы которых подключены соответственно к второй группе входов элемента и

И-ИЛИ, к первой группе входов пятого элемента И и к первым входам и элементов И группы, вторые входы кото. рых объединены и соединены с выходом второго элемента И, подключенным к третьему входу четвертого элемента И, третий вход первого элемента И соединен с и-м выходом второго дешифратора, второй выход которого подключен к первому входу седьмого элемента И, выход которого соединен с входом счетчика по, mod и, с второго по (п+1)-й выходь второго дешифратора подключены к четвертым входам формирователей дуг предыдущей строки матричной модели графа и с информационными входами коммутатора, управляющий вход которого является управляющим входом устройства, выходы первой группы коммутатора подключены к второй группе входов пятого элемента

И и к входам третьей группы блока формирования последовательности вершин графа, выходы первой группы которого соединены с пятыми входами формирователей дуг соответствующей строки второй матричной мсдели графа, одноименные выходы втсрой группы блока формирования последовательности вершин графа подключены к вторым входам формирователей дуг одноименного столбца первой матричной модели графа, третьи выходы формирователей дуг первой матричной модели соединены соответственно с входами и хп-входового элемента ИЛИ, выход которого подключен к второму входу седьмого элемента И, к второй группе входов элемента (и+1)И-ИЛИ блока управления и к вторым входам К элементов И и групп, выход элемента и И-ИЛИ соединен с шестыми входами формирователей дуг кроме первой строки второй матричной модели графа, выхбды второй группы коммутатора подключены соответственно к третьим входам формирователей дуг одноименной строки первой матричной модели графа, выходы элементов ИЛИ третьей группы соединены с четвертыми входами формирователей дуг соответствующей строки первой матричной модели графа, выходы третьей группы блока формирования последовательности вершин графа соединены соответственно с третьими входами К элементов И и групп, выходы четвертой группы выходов блока формирования последовательности вершин графа подключены к входам второго элемента ИЛИ, выходы пятой группы блока формирования последователь3596

11З ности вершин графа соединены с группой входов третьего элемента И,. вторая группа входов второго элемента И объединена и является входом задания длины пути устройства, вход запуска генератора импульсов объеди-. нен с входом реверсивного счетчика и является входом запуска устройства, выходы второго дешифратора, кроме первого и (n+1)-го, соединены с седьмыми входами формирователей дуг одноименной строки, кроме первой, второй матричной модели графа, выходы элементов ИЛИ первой группы подключены к шестым входам формирователей дуг первой строки второй матричной модели графа, 2. Устройство по п.1, о т л и— ч а ю щ е е с я тем, что блок формирования последовательности вершин графа содержит п счетчиков по mod и, и дешифраторов, и элементов и И-ИЛИ, и элементов 2 п И-ИЛИ, выходы которых являются выходами второй группы блока, первым входом которого являются объединенные первые группы входов п элементов 2пИ-ИЛИ, вторые группы входов которых являются одноименными входами третьей группы блока, входами первой группы которого, кроме (n+1)-ro, являются одноименные входы третьей группы и элементов 2пИ-ИЛИ, входы четвертой группы которого соединены соответственно с первым и вторым выходами одноименных дешифраторов, третьи выходы которых подключены к первым входам и-ых элементов И одноименных элементов пИ вЂ И и являются выходами пятой группы блока, вторым входом которого являются объединенные входы первой группы и элементов и И-ИЛИ, входы второй группы которых являются соответствующими входами первой группы, кроме г".ервого, блока, выходы и элементов п И-ИЛИ соединены с входами одноименных счетчиков по шой и, и-е выходы которых являются выходами третьей группы блока и подключены к разрядным входам одноименных дешифраторов, четвертые входы которых соединены с входами (r-1)-ых элементов И одноименных п элементов пИ-ИЛИ, (и+1)-е выходы счетчиков по

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

3; Устройство по п.1, о т л и— ч а ю щ е е с я тем, что формирователь дуги первой матричной модели

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

4 . Устройство по п.1, о т л и— ч а ю щ е е с я тем, что формирователь дуги первой строки второй матричной модели графа содержит два элемента И и триггер, прямой вход которого является шестым входом формирователя, вторым и пятым входами которого являются соответственно первый и второй входы первого элемен" та И, третий вход которого объединен с первым входом второго элемента И и является четвертым входом формирователя, первым входом которо-, го является второй вход второго элемента И, третий вход которого соединен с четвертью входом первого элемента И и подключен к единичному выходу триггера, выходы первого и второго элементов И являются соответственно первым и вторым выходами формирователя, третий вход которого является пятым входом первого элемента И ..

5. Устройство по и. 1, о т л и— ч а ю щ е е с я тем, что формирователь дуги каждой строки, кроме первой, второй матричной модели графа содержит элементы И и триггер, единичный выход которого соединен с первыми входами первого и второго элементов И, выходы которых являются соответственно первым и вторым выходами формирователя, четвертым входом которого являются объединен- . ные вторые входы первого и второго элементов И, третий вход которого является первым входом формирователя, третьим и пятым входами которого являются соответственно третий и четвертый входы первого элемента И, пятый вход которого объединен с первым входом третьего элемента И и

1133596

45 является вторым входом формировате- " ля, шестым и седьмым входами которого являются соответственно второй и

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

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

Недостатком устройства являются ограниченные функциональные возможности»

Наиболее близким к изобретению по технической сущности является устройство для определения характеристик графа, содержащее блок управления, первый вход которого является входом устройства, первую матричную модель графа, состоящую из их п формирователей дуг, по числу столбцов первой матричной модели графа группу.п-входовых элементов ИЛИ, четыре группы из и элементов И, по числу строк первой матричной модели графа группу триггеров, вторую матричную третий входы третьего элемента И, выход которого соединен с прямым входом триггера. модель графа из и хп формирователей дуг, три группы из и элементов ИЛИ, и-входовой элемент ИЛИ, и-входовой элемент И-ИЛИ, два и-разрядных регистра, блок индикации, причем i-e выходы первой группы выходов блока управления соединены с первыми входами формирователей дуг соответственно i-ых строк первой и второй матричных моделей графа, i-e выходы (i=1, 2, ..., n) второй группы выходов блока управления соединены с вторыми входами формирователей дуг

j-ых столбцов (j 1 2, ..., n) пер15 вой матричной модели графа, первыми входами j-ых элементов И первой группы и управляющими входами х-ых (i=j) разрядов первого регистра, первый, второй и третий выходы блока управления соединены с блоком индикации, четвертый выход блока управления соединен с вторыми входами элементов И первой группы и с инверсными входами элементов И вто25 рой группы, пятый выход блока управления соединен с вторыми входами формирователей дуг второй матричной модели графа и через линию задержки с первыми входами элементов И второй группы, второй вход блока управления соединен с выходом п-входового элемента ИЛИ, j-e входы которого соединены с выходами j-ых элементов И первой группы, третьими входами формирователей дуг j-ых столбцов и четвертыми входами формирователей дуг i-ых строк (i=j) второй матричной модели графа, инверсные входы

i-ых элементов И первой группы соединены с единичными выходами i-ых (i=j) триггеров группы, единичные входы которых соединены с блоком индикации и с выходами соответствующих элементов

И третьей группы, первый вход которых соединен с выходами д-ых элементов ИЛИ.первой группы, второй вход— с выходами j-ых (j=i) элементов ИЛИ второй группы и с первыми входами з 11335

j-ых элементов И, четвертой группы, инверсные входы элементов И третьей группы соединены с вторыми входами элементов И четвертой группы и с вторым входом устройства, выходы элементов И четвертой группы соединены с блоком индикации, первые выходы формирователей дуг i-ых строк второй матричной модели графа соединены с входами j-ых (j=i) элементов ИЛИ 10 первой группы,. вторые выходы формирователей дуг j-ых столбцов второй матричной модели графа соединены с входами j-ых элементов ИЛИ второй группы, пятые входы формирователей дуг j-ых столбцов второй матричной модели графа соединены с блоком индикации, выходами i-ых (i=j) разрядов второго регистра и с первыми входами i-ых (i=j) элементов И и -вхо. дового элемента И-ИЛИ, вторые входы которых соединены с .выходами i-ых элементов ИЛИ третьей группы, входы которых соединены с первыми выходами формирователей дуг i-ых строк первой 2g матричной модели графа, вторые выходы формирователей дуг j-ых столбцов первой матричной модели графа соединены с входами соответственно

j-ых элементов ИЛИ четвертой грУппы, выходы которых соединены с первыми информационными входами i-ых (i=j) разрядов второго регистра, вторые информационные входы этих же разрядов соединены с выходами i-ых

35 элементов И второй группы, второй вход которых соединен с выходами i-ых разрядов первого регистра, иифор; мационные входы которых. соединены с выходом и-входового элемента .„И-ИЛИ (2 .

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

Целью изобретения является расширение функциональных возможностей за счет обеспечения поиска и формиро- 5О вания последовательности вершин, образующих минимальные пути из вершины Х» в вершину Х .

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

96 4 формирователей дуг, по числу столбцов первой матричной модели графа первую группу п-входовых элементов

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

ИПИ, группу из и элементов И, блок регистрации и блок управления, состоящий из п элеменгов И, блок регистрации и блок управления,. состоящий из двух дешифраторов, счетчика по шоо и, двух триггеров, первого элемента И и генератора ылульсов, выход которого соединен с е|вьп: входом первого элемента И и со счетным входом счетчика по шой и, раз-, :ядние выходы которого соединены разрядными входами первого дешифратора, первые выходы формирователей дуг каждой строки первой матричной модели графа соединены с одноименными входами и-входового элемента ИЛИ второй группы соответствующей строки, выходы и-входовых элементов ИЛИ второй группы подключены к первой группе входов элемента пИ-ИПИ, вторые входы формирователей дуг каждого столбца первой матричной модели графа соединены с одноименными входами п-входовых элементов ИЛИ перьой группы соответствующего столбца, первые выходы формирователей дуг каждого столбца второй матричной модег:.: графа подключены к одноименньм входам и-входового элемента ИЛИ третьей группы, выходы п элементов И группы соединены с первой группой входов блока регистрации, введены в -:;и-входовый элемент ИЛИ, коммута -ор, (n+I) групп из К элементов И,, блок формирования последовательности вершин графа, а в блок управления введены элемент (п+1)И-ИЛИ, элемент

2И-ИЛИ, элементы И, элементл ИЛИ, реверсивный счетчик, разрядные выходы которого соединены с первыми входами К элементов И (и+1)-ой группы, с первой группой входов второго элемента И, с разрядными входами второго дешифратора, (и+1)-е выходы которого подключены к первой группе входов блока формирования последовательности вершин графа и к первои груп1133596 пе входов элемента И-ИЛИ блока управления, выход которого соединен с нулевым входом первого триггера, единичйый выход которого подключен к первому входу блока формирования после довательности вершин графа и к входу третьего элемента И, выход которого соединен с первым входом первого эле- мента ИЛИ, выход которого подключен к нулевому входу второго триггера и к 1О первому входу генератора импульсов, .выход которого соединен с первым входом четвертого элемента И, выход которого подключен к второму входу первого элемента ИЛИ, третий вход которого соединен с выходом первого элемента И, выход пятого элемента И подключен к вторым входам К элементов И (п+1)-ой группы и к единичным входам первого и второго триггеров, 2р единичный выход которого соединен с вторым входом блока формирования последовательности вершин графа, с первыми входами формирователей дуг второй матричной модели графа, с вторым входом первого элемента И, с первым входом первого элемента И элемента 2И-ИЛИ и с первым входом шестого элемента И, выход которого подключен к вычитающему входу ревер30 сивного счетчика, суммирующий вход которого соединен с выходом элемента ,2И-ИЛИ, первый вход второго элемента :И которого соединен с вторым входом четвертого элемента И и подключен к инверсному выходу второго триггера, 35 соединенному с вторыми входами формирователей дуг второй матричной модели графа и с первыми входами I:. элементов И и групп, выход второго элемента ИЛИ подключен к второму вхо-"О ду шестого элемента И и к второму входу первого элемента И элемента

2И-ИЛИ, второй вход второго элемента

И которого соединен с третьим входом шестого элемента И и подключен к (и+1)-у выходу первого дешифратора, п выходов которого соединены с второй группой входов блока формирования последовательности. вершин графа, с первыми входами формирователей о дуг одноименного столбца первой матричной модели графа и с третьими входами формирователей дуг одноименного столбца второй матричной модели графа, вторые выходы формирователей дуг каждого столбца второй матричной . модели графа соединены с одноименным входом п-входового элемента ИЛИ чет-: вертой группы, выходы которых подключены соответственно к второй группе входов элемента пИ-ИЛИ, к первой группе входов пятого элемента И и к первым входам п элементов И группы, вторые входы которых объединены и соединены с выходом второго элемента И, подключенным к третьему входу четвертого элемента

И, третий вход первого элемента И соединен с п-м выходом второго дешифратора, второй выхоц которого подключен к первому входу седьмого элемента И, выход которого соединен с входом счетчика по тоби, с второго по (п+I) — и выходы второго дешифрато— ра подключены к четвертым входам формирователей дуг предыдущей строки матричной модели графа и с информационными входами коммутатора, управляющий .вход которого является управляющим входом устройства, выходы первой группы коммутатора подключены к второй группе входов пятого элемента И и к входам третьей группы блока формирования последовательности вершин графа, выходы первой группы которого соединены с пятыми входами формирователей дуг соответствующей строки второй матричной модели графа, одноименные выходы второй, группы блока формирования пос.чедовательности вершин графа подключены к вторым входам формирователей дуг одноименного столбца первой матричной модели графа, третьи выходы формирователей дуг первой матричной модели соединены соответственно с входами и х ивходового элемента ИЛИ, выход которого подключен к второму входу седьмого элемента И, к второй группе входов элемента (и+1) И-ИЛИ блока управления и к вторым входам К элементов

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

1133596 входами К элементов И и групп, выходы четвертой группы выходов блока формирования последовательности вер- шин графа .подключены к входам второго элемента ИЛИ, выходы пятой группы 5 блока формирования последовательности вершин графа соединены с группой входов третьего элемента И, вторая группа входов второго элемента И объединена и является входом задания длины пути устройства, вход запуска генератора импульсов объединен с входом реверсивного счетчика и является входом запуска устройства, выходы второго дешифратора, кроме первого и 15 (и+1)-ro, соединены с седьмыми входами формирователей дуг одноименной строки, кроме первой, второй матричной модели графа, выходы элементов

ИЛИ первой группы подключены к шес- 20 тым входам формирователей дуг первой строки второй матричной модели графа.

Блок формирования последовательности вершин графа содержит и счетчиков по mod и, и дешифраторов, и элементов и И-ИЛИ и и элементов

2 и И-ИЛИ, выходы которых являются выходами второй группы блока, первым входом которого являются объединенЗО ные первые группы входов и элементов

2п И-ИЛИ, вторые группы входов которых являются одноименными входами третьей группы блока, входами первой группы которого, кроме (п+1)-го, являются одноименные входы третьей группы и элементов 2п Н-ИЛИ, входы четвертой группы которого соединены соответственно с первым и вторым выходами одноименных дешифраторов, третьи выходы которых подключены к первым входам и-х элементов И одноименных элементов и И-ИЛИ и являются выходами пятой группы блока, вторым входом которого являются объединенные входы первой группы и элемен- 45 тов п И-ИЛИ, входы второй группы которых являются соответствующими входами первой группы, кроме первого, блока, выходы п элементов И-ИЛИ соединены с входами одноименных счетчи- о ков no mod n, и-е выходы которых являются выходами третьей группы блока и подключены к разрядным входам одноименных дешифраторов, четвертые входы которых соединены с входами (n-1)-ых элементов И одноименных и элементов и И-ИЛИ, (и+1)-е выходы счетчиков по шой и являются выходами четвертой группы блоков, выходами первой группы которого являются соответственно первый, второй и третий вы ходы дешифратора.

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

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

И являются соответственно первым и вторым выходами формирователя, третий вход которого является пятым входом первого элемента И.

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

10 теля, шестым и седьмым входами кото-, рого являются соответственно второй и третий входы третьего элемента И, выход которого соединен с прямым входом триггера. 5

На фиг. 1 представлена схема уст-. ройства длеко определения характеристик связности ориентированного графа; на фиг. 2 — блок управления устройства; на фиг. 3 — формирователь дуги 10 первой матричной модели графа; на фиг. 4 — формирователь дуги первой строки второй матричной модели графа; на фиг. 5 — формирователь дуги второй матричной модели графа строк с 15 второй по п-ю.

Устройство содержит матричную модель 1 графа, состоящую из п хи формирователей 1 — 1 д дуг, хранящую состояние исследуемого графа, матрич- ро ную модель 2 графа, содержащую и хи формирователей дуг 2«« -2 п, блок 3 управления, коммутатор 4, блок 5 формирования последовательности вершин графа, блок 6 регистрации, группу из 25 и элементов И 7 -7««,.(п+1) групп из

К элементов И 8«« -8,„, 8«« -8 +щ, rруппы п-входовых элементов ИЛИ 9«-9д, 10« — 10п, 11« -11п, 12«-12«1, элемент n g-ИЛИ 13, щ их п-.àÿoäoâîé элемент ИЛИ 14.

Блок 3 управления предназначен для управления работой устройства, содержит дешифраторы 15 и 16, счетчик по mod n 17, реверсивный счетчик

18, триггеры 19 и 20, элементы И 21 и 22, элемент {и+1)И-ИЛИ 23, элемент

2И-ИЛИ 24, элементы ИЛИ 25 и 26, эле.— менты И 27-31, генератор 32 импульсов.

Блок 5 формирования последовательности вершин содержит п счетчиков по

mod n 33«-33«,, п дешифраторов 34«-34<, и элементов и И-ИЛИ 35 «-35,1, и элементов 2И-ИЛИ 36 «-36«,.

Каждый формирователь 1„, -1„ дуги первой матричной модели графа содержит триггер 37, элементы И, 38-40.

Формирователи (2, -2 „) — (2„ 2„„) дуги второй матричной модели 5«, графа содержат триггер 41, элементы

И 42-44. Формирователи 2«« -2„„ дуги содержат триггер 41, элементы И 42, и 43, входы-выходы блоков 45-80.

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

Ф

Режим определения окрестности вершины Х радиусом R. Исходйое состояние: счетчики 17 и 21, группа счетчиков 33: -33 „, триггеры 19 и 20 в нулевом состоянии, матричная модель

1 графа хранит исходное состояние графа, по шине 46 подается код, соответствующий величине заданного радиуса R.

При зажатии пары клемм 4 « -4 „ и

44«-4 4< соответственно на коммутаторе 4, соответствуюшей номеру начальной вершины Х «, сигнал с нулевой шины дешифратора 16 разрешает считывание информации с i-ой строки формирователей дуг матрицы 1 и запись ее параллельным кодом через группу элементов ИЛИ 9 -9 в первую строку мат««1 рицы 2 по входу 76, т.е. в i=1 строке матрицы 2 зафиксирована окрестность вершины Х радиусом R=1.

При поступлений сигнала в блок 3 управления по входу 45 (сигнал качала работы) разрешается работа генератора 32 и устанавливается ревер,сивный счетчик 18 в единичное состояние. При этом на первый вход эле мента и И-ИЛИ 13 поступает информация параллельным кодой с i--1 строки матрицы 2 через группу элементов ИЛИ

12«-12 g (по выходу 74 формирователей дуг). Одновременно на второй вход элемента и И-ИЛИ 13 поступает информация параллельным кодом последовательно с j=1,2, ..., п столбцов мат.рицы 1 через группу элементов .ИЛИ 10 -10 .Это достигается путем выда- . чи i-х (i=l, ..., n) импульсов генератором через счетчик 17 и дешифратор 15.

Результат дизьюнкции логического произведения i=1 строки матрицы 2 на

j-e столбцы матрицы 1 записываются в триггеры формирователей дуг второй строки соответственно j-ых столбцов матрицы 2 по информационному входу

80 через элемент И 44. Таким образом, в i=2 строке матрицы 2 сформирована окрестность вершины X радиусом R=2.

При поступлении (и+1)-го сигнала от генератора 32 счет «ик no mod п 17 устанавливается в нулевое состояние и сигнал с выходной нулевой шины дешифратора поступает на суммирующий вход реверсивного счетчика 18, увеличивая его состояние на единицу. При

i=2 шина дешифратора 16 возбуждает на считывание информацию i=2 строки матрицы 2, информация поступает параллельным кодом через группу эле11 113359 ментов ИЛИ 12 † 1 на первые входы элемента и И-. ИЛИ 13. При поступлении очередных импульсов от генератора 32 на счетчик 17 от i-х шин дешифратора 15 поступают управляющие сигналы на считывание информации параллельным кодом последовательно с j-x столбцов матрицы 1 через группу элементов ИЛИ 10 † и на вторые входы элемента п И вЂ И 13. В результате 10 работы элемента п И-ИЛИ 13 формируется окрестность вершины Х радиусом

R=3 и записывается в i=3 строку.

При появлении сигнала на выходе элемента И 21 на блок 6 регистрации выдается информация i-ой (i=R) строки рабочей матрицы через группу элементов И 7 — ° . Наличие сигналов на выходах j-ых элементов И 7 -7 указывает на наличие связи между вершиной Х и j-ми вершинами исследуемого графа.

Сигнал с выхода элемента И 21 через элементы И 29, ИЛИ 26 блокирует работу генератора 32, работа уст- 25 ройства в данном режиме прекращается.

Режим определения минимального пути из вершины Х< в вершину Х . Исходное состояние: счетчики 17 и 18, группа счетчиков 331-33, триггеры

19 и 20 в нулевом состоянии, матричная модель 1 графа хранит исходное состояние графа, по управляющей шине 60 подан высокий потенциал.

При зажатии пары клемм на коммутаторе 4 4 <-4 д и 441 -4А„, соответствующей вершине Х, и поступлении сигнала начала работы по входу 1 блока управления на генератор 32 импульсов формируется матрица 2 аналогично описанному выше, т.е. формируются окрестности вершины Х

Одновременно зажимается пара клемм

41< -4 1п и 421 -4 2ц на коммутаторе 4, соответствующая вершине Х . По входу 45

571-57 блока управления йа вход

0 элемента И 22 подается и-разрядный код по сигналу от шины 60 через зажатую клемму Х2. На второй вход элемента И 22 подается информация последо- 50 вательно e i-х (i=1 ..., и) строк матрицы 2 параллельным кодом по входам 58 -58 блока управления. При появлении сигнала с выхода элемента

И 22 (факт появления минимального 55 пути из вершины Х в вершину Х ) триггеры 19 и 20 устанавливаются в единичное состояние, этим же сигна6 12 лом по выходу 49 блока управления разрешается выдача содержимого счет. чика.18 (минимальная длина пути +, ) на блок 6 регистрации через группу элементов И З д,,) < — 81„, )„.

Высокий потенциал с выхода триггера 19 по выходу 50 блока управления через группу элементов 2 и И-ИЛИ 36>36 возбуждает на считывание по входу 65 формирователя дуги 1-й столбец матрицы 1, соответствующий номеру вершины Х (т.е. j X2). Это достигается при совпадении сигналов от шины 60 через зажатую клемму X, от триггера 19 и от i-й шины дешифратора 16 (=?, „ ).

Одновременно на вычитающий вход реверсивного счетчика через элемент

И 30 поступает сигнал с единичного выхода триггера 30 и в момент, когда на нулевой шине дешифратора 15 будет высокий потенциал-, уменьшает его состояние на единицу. На (i-1)-й шине дешифратора 16 высокий потенциал. При поступлении очередных сигналов с генератора 32 импульсов на счетчик 17 íà j-x sa>xi ax (j=1, 2, ..., n, О) дешифратора 15 возникают сигналы, которые последовательно считывают по выходу 78 содержимое триггеров формирователей дуг (i-1)-ой строки матрицы 2 через группу элементов ИЛИ 111 †1. Сигнал, возникающий на выходе j-ro элемента ИЛИ

11q-11,, возбуждает на считывание

i-ю (i=j) строку матрицы 1 по выходу 70. В результате наложения j=X> столбца и i-ой строки рабочей матрицы анализируется содержимое триггера 37 и через элемент И 38 по входу 64 формирователя дуги матрицы 1 определяется наличие входящей связи в вершину Х . Если связь обнаружена (сигнал на выходе и хп-входового элемента ИЛИ 14), счетчик 17 устанавливается в нулевое состояние через элемент

И 31 но входу 52 блока управления, а триггер 19 через элемент (п+1)

И-ИЛИ 23 устанавливается в нулевое состояние. Одновременно с анализом входящей связи фиксируется номер вершины, составляющей входящую связь.

Это достигается путем подсчета количества импульсов (i-1)-ым счетчиком группы 331-33>, которые поступают на счетньп вход через (i-1)-й элемент и И-ИЛИ :руппы 351-35, на входы которых сигналы поступают от де13 »335 шифратора 15 при совпадении управляющих сигналов от (i-I)-ой шины дешифратора 16, с единичного выхода триггера 20 и f-ых выходов (i-1)-ro дешифратора группы 341-34 . Если связь обнаружена (сигнал с выхода элемента ИЛИ il4) счетчик 17 через элеб мент И 31 устанавливается в нуль, На ,вычитающкй вход реверсивного счетчиа снова поступает сигнал через эле- 10 мент И 30, уменьшая его состояние на ,единицу и возбуждая на считывание (i-2)-ю шину дешифратора 16. При этом через элементы 2п И-ИЛИ 36 -36 вози буждается по входу 65 формирователя дуги столбец матрицы 1, номер которого содержит (i-1)-й счетчик группы

331-33,1, Это достигается путем пода- . чи сигйала с f-ro выхода (i-1)-го дешифратора группы 34 -34п на элемен- gp ты 2 п И-ИЛИ 361-36П Вход -щую связь в новую вершину обнаруживают путем подачи импульсов на счетчик 17 и через дешифратор 15 считывают информацию с (i-2)-й строки матрицы 2.

Сигнал на выходе j-ro элемента ИЛИ

12 †1 определяет номер возбуждаемой строки матрицы 1. Формирование номеров вершин, входящих в минимальный путь, заканчивается, когда на первой шине дешифратора 16 (выход 56 блока управления) имеется высокий потенциал и придет сигнал от и х пвходового элемента ИЛИ 14, При этом на блок 6 регистрации через группы элементов (8 -8 „„) — (8„, -8«) вы35 водится содержимое счетчиков 33 -33, т.е. номера вершин, составляющих минимальный путь из вершины Х в вершину Х, Возможен минимальный путь не один, Дальнейший поиск следующего о минимального пути осуществляется следующим образом. Высокий потенциал с первой шины дешифратора 16 снимает сигнал установки счетчика в нуль.

Это достигается путем подачи потен-. циала с первой шины дешифратора 16 на инверсный вход элемента И 31.

1При поступлении очередных импульсов с генератора 32 на счетчик 17 дешифратор 15 продолжает подключать на считывание j-e элементы первой стро. ки матрицы 2 по входу 77 формирователя дуги. В результате этого возникший сигнал на выходе j-го элемента

ИЛИ груп 121-12п од люча HR 55 считывание (i=j)-ю строку матрицы 1, Одновременно счетчик 31 подсчитывает дальше количество импульсов, и

96 14 если связь обнаружится (сигнал от элемента ИЛИ 14), на блок регистрации через группы элементов (8 8 )—

41 4К (8> -8, „) фиксируются вершины, образующие следующий минимальный путь, При достижении счетчиком 33 состояния и очередной сигнал от схемы 351 устанавливает его в нулевое состояние, при этом на управляющем выходе счетчика 331 появляется сигнал (сигнал установки счетчика в нулевое .состояние), который через элементы

ИЛИ 25, 2 И-ИЛИ 24 поступает на суммирующий вход реверсивного счетчика

18, увеличивая его состояние на единицу. Возбуждается вторая шина дешифратора 16 (i-2). При эгом через эле-. менты 2п И-ИЛИ 36 -36 возбуждается

t1 столбец рабочей матрицы, номер которого содержит счетчик 35 группы.

С поступлением очередных импульсов на счетчик 17 дешифратор l5 возбуждает последовательно элементы i=2 строки матрицы 2, начиная с элемента,. который не заблокирован дешифратором 34, т.е. с (j+m)-ro элемен— та, где ш — содержимое счетчика 34 .

Это достигается путем коммутации выходов i-ых дешифратороы 34,,-34 с входами i-ых элементов п И-ИЛИ 351—

35, a именно нулевой выход дешифратора (сигнал на нем) разрешает прохождение первого сигнала, первый выход — прохождение второго сигнала, m-й .выход — прохождение (j+m) — ro сигнала и т.д. Через группу элем нтов ИЛИ 11 11, начиная с (j+m), определяется номер «озбуждаемой строки матрицы 1 и, если связь обнаруживается, дальнейший поиск вершин проводится аналогично описанному выше. Если связи нет, при переходе счетчика 34, из состояния и в нулевое на управляющем выходе счетчи ".а

34, появляется сигнал, который через элементы ИЛИ 25, 2И-ИЛИ 24 поступает на суммирующий вход реверсивного счетчика. 18, увеличив его состояние на единицу, и дальнейший поиск осуществляется аналогично. Поиск прекра.щается, когда все счетчкки 33 1-33 g установятся в исходное нулевое состояние. Тогда сигнал с нулевых шин дешифраторов 34 -34 при отсутствии

l сигнала с единичного выхода триггера 19 через элемент ИЛИ 26 блокирует работу генератора 32 и устанавливает триггер 20 в исходное нулевое сосТоНННВ и работа устройства прекраяк.- Й ..А РР бб, 4647 б7,:.5+ Рб, б8„

Фиг.!

1 "1 11 щается. Если пути иэ вершины Х< в вершину Х2 не существует, появляется сигнал с выхода элемента И 28,через элемент ИЛИ 26 блокируется работа генератора 32 и работа устройства прекращается.

Предлагаемое устройство позволя- ет оперативно проводить исследова33596 16 ния характеристик связности ориентированного графа, а именно определять ( окрестности i-ой вершины радиуса R минимальные пути из вершины Х 4в вершину Х,7, фиксируя при этом ,последовательность вершин, входящих в путь, и длину этого пути.

1133596

У -Х7» руу

Составитель Н. Коробка

Текред И.Гергель Корректор С. Шекмар

Редактор Т. Кугрышева

Филиал ППП "Патент", г. Ужгород, ул. Проектная, 4 Заказ 9948/40 Тираж 710 Подписное

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

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