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

Описание патента на изобретение SU991434A1

(54) УСТРОЙСТВО ДЛЯ ОПРЕДЕЛЕНИЯ ХАРАКТЕРИСТИК ГРАФА

Похожие патенты SU991434A1

название год авторы номер документа
Устройство для определения характеристик связности ориентированного графа 1983
  • Ерошко Геннадий Антонович
  • Коробка Надежда Григорьевна
SU1133596A1
Устройство для определения крат-чАйшЕгО пуТи B гРАфЕ 1979
  • Титов Виктор Алексеевич
  • Гайдуков Владимир Львович
  • Назаров Станислав Викторович
  • Тафинцев Владимир Александрович
SU842842A1
Устройство для моделирования сетевых графов 1982
  • Титов Виктор Алексеевич
  • Баженов Сергей Михайлович
  • Левашов Владимир Константинович
SU1065858A1
Устройство для определения критического пути в графе 1981
  • Титов Виктор Алексеевич
  • Гайдуков Владимир Львович
  • Кислинский Евгений Васильевич
  • Крикунов Виктор Михайлович
  • Мачулин Василий Васильевич
SU962968A1
Устройство для исследования графов 1985
  • Швыркин Игорь Николаевич
  • Назаров Станислав Викторович
  • Сущев Владимир Иванович
  • Примаков Алексей Алексеевич
SU1307463A1
Устройство для исследования связности вероятностного графа 1985
  • Багрич Александр Иванович
  • Кустов Владимир Николаевич
SU1256039A1
Устройство для распределения заданий процессорам 1986
  • Матов Александр Яковлевич
  • Костюченко Валентин Дмитриевич
  • Ефимов Петр Валентинович
  • Кравчук Сергей Васильевич
SU1319031A1
Устройство для определения минимальных путей в графах 1980
  • Титов Виктор Алексеевич
  • Гудыно Лев Петрович
  • Шевченко Александр Григорьевич
  • Кузьменко Олег Антонович
SU886006A1
Устройство для исследования графов 1985
  • Омельченко Александр Сергеевич
  • Батраков Валерий Александрович
  • Сущев Владимир Иванович
SU1374236A1
УСТРОЙСТВО ПОИСКА НИЖНЕЙ ОЦЕНКИ РАЗМЕЩЕНИЯ В МАТРИЧНЫХ СИСТЕМАХ ПРИ НАПРАВЛЕННОЙ ПЕРЕДАЧЕ ИНФОРМАЦИИ 2009
  • Борзов Дмитрий Борисович
RU2452005C2

Иллюстрации к изобретению SU 991 434 A1

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

Формула изобретения SU 991 434 A1

Изобретение относится к вычислительной технике и может быть использовано при создании устройств для решения задач на графах и как составная часть вычислительных систем. Известно устройство для исследования графов, содержащее модели вершин, соединенные между собой согласно топологии исследуемого графа, регистр, вход и выход которого подключены к перво му выходу и входу блока управления, второй, третий и четвертый выходы котсфого соединены соответственно с первым, вторым и третьим входа1ли моделей вершин, информационные выходы регистра соединены с первыми входами элементов И группы, второй вход каждого из которых под, ключей к первому выходу соответствующей модели вершины, выходы элементов И группы подключены соответственно к четвертым входам моделей вершин, каждая из которых содержит два триггера, элементы ИЛИ, И, НЕ, два формироват ля импульсов, счетчик импульсов и блок индикации Г1Т Наиболее близким по техняческсму решению к предлагаемому является устройство для определения кратчайшего пути в графе, содержащее блок управления, ЕОФпульсный вход которого соединен с генератора импульсов, матричную модель графа, состоящую изу.И формирователей дуг, выходы формирователей дуг каждого столбца соединены с входами соответствующих элементов ИЛИ, по числу столбцов матричной модели графа пер вую и вторую группу триггеров, группу схем сравнения, первую и вторую группу счетчиков, группу элементов НЕ н четыре группы из V элементов И,приче счет ( ные входы триггеров второй группы подключены к вькоду соответствующей сх&мы сравнения, управляющие входы которых соединены с вторым выходом блока управления; третий и четвертый выходы которого подключены к управляющим вхопам соответствующих элементов И третьей и четвертой группы, выходы элементов И третьей и четвертой групп соединены с. входами счетчиков первой и второй группы, выходы которых подключены к входам схем сравнения, выходы триггеров первой группы соединены с входами элементов И первой группы и входами элементов НЕ грухшы, выходы элементов НЕ соединены с вторыми входами элементов И второй группы t 2 3 Недостатком известных устройств я&ляется невозможность определения окрестностей вершин графа определенного радиуса. Цель изобретения - расширение функциональных возможностей устройства за счет определения окрестностей вершин графа определенного радиуса. Поставленная цель достих ается тем, что в устройство для определения характеристик графа, содержащее блок упра&пения, первый вход которого является входом устройства, первую матричную модель графа, состояшую из И- И формирователей дуг, по числу столбцов первой мат ричной модели графа группу Ц-входовых элементов ИЛИ, четыре группы из и элементов И, по числу строк первой матричной модели графа группу триггеров, введе ны вторая матричная модель графа из , у,И формирователей дуг, три группы из элементов ИЛИ, И-входовой элемент ИЛИ И -входовой элемент И-ИЛИ, два V) -раэ рядных регистра, блок индикации Г причем i -ые выходы первой группы выходов блока управления соединены с первыми входами формирователей дуг соответственно 1 -X строк первой и второй матричных моделей графа, i -е выходы ( 1 1,2, .., и) второй группы выходов блока управления соединены с вторыми входами |формирователей а. столбцов { j 1,2, . ...,li) первой матричной модели графа, первыми входами j х элементов И первой группы и управляющими входамиf-2x ( р разрядов первого регистра, первый, второй и третий выходы блока управления соединены с блоком индикаюга, четвертый выход блока управления соеаянен с втсфыми входами элементов И первой группы и с инверсными входами элексентов И второй группы,пятый выход блока управления соедн пь1, пятый выход блока управления соединен с вторыми входами фс мирователей дуг второй матричной модели графа и через линию задержки с входами элементов И второй группы, второй вход блока управления соедшен с ыходом М -входового элемента ИЛИ, I е входы которого соединены с выходами j х эл&ментов И первой группы, третьими входами формирователей дуг у -х столбцов и четвертыми входами формирователей дуг -X строк (1 j ) второй матричной модели графа, инверсные входы 1-х элементов И первой группы соединены с единич ными выходами-i-x (1 ) триггеров группы триггеров, единичные входы которых единены с блоком индикации и с выходами соответствующих элементов И третьей группы, первый вход которых соединен с выходами Н -X элементов ИЛИ первой группы, второй вход - с выходами j -х ( j i) элементов ИЛИ второй группы и с первыми входами j -X элементов И четвертой группы, инверсные входы элементов И ретьей группы соединены со вторыми входами элементов И четвертой группы и со вторым входом устройства, выходы . элементов И четвертой группы соединены с блоком индикации, первые выходы форМ1 рователей дуг - х строк второй матричной модели графа соединены с входами j-x(l) элементов ИЛИ первой группы, вторые .выходы формирователей дуг - X столбцов второй матричной модели графа соединены со входами j - х элементов ИЛИ второй группы, пятые входы формирователей дуг - ых столбцов второй матричной модели графа соединены с блоком индикации, выходами -f - х {-1 j ) разрядов второго регистра и с первыми входами } -х ) элементов И (-входового элемента И-ИЛИ, вторые входы которых соединены с выходами /i - k элементов ИЛИ третьей группы, входы которых соединены с первыми выходами формирователей дуг 1-х строк первой матричной модели графа, вторые выходы формирователей дуг j.- х столбцов первой матричной модели графа соединены со входами соответственно j - х элементов ИЛИ четвертой группы, выходы кото, рых соединены с первыми информационными входами j-x (l j ) разрядов второго регистра, вторые информационные входы этих же развдцов соединены с выхода ми - X элементов ТИ группы, второй вход коториых соепинен с выходами П - X разрядов первого регистра, информационные входы которых соединены с выходом М -входового элемента И-ИЛИ, Блок управления содержит три сяетч. кй по ) генератор импульсов, элемент И, два триггера и два дешифратора, причем вход первого дешифратора соединен с первым информационным выходом первого счетчика, второй информационный выход которого является первым выходом блока управления, i - е выходы первого дешиф ратора (i l,2t..и) являются первой группой выходов блока управления, управ.ляющий выход первого счетчика соединен с единичным входом первого триггера и нулевым входом второго триггера, информационной вход первого счетчика соединен с управляющим выходом третьего счетчику, информационный выход которого являе ся вторым выходом блока управления, пер вый информационный вход третьего счетчика является вторым входом блока управ ления, второй информационный вход треть го счетчика соединен с управляющим выходом второго счетчика, который соединен с нулевым входом первого триггера и яа ляется пятым выходом блока управления, информационный выход второго счетчика соединен с входом второго дешифтатора, -1 - е выходы которого ( i 1,2... И ) я&ляются второй группой выходов блока управления, выход генератора импульсов соединен с информационным входом второго счетчика и первым входом элемента И, второй и третий входы которого со&динены соответственно с нулевыми выходами первого и второго триггеров, а выход - с блокирующим входом генератора импульсов и является третьим выходом блока управления, единичный выход первого триггера является четвертым выходом блока управления, а установочные входы первого и третьего счетчиков и вход генератора импульсов соединены с первым входом блока управления. Формирователь дуги первой матричной модели графа содержит триггер и два элемента И, причем единичный выход триггера соединен с первыми входами первого и второго элементов И, второй вход первого элемента И является входом формирователя дуги, второй вход второго элемента И является вторым входом формирователя дуги, выход второго элемента И является первым, а выход первого элемента И - вторым выходами формирователя дуги первой матричной модели графа, Формирователь дуги второй матричной модели графа содержит триггер и три эл& мента И, причем единичный выход тригге ра соединен с первымк входами первого и второго элементов И, единичный вход триггера соединен с .выходом третьего элемента И, первый вход которого являет ся первым, втсфой - вторым, третий - пя тым входами формирователя дуги, второй вход первого элемента И является третьим входом формирователя дуги, второй вход второго элемента И является четвертым входом формирователя дуги, выход первого элемента И является первым, выход второго элемента И - вторыми вьисодами формирователя дуги второй матричной модели графа. На фиг. 1 представлена структурная схема устройства для определения харак теристик графа; на фиг. 2 - формирователь дуги первой матрицы; на фиг. 3 формирователь душ второй матрицы. Устройство содержит, матрицу 1, со- . держащую и-и функциональных нечек 1 - 1|,у, , хранящую исходное состояние иоследуёмого графа, матрицу 2, содержащую И- м функциональных ячеек 2, пи з„ .4;.группы из и элементов И И И ® - у1 1 -входовой элемент ИЛИ 7, линию 8 задержки, группу из п триггеров 9/( - 9у, , элемент П И-ИЛИ 10, регистры 11 и 12, группы ИЛИ 13 - 13ц , 14,элементов15j- 15 У,, А0„ , 16 , блок 17. индикации, блок 18 управления, включающий счетчики по тойи19-21, генератор 22 импульсов, элемент И 23, триггеры 24 и 25, дешифраторы 26 и 27, щнны управления 28-29. Выход дешифратора 26 соединен с первым информационным выходом счетчика 19, второй информационный выход которого соединен с блоком 17 индикации. Счет чик 19 предназначен для последовательного выбора и храненш номера начальной вершины графа, 1 е выходы дешифратора 26 соединены с первыми входами функциональщ 1х 51чеек соответственно -1-х строк матриц 1 и 2. Матрица 2 предназначена для формирования и хранония матрицы достижимости. Вторые входы функциональных ячеек j - х столбцов маг рицы 1 соединены с первыми входами соответственно j- х элементов И группы 3j - 3 , с утфавляющими входами СООТЕ ветственно /J - х разрядов регистра 11 и с J- ми выходами дешифратор 27. Р&гистр 11 предназначей для формирования окрестностей определенной вершины длиной 6 . Вход дешифратора 27 соединен с информационным выходом счетчика 21, управляющий выход которого соединен с первым информационным входом счетчика 2 0( через линию 8 задержки и с первыми входами j - X элементов И группы 4 с вторыми входами - х строк функрциональных ячеек матрицы 2, с нулевым

7Й914348

входом триггера 25, единичный выходвенно 4- х элементов ИЛИ группы 15 которого соединен со вторыми входами аявчI L., вхрды которых соединены с первыми

ментов И группы 3.- с инверсными вхавыходами функциональных ячеек cooтвeтc дами элементов И группы 4 - 4 нулевойвенно - х строк матрицы 1, вторые

выход соединен с первым входс эп&лен Sвыходы функциональных ячеек - х стопбта И 23, второй вход которого соединен с нулевым выходом триггера 24, нулевой вход которого соединен с управпяюощм выходом счетчика 19 и с единичным входом триггера 25, а единичный вход - с О ветственно j- х разрядов регистра 12i шиной 23, у установочными входами Вторые информационные входы Я - х ра; чиков 19 -20, с входом генератора 22 импульсов, выход которого соединен с информахшонным входом счетчика 21, с третьим входом элемента И 23, выход которого соединен с блокирующим входом генератора 22 и с блоком 17 индикации, который еще соединен с информационным выходом счетчика 20, управляющий выход которого соединен с информационным входом счетчика 19, второй информацион- ный вход счетчика 20 соединен с выходом элемента ИЛИ 7, - е входы которого соединены с третьими входами функ1Ш шал ных ячеек соответственно J.- х столбцов и четве15тыми входами функциональных яческ j - X строк матрицы 2, а также с вь1ходами - X элементов И группы 3 - Зи , инверсные входы которых со&динены о единичными выходами соответственно } - X триггеров группы 9 - 9j,, единичные входы которых соединены с блоком 17 индикации и с выходами co y ветственно j - х элементов И группы - Vi ®Р°Ь1й вход которых соединен с выходами соответственно -j - х эдемевн тов ИЛИ 13, второй вход элементов И группы 5„ соединен с выхода ми соответственно -( - х- элементов ИЛИ группы 14 и с первыми входами - X элементов И группы 6, - бу,, инверсный вход элементов И 5,(- 5j, соединен с иганой 29 и со вторыми ёхоав мя I- X элементов И гругавы 6j,, выходы которых соед1Шены с блоком 17 индик ши. Первые выходы функциональных ячеек 1- X строк матрицы 2 соединены с входами соответственно j - х элемен-« тов ИЛИ группы 13у- 13, вторые выходы функдисжальных ячеек j- х сгголбцов матрицы 2 соединены со входами соответ ственно { X элементов ИЛИ группы 14 14у,. Пятые входы функшональных ячеек - X столбцов матрицы 2 соединены с блоком 17 индикации, с выходами cooi ветственно 3 разряда регистра 12 и с первыми входами - х элементов И элемента У И-ИЛИ 1О, вторые входы которых соединены с выходами соответст

цов матрицы 1 соединены с входами cooi ветственно /(-ых элем:ентов ИЛИ группы

16. ut выходы которых соединены с первыми информационными входами соот. ряиов регистра 12 соединены с выходами соответственно j - х элементов И группы 4 , второй вход которых соединен с выходами соответственно - х разрядов регистра 11, информационные входы j- X разрядов регистра 11 соединены с выходом элемента Y И-ИЛИ 10.. Функциональные ячейки f - матрицы цы 1 содержат триггер 30 и элементы И 31-32, причем едшшчный выход тригг&ра ЗО соединен с первыми входами элементов И 31-32, второй вход элемента И 31 япвпяется первым входом ячейки, вто- рой вход элемента И 32 является вторым входом 5 чейки, выход элемента И 32 является первым, выход элемента И ЗД вторым выходами функциональной ячейки матрицы 1. Функциональные ячейки 2 - 2 матрицы 2 содержат триггер 33 и элементы И 34 - 36, причем единичный выход тригг ра соединен с первыми входами элементов И 34 - 35, единичный вход триггера соединен с выходом элемента И 36, первый вход которого является первым, второй - вторым, третий - пятым входами ячейки, второй вход элемента И 34 является третьим входом ячейки, второй вход элемента И 35 является четвертым входом ячейки, выход элемента И 34 является первым, выход элемента И 35 вТррым выходами функциональной ячейки матриць 2. Устройство работает следующим образом. Исходное состояние: счетчики 19-21, триггер , 24-25, регистры 11-12в нулевом состоянии, в триггеры 2 - 28у, функциональных ячеек 1. - 1 записано исходное состояние исследуемого графа. Сигнал по управляющей шине 2S (сигнал начала работы) устанавливает триггер 24, счетчики 19 - 2О в единичное сос тояние и разрешает работу генератора 22 импульсов. При этом считывается информация с первой ( -1 1) строки мат рицы 1 и через группу элементов ИЛИ

;16ij- 16у| записывается направленным кодом в регистр 12. В данном случае в регистр записана окрестность первой -верцшины (Х) на расстоянии Е 1Сигнал с генератора 22 на счетчик 21 установит его в единичное состояние и дешифратор 27 вьшаат. по первой шине сигнал который считывает информацию с первого ( j 1) столбца к атрицы 1, которая через группу элементов ИЛИ 15.- 15у поступает на первые входы элемента -И И-ИЛИ Ю. На вторые входы элемента И И-ИЛИ 1(Э Поступает информация с регистра 12. Осуществляется операция дизъюнкции логического умножения первой строки и первого столбца матрицы 1. Р&зультат этой операции записывается в первый разряд ( j 1) регистра 11.

При поступлении очередных импульсов с генератора 22 на счетчик 21,дешифратор 27 последовательно считываете - е столбцы ( j 1,2. . . ,V), которые поступают на первые входы элемента V И-ИЛИ 10 и в результате его срабатывания в регистре 11 формируется совокупность вершин, составляюших окрестность вершины Xj на расстоянии В 2. Сигнал йа управляющем выходе счетчика 21 (сигнал перехода счетчики из состояния п. в нулевое состояние) увеличивает содержимое счетчи- ка 20 на единицу, pa3peiiiaeT запись информации из регистра 12 в первую строку (/I 1) матрицы 2 параллельным кодом через элементы И 36 по входу 5 фуйкциональных 5гчеек, а также, пройдя через линию S задержки (линия задержки на время необходимое для переписи информации из регистра 12 в i -ю строку матрицы 2), разрешает перепись информации из регистра 11 -в регистр 12 параллельиым кодом черех группу элементов И ,.

При поступлении на счетчик 21 очередных импульсов через дешифратор 27 считывается информация последовательно j - X столбцов матриш 1 1, которые через группу элементов ИЛИ lELncxv тупают на входы элемента И-ИЛИ 10, а иа вторые входы поступает информация с регистра 12 (окрестность вершины расстоянии I - 2). В регистре 11 формируется окрестность вершины X на расстоянии 2 3. По управлякн щему сигналу от счетчика 21, сформированные очередные окрестности вершины : Хд ( Е 1,2, -. и) лопачески складываЮ1Т ея и запоминаются в первой строке (1 1) матрицы 2.

Сигнал на управляющем выходе счетчика 2О (сигнал при переходе из состоявшя Y в нулевое состоя1ше) увеличивает содержимое счетчика 19 на единицу, д&шифратор 26 возбуждает на считывание вторую строку (i 2) матрицы 1. А в первой строке матрицы 2 к этому момен- ту сформировано множество вершин, доотижимых из вершины X .

Аналогично формируется множество вершин. достижимых из вершин JL - i которые записываются.в ,,.. , VI -е строки матрицы 2.

Блок индикации фиксирует окрестиосга X : - и вершины на расстоянии В (содержимое регистра 12) в момент, переписи ее в матрицу 2, содержимое счетчика 19 при этом указывает на номер вершины, а содержимое счетчика 20 указьгоает расстояние 8 .

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

рез группу элементов ИЛИ 14j и с первого Столбца (через группу элементов ИЛИ 13.- 13у,) параллельным кодом и поступает на Первый и второй входы элементов И 5.- 5у,(схбму совпадения), сигналы на j - X выходах схемы qoMiaa ния обозначат совокупность верщив, вхо;дяших в первый максимальный сипьносйяэный подграф, который зафиксирует блок 17 иидикашшэ счетчик 2О зафиксн| ует номер максимального сильиосвязного подграфа (сигналы с вь1ходов группы элементов ИЗ.- Зу,через элемент ИЛИ 7 подакяся иа второй информационный вход счетчика 20). ,

Сигналы с -J - X элементов И 5 установят в единичные состошшяг j в триггеры 9, которые заблокируют

j ж 4 - е столбцы и строки матрицы 2 Последовательным подключением не. заблокированных 5 1 столбцов и строк на схему совпадения (группу эле119914ментов И 5,(- fy позволяет обнаружить очередные максимальные сильносвязнЫе подграфы, вершины которых зафиксирует блок 17 индикашш, номер подграфа отхрвделяется счетчиком 20 и фиксируется блоком 17 индикации. Процесс нахождения сильносвязных подграфов прекращается, когда счетчик 21 сигналом по. управляющему выходу установит триггер 25 в нулевое состоя- 0 ние,, При нулевом состо1шии триггеров 24 а 25 сигнал с выхода элемента И 23 сигнализирует в блок индикашш об окончании работы устройства и блокирует работу ге-5 нератора 22 импульсов. В случае , если требуется выдавать на блок индикашш матрицу достижимости по шине 29 подается высокий потенциал. После ее формирования (сигнал на едшшч-20 ном выходе триггера 25) сигнал с щины 29 блокирует группу элементов И - 5 и на блок 17 индикашш последовательно считывается информация -1 х строк мат- рицы 2 через группу элементов ИЛИ i 14у1И группу элементов И бу,. Предлагаемое устройство позволяет расинфить функциональные возможности по сравнению с известными, так как поэволяет определять окрестности любой30 X - и вершины графа радиуса Р и матри- цу достижимости, а при поиске макснмальных сильносвязных подграфов исключает необходимость предварительной кс 1мута ции моделей вершин графа, что обеспечи- 35 вает адаптивность устройства к изменению состояния графа и возможность его иопользования в составе вычислительных систем. Формула изобретения 1. Устройство для определения характеристик графа, содержащее блок управл&ния, первый вход которого является входом устройства, первую матричную модель

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

группы и со вторым входом устройства, выходы элементов И четвертой группы соединены с блоком индикации, первые выходы формирователей дут -} - х строк второй матричной модели графа соедин&ны с входами -x(l) элементов ИЛИ первой группы, вторые выходы фо1 мирователей дуг j - х столбцов второй матричной модели графа соединены со входами j - X элементов ИЛИ второй группы, пятые входы формирователей дуг j - X столбцов второй матричной модели графа соединены с блоком инди3412элемент ИЛИ, Ц -входовой элемент И-ИЛИ, два П-разрядных регистра, блок индикации, причем 1 - ые выходы первой группы вькодов блока управления соединены с первыми входами формирователей дуг соответственно -i - х строк первой и вто. рой матричных моделей графа, 1 - е выхсхды ( Ч 1,2, Ц ) второй группы выходов блока управления соединены с вторыми входа л1 формирователей дуг J- х сталбЦов ( j 1,2,..И ) матричной модели графа, первыми входами J - х элементов И первой группы и управляющими входами - х ( j) разрядов первого регистра, первый, второй и третий выходы блока управления соединены с блоком индикации, четвертый выход блока управ- ления соединен с вторыми входами элеме тов И первой группы и с инверсными входами элементов И второй группы, пятый выход блока управления соединен с вторыми входами формирователей дуг второй матричной модели графа и через линию задержки с первыми входами элементов И второй группы, второй вход блока управления соединен с выходом И -входово о элемента ИЛИ, j - е входы которого соединены с выходами j - х элементов И первой группы, третьими входами формирователеГ дуг j - х столбцов и четве1 тыми входами формирювателей дуг 1 - х строк (i j) второй матричной модели графа, инверсные входы - х элементов И первой группы соединены с единичным &ь1ходами -(-х ( j) триггеров группы триггеров, единичные входы которых соёдинены с блоком индикации и с выходами соответствующих элементов И третьей группы, вход которых соединен с выходами I - X элементов ИЛИ первой группы, BTojpoft вход - с выходами f- х (j 1 ) элементов ИЛИ второй группы и с первыми входами j - х элементов И четвертой груш1ы,инве1х;ные входы элементов И третьей группы соединены с вторыми входами элементов И четвертой 1399 кации, выходами -j- x(). разрядов второго регистра и с первыми входами -1 - X ( i j ) элементов И VI - входового элемента И-ИЛИ, вторые входы которых соединены с выходами -j - х элементов ИЛИ третьей группы, входы которых соединены с первыми выходами формирователей дуг -{ - X строк первой матрич ной модели графа, вторые выходы формиррователей дуг |- х столбцов первой матричной модели графа соединены со входами соответственно j - х элементов ИЛИ четвёртой группы, выходы которых соединены с первыми информашюнными входами 1-х () разрядов второго регистра, вторые информационные входы этих же разр5здов соединены с выходами i - X элементов И второй группы, второ вход которых соединен с выходами -j - х разрядов первого регистра, информацион- ные входы Которых соединены с выходом У) -входового элемента И-ИЛИ. 2. Устройство по п. 1, о т л и ч а го га е е с я тем, что блок управления со держит три счетчика по тоби генератор импульсов, элемент И, два триггера и два дешифратора, причем вход первого дешифратор соединен с первым информационным выходом первого счетчика, второй информационный выход которого является первым выходом блока управления, i - е выходы первого {1 l,2,.i.,n} являются цервсй группой выходов блока управления, управляющий выход первого счетчика соединен с ешьиичным входом первого ориггера и нулевым входом вфорого триггера, {Шформащонный вход первого счетчика соединен с управляющим кыхоаам третьего счетч1& K&t Ш фсфмаш1онный выход которого явяяется вторым выходом блока управления первой янфс1рма1шоша 1й вход третьего :счетчика $шляется вторым входом блока управления, второй информационный вход третьего счетчика соединен с управляющим выходом второго счетчика, который соеда нен с нулевым входом первого тригг и является пятьшГ выходом блока управле ния, информационный выход второго счег чика соединен с бходом второго дешифратора, 4- е выходы которого (i - 1,2,... являются второй группой выходов блока 4 упраЕшения, выход генератора импульсов, соединен с информацио1шым входом второго счетчика и первым входом элeмe:iтa И, второй и третий входы которого соешшены соответственно с нулевьиии выходами первого и второго триггеров, а выход - с блокирующим входом генератора импульсов и является третьим выходом блока управления, единичный выход первого трнг гера является четвертым выхоаом блока ущ авления, а установочные входы нерво го и третьего счетчиков и вход генератора импульсов соединены с. первым входом блока управления., 3.Устройство по п, 1, о т л и ч а юш е е с я тем, что формирователь дугя первой матричной модели графа содержит триггер и два элемента И, прич0 единвч ный выход триггера соединен с новыми входами первого н BTqporo эл лентов И, второй вход первого элемента И является первым входом формирователя дуги, вход второго элемента И является вторым входом формирователя дуги, выход втсфого элемента И является первым, а выход первото элемента И - вторым выходами формирователя дуги первой матричной модели графа. 4.Устройство по п. 1, отличак. ш е е с я тем, что формнроватпль дуги второй матричной модели графа содержит .триггер н эл мевта И, тщтем единичный выход триггера соедгнен с первыми входами первого н элементов И, единичный вход триггера соединен с вь ходом. третьего элемента И, вход которого является первым, второй - вторым, третий - пятым входами формщюватепя дуги, второй вход первого зп&л&па И является третьим формирователя дуги, второй вход второго элемента И является четвертым входшл формиров теля дуги, выход первого элемента И является первым, выход второго эпеме та И - втсфым выходами формирователя дуги второй матричной модели графа Источники информации ., пршштые во внимание при экспертизе 1. Авторское свидетельство СССР № 643880, кл. QO6F 15/2О, 1979. 2. Авторское свидетельство СССР № 842642, кл. GЮ6f 7/122, 1981.

SU 991 434 A1

Авторы

Ерошко Геннадий Антонович

Коробка Надежда Григорьевна

Даты

1983-01-23Публикация

1981-10-21Подача