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

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

Иллюстрации

Показать все

Реферат

 

(72) Авторы изобретения

Г. А, Ерошко и Н. Г. Коробка (71) Заявитель.(54) УСТРОЙСТВО ДЛЯ ОПРЕДЕЛЕНИЯ

ХАРАКТЕРИСТИК ГРАФА

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

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

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

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

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

И первой группы и входами элементов НЕ группы, выходы элементов НЕ соединены с вторыми входами элементов И второй 10 группы (21 .

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

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

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

g,и формирователей дуг, три группы из И элементов ИЛИ, g-входовой элемент ИЛИ, И -входовой элемент И-ИЛИ, два И -раз35

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

34 4

И -входового элемента ИЛИ, j =е входы

\ которого соединены с выходами ) =х элвментов И первой группы, третьими входами формирователей дуг 1 -х столбцов и четвертыми входами формирователей дуг

j -х строк (1 = 1 ) второй матричной модели графа, инверсные входы 1-х элементов И первой группы соединены с единичными выходами 1-х (4 = j) триггеров группы триггеров, единичные входы которых соединены с блоком индикации и с выходами соответствующих элементов И третьей группы, первый вход которых соединен с выходами g-x элементов ИЛИ первой группы, второй вход - с выходами 1 -х () =1) элементов ИЛИ второй группы и с первыми входами 1 х элементов И четвертой группы, инверсные входы элементов И третьей группы соединены со вторыми входами элементов И четвертой группы и со вторым входом устройства, выходы элементов И четвертой группы соединены с блоком индикации, первые выходы формирователей дуг 1 --х строк второй матричной модели графа соединены с входами ) —. х (1 =1 ) элементов ИЛИ первой группы, вторые . выходы формирователей дуг ) - х столбцов второй матричной модели графа соединены со входами j - х элементов ИЛИ второй группы, пятые входы формирователей дуг 1 - ых столбцов второй матричной модели графа соединены с блоком индикации, выходами y - х (q = 1 ) разрядов второго регистра и с первыми входами 1 - x (1 =1 ) элементов

И И-входового элемента И-ИЛИ, вторые входы которых соединены с выходами

1- х элементов ИЛИ третьей группы, входы которых соединены с первыми выходами формирователей дуг q - х строк первой матричной модели графа, вторые выходы формирователей дуг ) - х столбцов . первой матричной модели графа соединены

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

1 - х разрядов первого регистра, инфор» мационные входы которых соединены с выходом К -входового элемента И-ИЛИ.

Блок управления содержит три счетщ = ка no AOclg генератор импульсов, элемент

И, два триггера и два дешифратора, причем вход первого дешифратора соединен с пер5 9914 вым информационным выходом первого счетчика, второй информационный выход которого является первым выходом блока управления, i е выходы первого дешифратора (1 = 1,2 "n) являются первой группой выходов блока управления, управ.ляющий выход первого счетчика соединен с единичным входом первого триггера и нулевым входом второго триггера, информационной вход первого счетчика соединен10 с управляющим выходом третьего счетчика, информационный выход которого являет ся вторым выходом блока управления, первый информационный вход третьего счетчика является вторым входом блока управ-1$ ления, второй информационный вход треть го счетчика соединен с управляющим выходом второго счетчика, который соединен с нулевым входом первого триггера и является пятым выходом блока управления, 20 информационный выход второго счетчика соединен с входом второго дешифтатора, 1 - е выходы которого (1 = 1,2... И ) яв ляются второй группой выходов блока управления, выход генератора импульсов 2$ соединен с информационным входом второго счетчика и первым входом элемента

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

I входы первого и третьего счетчиков и вход генератора импульсов соединены с первым входом блока управления, Формирователь цуги -первой матричной модели графа содержит триггер и два 40 элемента И, причем единичный выход триггера соединен с первыми входами первого и второго элементов И, второй вход первого элемента И является пеум вым входом формирователя дуги, второй вход второго элемента И является вторым входом формирователя дуги, выход второго элемента И является первым, а выход первого элемента И вЂ” вторым выходами формирователя дуги первой матричной модели графа, Формирователь дуги второй матричной моделй графа содержит триггер и три элемента И, причем единичный выход триггера соединен с первыми входами первого $$ и второго зпементов И, единичный вход трйггера соединен с,выходом третьего элемента И, первый вход которого являеъся первым, второй - вторым, третий - пя34 6 тым входами формирователя дуги, второй вход первого элемента И является третьим входом формирователя дуги, второй вход второго элемента И является четвертым входом формирователя дуги, выход nepaci го элемента И является первым, выход второго элемента И - вторыми выходами формирователя дуги второй матричной модели графа.

На фиг. 1 представлена структурная схема устройства для определения харак теристик графа; на фиг. 2 - формирователь дуги. первой матрицы; на фиг. 3формироватепь дуги второй матрицы.

Устройство содержит матрицу 1, со держащую И и функциональных печек 1„„

- 1ии, хранящую исходное состояние исследуемого графа, матрицу 2,. содержащую

И и функциональных ячеек 2,;„- 2ип.. группы из и элементов И 3 - 3

4„, 5 — 5И, 6 - 6, р -входовой элемент ИЛИ 7, линию 8 задержки, груп» пу изб триггеров 9 - 9И, элемент A

И-ИЛИ 10, регистры 11 и 12, группы из И элементов ИЛИ 13 - 13, 14114, 15 - 15и, 16- 16„,, блок 17. индйкации,блок 18 управления, включающий счетчики по в0ДИ19-21, генератор

22 импульсов, элемент И 23, триггеры

24 и 25, дешифраторы 26 и 27, шины управления 28-29.

Выход дешифратора 26 соединен с пер вым информационным выходом счетчика

19, второй информационный выход котороi o соединен с блоком 17 индикации. Счеч чик 19 предназначен для последовательного выбора и хранения номера началь ной вершины графа, 1 = е выходы дешнфратора 26 соединены с первыми входами функциональных ячеек соответственно — х строк матриц 1 и 2. Матрица 2 предназначена для формирования и хране ния матрицы достижимости. Вторые входы функциональных ячеек j- x столбцов мат» рицы 1 соединены с первыми входами соответственно j- x элементов И группы . 3 — 3, с управляющими входами соответственно ) - x разрядов регистра 11 и с j- ми выходами дешифратора 27. Регистр 11 предназначей для формирования окрестностей определенной вершины длн ной 3 . Вход дешифратора 27 соединен с информационным выходом счетчика 2,1, управляющий выход которого соединен с первым информационным входом счетчика

20(через линию 8 задержки и с первыми входами j - х элементов И группы 4, 4И, с вторыми входами j - х строк функ циональных ячеек матрицы 2, с нулевым

7 9914 входом триггера 25, единичный выход которого соединен со вторыми входами эле ментов И группы 3 - 3 и с инверсными вхо дами элементов И группы 4 - 4„нулевой выход соединен с первым входом элемен 5 та И 23, второй вход которого соединен с нулевым выходом триггера 24, нулевой вход которого соединен с управляюпщм выходом счетчика 19 и с единичным входом триггера 25, а единичный вход - с шиной 28, у установочными входами счетчиков 19-20, с входом генератора 22 импульсов, выход которого соединен с информационным входом счетчика 21, с третьим входом элемента И 23, выход которого соединен с блокнруюшим входом генератора 22 и с блоком 17 индикации, . который еше соединен с информапионным. выходом счетчика 20, управляюший вы-! ход которого соединен с. информационным 20 входом счетчика 19, второй информационный вход счетчика 20 соединен с выходом элемента ИЛИ 7, y - е входы которого соединены с.третьими входами функциональ ных ячеек соответственно 4 — х столбцов И и четвертыми входами функциональных ячеек ) - х строк матрицы 2, а также с выходами j- x элементов И группы

ЗА - Зи, инверсные входы которых соединены с единичными выходами соответст- зе венно ) — х триггеров группы 9 — Q единичные входы которых соединены с блоком 17 индикации и с выходами соответственно j - х элементов И группы

54" 5 первый вход которых соединен с зз выходами соответственно j - х элементов ИЛИ 13<- 13, второй вход элемент)1 тов И группы 5 - 5д соединен с выхода-. мн соответственно g - х элементов ИЛИ группы 14 - 14< и с первыми входами

j - х элементов И группы 6 - 6, ин»

4 версный вход элементов И груг.сы 54- 5 соединен с шиной 29 и со вторыми входа 4и 4- х элементов И группы 6„- 6И, выходы которых соединены с блоком 17 4 индикации. Первые выходы функциональных ячеек 4 - х строк матрицы 2 соединены

° t с входами соответственно g - х элемен тов ИЛИ группы 13, 13, .вторые выхо»ды функциональных ячеек j- х столбцов матрицы 2 соединены со входами соответственно ) - х элементов ИЛИ группы 14 14 . Пятые входы функциональных ячеек

- х столбцов матрицы 2 соединены с блоком 17 и алии, с выходами соо вветственно у =го разряда регистра 12 и с первыми входами ) - х элементов .

И элемента И И-ИЛИ 10, вторые входы которых соединены с выходами соответсъ34 8 венно j - х элементов ИЛИ группы 15 15, входы которых соединены с первыми выходами функциональных ячеек соответст венно j- х строк матрицы 1, вторые выходы функциональных ячеек j - x столбцов матрицы 1 соединены с входами соответственно j-ых элементов ИЛИ группы

16 - 16„, выходы которых соединены с первыми информационными входами соответственно 4- х разрядов регистра 12;

Вторые информационные входы R - х разрядов регистра 12 соединены с выходами соответственно j - х элементов И групцы 4;- 4, второй вход которых соединен и с выходами соответственно j — х разрядов регистра 11, информационные входы

j - х разрядов регистра 11 соединены с выходом элемента и И-ИЛИ 10., функциональные ячейки ф „. -" матрицы пп цы 1 содержат триггер 30 и элементы

И 31-32, причем единичный выход триггера 30 соединен с первыми входами элементов И 31-32, второй вход элемента И

31 BMIBBTcsl первым входом ячейки, Вто» рой вход элемента И 32 является вторым входом ячейки, выход элемента И 32 является первым; выход элемента И 3„1 « вторым выходами функциональной ячейки матрицы 1. функциональные ячейки 2« - 2 матрицы

2 содержат триггер 33 и элементы И

34 - 36, причем единичный выход триггера соединен с первыми входами элементов

И 34 - 35, единичный вход триггера соединен с выходом элемента И 36, первый вход которого является первым, второй - вторым, третий — пятым входами ячейки, второй вход элемента И 34 является третьим входом ячейки, второй вход элемента И 35 является четвертым входом ячейки, выход элемента И 34 является первым, выход элемента И 35вторым выходами функциональной ячейки матрицы 2.

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

Исходное состояние: счетчики 19-2 1. триггер 9, 9„, 24-25, регистры 11-12— в нулевом состоянии, в триггеры 2ф, » 28> функциональных ячеек 1 - 1 записано ис»

44 ИИ ходкое состояние исследуемого графа.

Сигнал по управляющей шине 28 (сигнал начала работы) устанавливает триггер

24, счетчики 19 - 20 в единичное состояние и разрешает работу генератора

22 импульсов. При этом считывается ин4 формация с первой (1= 1) строки мач рицы 1 и через группу элементов ИЛИ

991434

9 16 - 16„записывается направленным кодом в регистр 12. В данном случае в регистр записана окрестность первой .вершины (Х ) на расстоянии = 1.

Сигнал с генератора 22 на счетчик 5

21 установит его в единичное состояние и дешифратор 27 выдает- по первой шине сигнал, который считывает информацию с первого () = 1} столбца матрицы 1, которая через группу элементов ИЛИ 15—

15ипоступает на первые входы элемента

° yi И-ИЛИ 10. На вторые входы элемента

И И-ИЛИ 10 поступает информация с регистра 12. Осуществляется операция дизъюнкции логического умножения первой строки и первого столбца матрицы 1. Результат этой операции записывается в первый разряд (= 1) регистра 11.

При поступлении очередных импульсов с генератора 22 на счетчик 21, дешиф- 2О ратор 27 последовательно считывает j - е столбцы () = 1,2,. ° .,И), которые поотупают на первые входы элемента ) И-ИЛИ

10 и в результате его срабатывания в регистре 11 формируется совокупность вершин, составляющих окрестность верши ны Х на расстоянии g = 2. Сигнал íà уггравляющем выходе счетчика 21 .(сигнал перехода счетчика из состояния и. в нулевое состояние) увеличивает содержимое счетчи- зэ ка 20 на единицу, разрешает запись ин» формации из регистра 12 в первую строку (4 = 1)матрицы 2 параллельным кодом через элементы И 36 по входу 5 фуйкциональных ячеек, а также, пройдя через .З линию 8 задержки (лийия задержки на . время необходимое для переписи информаI ции из регистра 12 в j -ю строку матрицы 2), разрешает перепись информации из регистра 11 s регистр 12 параллель- 4о ным кодом черех группу элементов И

4Л- 4и

При поступлении на.счетчик 21 очередных импульсов через дешифратор 27 считывается информация последовательно

$ - x столбцов матрицы 1, которые че рез группу элементов ИЛИ 15<- 1. по тупают на первые входы элемента И-ИЛИ

l0, а на вторые входы поступает инфор» мания с регистра 12 (окрестность вер шины Х„на расстоянии С = 2). В регист ре 11 формируется окрестность вершины

Х на расстоянии f = 3. По управляю» щему сигналу от счетчика 21, сформиро

5S ванные очередные окрестности вершины

Х, (» 1,2, ... И) логически складывают ся и запоминаются в первой строке (1) матрицы 2.

Сигнал на управляющем выходе счетчи ка 2О (сигнал при переходе иэ состояния д в нулевое состояние) увеличивает содержимое счетчика 19 на единицу, äe» шифратор 26 возбуждает на считывание вторую строку (j = 2) матрицы 1. А в первой строке матрицы 2 к этому момен ту сформировано множество вершин, дос тижимых нз вершины Х„.

Аналогично формируется множество вершин достижимых из вершин Q, ..., Х, которые записываются. в = 2,. ° °

И -е строки матрицы 2.

Блок индикации фиксирует окрестность

Х - и вершины на расстоянии В (содер1 жимое регистра 12) в момент. переписи ее в матрицу 2, содержимое счетчика 19 при этом указывает на номер вершины, а содержимое счетчика 20 указывает рао стояние 9

Сигнал на управляющем выходе счетчика 19 (при переходе иэ состояния И в нулевое), означающий, что сформирова» на матрица достижимости, устанавливает триггер 24 в-нулевое, а триггер 25 - в единичное состояние. Высокий потенниал с единичного выхода триггера 25 через группу элементов И 3,,— 3,разрешает выдачу сигналов от дешифратора 27 на стро» ки и столбцы матрицы 2, блокируя при этом цепь передачи из регистра ll в регистр 12. При подключении дешифрато-ром 27 первой шины (пятый вход ) = 1 столбца, четвертый вход 1= 1 строки функциональных ячеек матрицы 2) инфор мация считывается с-первой GTpoKR (че рез группу элементов ИЛИ 14 - 14 ) и с первого столбца (через группу элементов

ИЛИ 13 — 13,) параллельным кодом и поступает на первый и второй входы эле» ментов И 5 5 (схему совпадения), сиг I калы на j - х: выходах схемы совпадения обозначат совокупность вершин, sxo

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

17 индикации, счетчик 20 зафиксирует номер максимального сильиосвязного подграфа (сигналы с выходов группы элемен тов И 3 - 3 через элемент ИЛИ 7 подают

4 и ся на второй информационный вход счетчика 20)., Сигналы с - х элементов.И 5„- 5 установят в единичные состояния - e триггеры 9„- 9, которые заблокируют

6 е столбцы и строки матрицы 2;

Последовательным подключением не, эа блокированных = j -,х. столбцов и строк на схему совпадении (группу эле11. 991 ментов И 5,}- Щ позволяет обнаружить очередные максимальные сильносвязные подграфы, вершины которых зафиксирует блок 17 индикации, номер подграфа определяется счетчиком 20 и фиксируется блоком 17 индикации.

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

21 сигналом по,управляющему выходу установит триггер 25 в нулевое состоя- >0 ние.

При нулевом состоянии триггеров 24 и

25 сигнал с выхода элемента И 23 сигнализирует в блок индикации об окончании работы устройства и блокирует работу ге->> нератора 22 импульсов.

В случае, если требуется выдавать на блок индикации матрицу достижимости по шине 29 подается высокий потенциал.

После ее формирования (сигнал на единич-20 ном выходе триггера 25) сигнал с шины

29 блокирует группу элементов И 5 «5и и на блок 17 индикации последовательно считывается информация } = x строк матрицы 2 через группу элементов ИЛИ 1Я, - 5

14},и группу элементов И 6„- 6

Предлагаемое устройство позволяет расширить функциональные возможности Ilo сравнению с известными, так как позволяет определять окрестности любой 30

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

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

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

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

=руппы из }} элементов ИЛИ,}} -входовой

434 12 элемент ИЛИ, } -входовой элемент И-ИЛИ, два т} -разрядных регистра, блок индикации, причем } — ые выходы первой группы выходов блока управления соединены с первыми входами формирователей дуг соответственно q — х строк первой и вто рой матричных моделей графа, < - е выходы (}= 1,2, } } ) второй группы выходов блока управления соединены с вторыми входами формирователей дуг f- x столбпов (j = 1,2,.-}} ) первой матричной модели графа, первыми входами g - х элементов И первой группы и управляющими входами q — x (} = ) разрядов первого регистра, первый, второй и третий выходы блока управления соединены с блоком индикации, четвертый выход блока управления соединен с вторыми входами элементов И первой группы и с инверсными входами элементов И второй группы, пятый выход блока управления соединен с вторыми входами формирователей дуг второй матричной модели графа и через линию задержки с первыми входами элементов

И второй грутшы, второй вход блока управления соединен с выходом }} -входового элемента ИЛИ, - е входы которого соединены с выходами - х элементов

И первой грутшы, третьими входами формирователей дуг j — x столбцов и четвер» тыми входами формирователей дуг} - х строк (} = )) второй матричной модели графа, инверсные входы a - х элементов

И первой группы соединены с единичныьи выходамп } - х (1 = g ) триггеров группы триггеров, единичные входы которых соединены с блоком индикации и с выходами соответствующих элементов И третьей группы, первый вход которых соединен с выходами 1- х элементов ИЛИ пеовой группы, второй вход - с выходами - х () =1 ) элементов ИЛИ второй группы и с первыми входами y — х элементов И четвертой группы, инверсные входы элемен» тов И третьей группы соединены с вто рыми входами элементов И четвертой группы и со вторым входом устройства, выходы элементов И четвертой группы соединены с блоком индикации, первые выходы формирователей дуг q - х строк второй матричной модели графа соединены с входами j- х () = } ) .элементов

ИЛИ первой группы, вторые выходы фор»мирователей дуг j - х столбцов второй матричной модели графа соединены со входами ) - x элементов ИЛИ второй группы, пятые входы формирователей дуг j - х столбцов второй матричной модели графа соединены с блоком инди34

13 9914 кации, выходами j — х (1 = j ). разрядов второго регистра н с первыми входами — x (j =j ) элементов И И -входового элемента И-ИЛИ, вторые входы которых соединены с выходами j — х элемен S тов ИЛИ третьей группы, входы которых соединены с первыми выходами формирователей дуг 4 - х строк первой матричной модели графа, вторые выходы формирователей дуг -j — х столбцов первой матричной модели графа соединены со входами соответственно, - х элементов

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

j - х элементов И второй группы, второй вход которых соединен с выходами j - х разрядов первого регистра, информацион» 20 ные входы «оторых соединены с выходом

8 -входового элемента И-ИЛИ.

2. Устройство по п. 1, о т л и ч а ю»

III е е с я тем, что блок управления со держит три счетчика по e05N, генератор 2S импульсов, элемент И, два триггера и два дешифратора, причем вход первого дешифратора соединен с первым информационным выходом первого счетчика, второй информационный выход которого 30 явпяется первым выходом блока управле ния, 1 - е выходы первого дешифратора (1 = 1,2,. .,й) являются первой группой выходов блока управления, управляющий выход первого счетчика соединен с еди- д яичным входом первого триггера и нулевым входом второго триггера, информационный вход aepaoro счетчика соединен с управляющим выходом третьего счетчика, информацйонный выход которого яв-. щ ляется вторым выходом блока управления, первый -информационный вход третьего .счетчика является вторым входом блока управления, второй информационный вход третьего счетчика соединен с управляющим а выходом второго счетчика, который соеди

1 кен с нулевым входом первого триггера и является пятым выходом блока управце ния, информационный выход второго счеь чннв ооенннен о неоном второго неннфрм тора, j- e выходы которого (q = 1,2,;,.й являются второй группой выходов блока управления, выход генератора импульсов, соединен с информационным входом второго счетчика и первым входом элемента И, второй и третий входы которого соединены соответственно с нулевыми выходами первого и второго триггеров, а выход - с блокирующим входом генератора импуль сов и является третьим выходом блока управления, единичный выход первого трит гера является четвертым выходом блока управления, а установочные входй перво»

ro и третьего счетчиков и вход генератора импульсов соединены с. первым входом блока управленим.

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

; первой матричной модели графа содержит триггер и два элемента И, причем единичный выход триггера соединен с первыми входами первого и второго элементов И, второй вход первого элемента И является первым входом формирователи дуги, вто рой вход второго элемента И является вторым входом формирователя дуги, выход второго элемента И является первым, а выход первого элемента И - вторым вы» ходами формирователя дуги первой матричной модели графа.

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

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

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

% 643880, кл. 6061 15/20, 1979.

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

% 842842, кл. GO6F 7/122, 1981,