Устройство для определения характеристик связности ориентированного графа Советский патент 1985 года по МПК G06F15/173 

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

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

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

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

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

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

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

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

1133596

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

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

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

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

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

2

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

.Группы, третьими входами формирователей дуг j-ых столбцов и четвертыми входами формирователей дуг i-ых строк () второй матричной модели графа, инверсные входы 1-ых элементов И перЕюй группы соединены с единичными вьпсодами 1-ых ( триггеров группы, единичные входы которых соединены с блоком индикации и с выходами соответствующих элементов И тр етьей группы, первый вход которых соединен с выход 1ми 1-ых элементов ШШ.цервой группы, второй .вход с выходами j-ых () элементов ИЛИ второй группы и с первыми входами j-ых элементов И четвертой группы, . инйерсные входы элементов И третьей группы соединены с вторыми входами элементов И четвертой группы и с вторым входом устройства, выходы эле ментов И четвертой группы соединены с блоком индикации, первые выходы формирователей дуг i-ых строк второй матричной модели графа соединены с входами j-ых () элементов ИЛИ первой группы, .вторые выходы формирователей дуг j-ых столбцов второй матричной модели графа соединены с входами j-ых элементов РШИ второй группы, пятые входы формирователей дуг j-ых столбцов второй матричной Q модели графа соединены с блоком индикации, выходами i-ых () разрядов второго регистра и с первыми входами i-ых () элементов И п-вх дового элемента И-ИЛИ, вторые входы которых соединены с .выходами i-ых элементов ИЛИ третьей группы, входы которых соединены с первыми выходам формирователей дуг i-ых строк перво матричной модели графа, вторые выходы формирователей дуг j-ьгх столбцов первой матричной модели графа соединены с входами соответственно j-ых элементов ИЛИ четвертой грУппы, выходы которых соединены с первыми информационными входами i-ых () разрядов второго регистра, вторые информационные входы этих же разрядов соединены с выходами i-ых элементов И второй группы, второй вход которых соединен с выходами . i-ых разрядов первого регистра, инф мационные входы которых соединены с выходом п-входового элемента ,И-ИЛИ .2. Известное устройство по:зволяет определять окрестности вершин графа определенного радиуса, но не обеспе ,чиваёт поиск и формирование последевательности вершин, образующих мини мальные пути. Целью изобретения является расши рение функциональных возможностей з счет обеспечения поиска и формирования последовательности вершин, образующих минимальные пути из верщины X. в вершину Х. Поставленная цель достигается те ,что в устройство для определения ха рактеристик связности ориентированн го графа, содержащее первую матричную модель графа, состоящую Из пхп формирователей дуг, по числу столбцов первой матричной модели графа первую группу п-входовьгх элементов ИЛИ, по числу Строк первой матричной модели графа вторую группу п-входовых элементов ИЛИ, элемент пИ-ИЛИ, вторую матричную модель графа, состоящую из пXп формирователей дуг, по числу столбцов второй матричной модели графа третью группу п-входо- вых элементов ИЛИ, по числу строк четвертую группу п-вхбдовых элементов ШШ, группу из п элементов И, блок регистрации и блок управления, состоящий из п элементов И, блок регистрации и блок управленияS состоящий из двух дешифраторов, счетчика по mod п, двух триггеров, первого элемента И и генератора импульсов, выход которого соединен с первык входом первого элемента И и со счетным входом счетчика по mod п, разрядные выходы которого соединены с разрядньми входами первого дешифратора, первые.выходы формирователей дуг каждой строки первой матричной ioдeли графа соединены с одно1да енными входами п-входового элемента ИЛН второй группы соответствующей строки, выходы п-входовых элементов РШИ второй группы подключены к первой группе входов элемента пИ-ШШ, вторые входы формирователей дуг каждого столбца первой матричной модели графа. соединены с одноименными входами п-входовых элементов ИЛИ первой группы соответствующего столбца, первые выходы формирователей дуг каждохо столбца второй матричной модели графа подключены к одноименным входам п-входового элемента ИЛИ третьей группы, выходы п элементов И группы соединены с первой группой входов блока регистрации, введены п х п--входовый элементИЛИ, коммутатор, (п-ь1) групп из К элементов И,, блок формирования последовательности вершин графа, а в блок управления введены элемент (п+1)И-ИЛИ, элемент 2И-ИЛИ, элементы И, элементы ИПИ, реверсивный счетчик, разрядные выходы которого соединены с первыми входами К элементов И (п+1)-ой группы, с первой группой входов второго элемента И, с разрядными входами второго дешифратора, (.li+D-e выхо,цы которого подключены к первой группе входов блока формирования последовательности вершин графа и к первой групJ1пе входов элемента И-ИЛИ блока упра ления, выход которого соединен с нул вым входом первого триггера, единичный выход которого подключен к первому входу блока формирования последовательности вершин графа и к вход третьего элемента И, выход которого соединен с первым входом первого эле мента ИЛИ, выход которого подключен нулевому входу второго триггера и к первому входу генератора импульсов, выход которого соединен с первым входом четвертого элемента И, выход которого подключен к второму входу первого элемента ИЛИ, третий вход которого соединен с выходом первого элемента И, выход пятого элемента И подключен к вторым входам К элементов И (ii+1)-oft группы и к единичным входам первого и второго триггеров, единичный выход которого соединен с вторым входом блока формирования последовательн остивершин графа, с первыми входами формирователей дуг второй матричной модели графа, с вторым входом первого элемента И, с первым входом первого элемента И элемента 2И-ИЛИ и с первым входом шестого элемента И, выход которого подключен к вычитающему входу реверсивного счетчика, суммирующий вход которого соединен с выходом элемента ,2И-ИЛИ, первый вход второго элемента И которого соединен с вторым входом четвертого элемента И и подключен к инверсному выходу второго триггера, соединенному с вторыми входами формирователей дуг второй матричной модели графа и с первыми входами К элементов И п групп, выход второго элемента ИЛИ подключен к второму вхо ду шестого элемента И и к второму входу первого элемента И элемента 2И-ИЛИ, второй вход второго элемента И которого соединен с третьим входом шестого элемента И и подключен к (п+1)-у выходу первого дешифратора, п выходов которого соединены с второй группой входов блока формирования последовательности вершин графа, с первыми входами формирователей дуг одноименного столбца первой матричной модели графа и с третьими вхо дами формирователей дуг одноименного столбца второй матричной модели графа, вторые выходы формирователей дуг каждого столбца второй матричной модели графа соединены с одноименным входом п-входового элемента ИЛИ чет-. 6 вертой группы, выходы которых подключены соответственно к второй входов элемента пИ-1-ШИ, к первой; группе входов пятого элемента И и к первым входам п элементов И группы, вторые в-ходы которых объединены и соединены с выходом второго элемента И, подключенным к третьему входу четвертого элемента И, третий вход первого элемента И соединен с п-м выходом второго дешифратора, второй выход которого подключен к первому входу седьмого элемента И, выход которого соединен с входом счетчика по modп, с второго по (п+1)-й выходы второго дешифратора подключены к четвертым входам формирователей дуг предыдущей строки матричной модели графа и с информационными входами KOMiviyTaTopa, управляющий .вход которого является управляющим входом устройства, выходы первой группы коммутатора подключены к второй группе входов пятого элемента И и к входам третьей группы блока формирования последовательности вершин Графа, выходы первой группы которого соединены с пятыми входами формирователей дуг соответствующей . строки второй матричной модели графа, одноименные выходы второй, группы блока формирования последовательности вершин графа подключены к вторым входам формирователей дуг одноименного столбца первой матричной модели графа, третьи выходы формирователей дуг первой матричной модели соеди- , нены соответственно с входами п х пвходового элемента ИЛИ, выход которого подключен к второму входу седьмого элемента И, к второй группе входов элемента (п+1) И-ИЛИ блока управления и к вторым входам К элементов И п групп, выход элемента п И-ИЛИ соединен с шестыми входами формирователей дуг кроме первой строки второй матричной модели графа, выходы второй группы коммутатора подключены соответственно к третьим входам формирователей дуг одноименной строки первой матричной модели графа, выходы элементов ИЛИ третьей группы соединены с четвертыми входами формирователей дуг соответствующей строки первой матричной модели графа, выходы ретьей группы блока формирования оследовательности вершин графа соединены соответственно с третьими входами К элементов И п групп, выходы четвертой группы выходов блока формирования последовательности вершин графа подключены к входам второго элемента ИЛИ, выходы пятой группы блока формирования последовательности вершин графа соединены с группой входов третьего элемента И, вторая группа входов второго элемента И объединена и является входом задания длины пути устройства, вход запуска генератора импульсов об-ьединен с входом реверсивного счетчика и является входом запуска устройства, выходы второго дешифратора, кроме первого и (п+1)-го, соединены с седьмыми входа ми формирователей дуг одноименной строки, кроме первой, второй матричной модели графа, выходы элементов ИЛИ первой группы подключены к шестым входам формирователей дуг первой строки второй матричной моде.ли графа Блок формирования последовательности вершин графа содержит п счетчи ков по modп, п дешифраторов, п элементов п И-ИЛИ и п элементов 2 п И-1ШИ, выходы которых являются выходами второй группы блока, первым входом которого являются объединенные первые г зуппы входов п элементов 2пИ-ИЛИ, вторые группы входов которых являются одноименными входами третьей группы блока, входами первой группы которого, кроме (п+1)-го, являются одноименные входы третьей группы п элементов 2пИ-ИЛИ, входы четвертой группы которого соединены соответственно с первым и вторым выходами одноименных дешифраторов, третьи выходы которых подключены к первым входам п-х элементов И одноименных элементов п И-ИЛИ и являются выходами пятой группы блока, вторым входом которого являются объединенные входы первой группы п элементов п И-ИЛИ, входы второй группы которых являются соответствующими входами первой группы, кроме первого, блока, выходы п элементов И-ИЛИ соединены с входами одноименных счетчиков по modn, п-е выходы которых являются выходами третьей.группы блока и подключены к разрядным входам одно именных дешифраторов, четвертые входы которых соединены с входами (п-1)-ых элементов И одноименных п элементов пИ-ИЛИ, (п+1)-е выходы сче чиков по mod п являются выходами чет- вертой группы блоков, выходами первой группы которого являются соответственно первьй, второй и третий выходы дешифратора. Формирователь дуги первой матричной модели графа содержит три элемента И и триггер, единичный выход которого соединен с первыми входами элементов И, второй и третий входы первого элемента И являются соответственно вторым и четвертым входами формирователя, первым и третьим входами которого являются вторые входы соответственно второго и третьего элементов И, выходы которых являются соответственно первым и вторым выходами формирователя, третьим выходом которого является выход первого элемента И. Формирователь дуги первой строки второй матричной -модели графа содержит два элемента.И и триггер, прямой вход которого является шестым входом формирователя, вторым и пятым входами которого являются соответственно первый и второй входы первого элемента И, третий вход которого объединен с первым входом второго элемента И и является 4viTвертым входом формирователя, первым входом которого является, второй вход второго элемента И, третий вход которого соединен с четвертым входом первого элемента И, и подкЛючен к единичному выходу триггера, выходы первого и второго элементов И являются соответственно первым и вторым выходами формирователя, третий вход которого является пятым входом первого элемента И. Формирователь дуги каждой строки, кроме первой, второй матричной модели графа содержит элементы И и триггер, единичный выход которого соединен с первыми входами первого и второго элементЬв И, выходы которых являются соответственно первым и вторым выходами формирователя, четвертым входом которого являются объединенные вторые входы первого и второго элементов И, третий вход которого является первьм входом формирователя, третьим и пятым входами которого являются соответственно третий и четвертый входы первого элемента И, пятый вход которого объединен с первым входом третьего элемента И и является вторьм входом формирователя, шестым и седьмым входами которого являются соответственно второй и третий входы третьего элемента И, выход которого соединен с прямым вхо дом триггера. На фиг. 1 представлена схема уст-г ройства дл«) определения характеристи связности ориентированного графа; на фиг 2 - блок управления устройст ва; на фиг 3 - формирователь дуги первой матричной модели графа; на фиг. 4 - формирователь дуги первой строки второй матричной модели графа на фиг,. 5 - формирователь дуги второй матричной модели графа строк с второй по п-ю. Устройство содержит матричную модель 1 графа, состоящую из п х п формирователей 1 - 1 ДУ хранящую состояние исследуемого графа, матрич ную модель 2 графа, содержащую пхп формирователей дуг , блок 3 управления, коммутатор 4, блок 5 фор мирования последовательности вершин графа, блок 6 регистрации, группу из п элементов И 7(-7,. (п+1) групп из К элементов И ,| , ..., 9 группы п-вхо довых элементов ИЛИ , 10;,10п, , , элемент п Ji-ШШ 13 п X п-зходовой элемент 1-ШИ 14. Блок 3 управления предназначен для управления работой устройства,, содержит дешифраторы 15 и 16, счетчик по mod п 17, реверсивный счетчик 18, триггеры 19 и 20, эглементы И 21 и 22, элемент (п+1)И-ИЖ 23, элемент 2И-Ш1И 24, элементы Ш1И 25 и 26, эле менты И 27-31, генератор 32 импульсов . Блок 5 формирования последователь ности вершин содержит п счетчиков по mod п 33.1-ЗЗп 5 II дешифраторов 341-34., п элемен ов пИ-ШШ35,-35,, п элементов 2И-Ш1И 36 ,-36. Каждый формирователь 1 первой матричной модели графа содержит триггер 37, элементы И, 38-40. Формирователи (224-2) () дуги второй матричной модели графа содержат триггер 41j элементы И 42-44, Формирователи 2 2 дуги содержат триггер 41, элементы И 42 , и 43, входы-выходы блоков 45-80. - Устройство работает следующим об„ разом. Режим определения окрестности вер шины Xj радиусом R Исходйое состоя11 , 610 ние: счетчики 17 и 21, группа счетчиков , -приггеры 19 и 20 в нулевом состоянии, матричная модель 1 графа хранит исходное состояние графа, по шине 46 подается код, соответствующий величине заданного радиуса R. При зажатии пары клемм 4,, Яп соответственно на коммутаторе 4, соответствующей номеру начальной вершины Х, сигнал с нулевой шины дешифратора 16 разрешает считывание информации с 1-ой строки формирователей дуг матрицы 1 и запись ее параллельным кодом через группу элементов ИЛИ 9jj-9« в первую строку матрицы 2 по входу 76, т.е. в строке матрицы 2 зафиксирована окрестность вершины X, радиусом , При поступлений сигнала в блок 3 управления по входу 45 (сигнал начала работы) разрешается работа генератора 32 и устанавливается ревер,сивный счетчик 18 в единичное состояние. При этом на первый вход элемента пИ-Ш1И13 поступает информация параллельнымкодо с строки матрицы 2 через группу элементов ИЛИ , (по выходу 74 формирователей дуг). Одновременно на второй вход элемента п И-ИЛИ 1 3 поступает информация параллельным кодом последовательно с ,2, ..., п столбцов матрицы 1 через группу элементов -ШШ ,.Это достигается путем выдачи i-x ( , ..., n) импульсов генератором через счетчик 17 и дешифратор 15. Результат дизъюнкции логического произведения строки матрицы 2 на j-e столбцы матрицы 1 записываются в триггеры формирователей дуг второй соответственно j-ых столбцов 2 по информационному входу 80 через элемент И 44. Таким образом, в строке матрицы 2 сформирована окрестность вершины X, радиусом . При поступлении (rn-l)-ro сигнала от генератора 32 по mod п 1 7 устанавливается в нулевое состояние и сигнал с выходной нулевой шины дешифратора поступает на суммирующий вход реверсивного счетчика 18, увели«f ° состояние на единицу. При шина дешифратора 16 возбуждает .« л на считывание информацию матрицы 2, информация поступает параллельным кодом через группу элементов ИЛИ на первые входы элемента п И-ИЛИ 13. При поступлении очередных импульсов от генератора 32 на счетчик 17 от i-x шин дешифратора 15 поступают управляющие сигналы на считывание информации параллельным кодом последовательно с j-x столбцов матрицы 1 через группу элементов ИЛИ 10;|-10f Ha вторые входы элемента пИ-ИПИ 13. В результате работы элемента п И-ИЛИ 13 формируется окрестность вершины Х радиусом и записывается в строку. При появлении сигнала на выходе элемента И 21 на блок 6 регистрации выдается информация i-ой () строки рабочей матрицы через группу элементов И 7. -7f|, Наличие сигналов на выходах j-ых элементов И указывает на наличие связи между вершиной X;) и j-ми вершинами исследуемого графа. Сигнал с выхода элемента И 21 через элементы И 29, ИЛИ 26 блокирует работу генератора 32, работа устройства в данном режиме прекращается Режим определения минимального пути из вершины Х в вершину Хл. Исходное состояние: счетчики 17 и 18, группа счетчиков , триггеры 19 и 20 в нулевом состоянии, матричная модель 1 графа хранит исходное Iсостояние графа, по управляющей шине 60 подан высокий потенциал. При зажатии пары клемм на коммутаторе 4 ,r) и (-Адп соответствующей вершине Х, и поступлении сигнала начала работы по входу 1 бло ка управления на генератор 32 импульсов формируется матрица 2 аналогично описанному выше, т.е. формируются окрестности вершины X,. Одновременно зажимается пара клем п .2п коммутаторе 4, соответствующая вершине X. По входу блока управления на вход элемента И 22 подается п-разрядный код по сигналу от шины 60 через зажа тую клемму Хп. На второй вход элемен та И 22 подается информация последовательно с i-x (, ..., n) строк матрицы 2 параллельным кодом по входам 58j|-58p блока управления. При по явлении сигнала с выхода элемента И 22 (факт появления минимального пути из вершины Хл в вершину Хл) , триггеры 19 и 20 устанавливаются в единичное состояние, этим же сигналом по выходу 49 блока управления разрешается выдача содержимого счетчика- 18 (минимальная длина пути1 ) на блок 6 регистрации через группу элементов И 8(,y, - 8(„,. Высокий потенциал с выхода триггера 19 по выходу 50 блока управления через группу элементов 2 п И-ИЛИ 36||36 возбуждает на считывание по входу о5 формирователя дуги j-й столбец матрицы 1, соответствующий номеру вершины Х- (т.е. ). Это достигается при совпадении сигналов от шины 60 через зажатую клемму X , от триггера 19 и от i-fi шины дешифратора 16 (.). Одновременно на вычитающий вход реверсивного счетчика через элемент И 30,поступает сигнал с единичного выхода триггера 30 и в момент, когда на нулевой шине дешифратора 15 буд,ет высокий потенциал-, уменьшает его состояние на единицу. На (1-1)-й шине дешифратора 16 высок ш потенциал. При поступлении очередных сигналов с генератора 32 импульсов на счетчик 17 на j-x выхрдах (, 2, ..., п, 0) дешифратора 15 возникают сигналы, которые последовательно считывают по выходу 78 содержимое триггеров формирователей дуг (1-1)-ой строки матрицы 2 через группу элементов ИЛИ . Сигнал, возникающий на выходе j-ro элемента ИЛИ , возбуждает на считывание i-ю () строку матрицы 1 по выходу 70. В результате наложения столбца и i-ой строки рабочей матрицы : анализируется содержимое триггера 37 и через элемент И 38 по входу 64 формирователя дуги матрицы 1 определяется наличие входящей связи в вершину Х. Если связь обнаружена (сигнал на выходе п х п-входового элемента ШШ 14), счетчик 17 устанавливается в нулевое состояние через элемент И 31 по входу 52 блока управления, а триггер 19 через элемент (п+1) И-ИЛИ 23 устанавливается в нулевое состояние, Одновременно с анализом входящей связи фиксируется HOMiep верщины, составляющей входящую связь. Это достигается путем подсчета количества импульсов (1-1)-ым счетчиком группы 33;|-33j, которые поступают на счетный вход через (1-1)-й элемент п И-ИЛИ группы 35,|-35, на входы которых сигналы поступают от дашифратора 15 при совпадении управляю щих сигналов от (1-1)-ой шины дешифратора 16, с единичного выхода триггера 20 и J-ых выходов (i-l)-ro дешифратора группы 34(-34. Если связь обнаружена (сигнал с выхода элемента ШШ 14). счетчик 17 через элемент И 31 устанавливается в нуль. На .вычитайщк-й вход реверсивного счетчижа снова поступает сигнал через элемент И 30, уменьшая его состояние на единицу и возбуждая на считывание (1-2)-ю шину дешифратора 16. При это через элементы 2п И-ИЛИ 36,-36 возбуждается по входу 65 формирователя дуги столбец матрицы 1, номер которо го содержит (1-1)-й счетчик группы 33.-33. Это достигается путем подачи сигнала с f-ro выхода (i-l)-ro дешифратора группы ), на злемен ты 2 п И-РШИ . Входящую связь в новую вершину обнаруживают путем подачи импульсов на счетчик 17 и через дешифратор 15 считывают информацию с (г-2)-й строки матрицы 2. Сигнал на выходе j-ro элемента ИЛИ 12;|-12 определяет номер возбуждаемой строки матрицы 1. Формирование номеров вершин, входящих в минимальный путь, заканчивается, когда на первой шине дешифратора 16 Свыход 56 блока управления) имеется высокий потенциал и придет сигнал от пхпвходовбго элемента ИЛИ 14. При этом на блок 6 регистрации через группы элементов (S (8,-8«к) выводится содержимое счетчиков 33/|-33 т.е. номера вершин, составляющих минимальный путь из вершины Х в вершину Хп, Возможен минимальный пут не один. Дальнейший поиск следующего минимального пути осуществляется сле дующим образом. Высокий потенциал с первой шины дешифратора 16 снимает сигнал установки счетчика в нуль. Это достигается путем подачи потен циала с первой шины дешифратора 16 на инверсный вход элемента И 31. (При поступлении очередных импульсов с генератора 32 на счетчик 17 дешифратор 15 продолжает подключать на считывание j-e элементы первой строки матрицы 2 по входу 77 формировате ля дуги. Б результате этого возникший сигнал на выходе j-го элемента ИЛИ группы подключает на считывание () строку матрицы 1, Одновременно счетчик 31 подсчитывает дальше количество импульсов, и если связь обнаружится (сигнал от элемента ИЛИ 14), на (шок регистрации через группы элем€ нтов (8....)(8j,-8p|,) фиксируются вершины, образующие следующий минимальный путь. При достижении счетчиком 33 состояния п очередной сигнал от схемы 35j устанавливает его в нулевое состояние, при этом на управляющем выходе счетчика 33j появляется сигнал (сигнал установки счетчика в нулевое -состояние), который через элементы ИЛИ 25, 2И-ИЛИ 24 поступает на суммирующий вход реверсивного счетчика 18, увеличивая его состояние на единицу. Возбуждается вторая шина дешифратора 16 (). При этом через элементы 2пИ-ИЛИ возбуждается столбец рабочей матрицы, номер которого содержит счетчик .. группы. С поступлением очередных импульсов на счетчик 17 дешифратор 15 возбуждает Последовательно элементы строки матрицы 2, начиная с элемента, которьй не заблокирован дешифратором 34, т.е. с (j+m}-ro-элемента, где п - .содержимое счетчика 34л. Это достигается путем коммутации выходов 1-ых дешифраторов 34,-34 с входами i-ых элементов; п И-ИЛИ 35 35j, а именно нулевой ЕЫХОД дешифратора (сигнал на нем) разрешает прохождение первого сигнала, первьш выход - прохождение второго сигнала, т-й , выход - прохождение (j+m)-ro сигнала и т.д. Через группу элементов ИЛИ 11f-11n, начиная с (j+ra), определяется номер иозбуждаемой строки матрицы 1 и, если связь обнаруживается, дальнейший поиск вершин проводится аналогично описанному Bbmie. Если связи нет, при переходе счетчика из состояния п в нулевое на управляющем выходе счетчиса 34. появляется сигнал, который 4epie3 элементы IfflH 25, 2И-Ш1И 24 поступает насуммирующий вход- реверсивного счетчика. 18, увеличив его состояние на единицу, и дальнейший поиск осуществляется аналогично. Поиск прекраается, когда все счетчкаси установятся в исходное нулевое состояние. Тогда сигнал с нулевых шрш дешифраторов 34j-34 при отсутствии сигнала с единичного выхода триггера 19 через элемент ИЛИ 26 блокирует работу генератора 32 и устанавливает триггер 20 в исходное нулевое остояние и работа устройства прекраKl11

щается, пути из иеришны Х в вершину Xrt не существует, появляется сигнал с выхода элемента И 28,через элемент ИШ 26 блокируется работа генератора 32 и работа устройства прекращается.

Предлагаемое устройство позволяет оперативно проводить исследоваS7,.S7,

4S67

3,.55„ «,.,.«„ S3,..,S3n Я,...58„

3359616

НИИ характеристик связности ориентированного графа, а именно определять окрестности i-ой вершины радиуса R, минимальные пути из вершины в 5 вершину Х , фиксируя при этом .последовательность вершин , входящих в путь , и длину этого пути. Фиг.1

,вт sfV

L.

ЗВ,,и,...№„„Щ.5Эп Л,...Ля „ л, .Нл

л, ,Av, ,л 31