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

.Семенов681.333(088.8)1. Авторское св630, кл. С 06 РАвторское свид738, кл. С 06 Ротип) . Р 39В.Е.Назаренко детельство ССС15/20, 1980.тельство СССР15/20, 1980 У 94 про ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССРПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ К АВТОРСКОМУ СВИДЕТЕЛЬС(54)(57) УСТРОЙСТВО ДЛЯ ИССЛЕДОВАНИЯПАРАМЕТРОВ ГРАФА, содержащее генератор тактовых импульсов, выход которого соединен с первым входом первого элемента И, второй вход которогосоединен с выходом элемента НЕ,вход которого подключен к выходупереполнения реверсивного счетчика,вычитающий вход которого соединен свыходом первого элемента И, о т л ич а ю щ е е с.я тем, что, с цельюрасширения функциональных возможностей устройства за счет. обеспечениявоэможности вычисления рангов вершинграфа, в устройство введены второйэлемент И, элемент задержки и и вычислительных блоков, каждый из которых состоит из регистра сдвига, блока ключей, первой и второй группэлементов И, первого и второго элементов ИЛИ, первого, второго и третьего дешифраторов, первого, второгореверсивных счетчиков, счетчика, первого и второго элементов НЕ, первого и второго элементов И, блока информации, причем в каждом вычислительном блоке выходы блока ключей соеди"иены с установочными входами разрядов регистра сдвига, выходы разрядов регистра сдвига подключены к первымвходам элементов И первой и второйгрупп, выходы элементов И первойгруппы соединены с входом первогоэлемента ИЛИ, выход которого соединен с суммирующим входом первого реверсивного счетчика, выход которогочерез первый дешифратор соединен свходом первого элемента НЕ, выходкоторого подключен к первому входупервого элемента И вычислительногоблока, выход которого соединен свычитающим .входом первого реверсивного счетчика и с вторым входомсоответствующего элемента И второйгруппы, выходы элементов И второйгруппы соединены с входами второгоэлемента ИЛИ, выход которого подклю,чен к информационному входу счетчика,выход которого. через второй дешифратор соединен с входом блока йндикации, выход последнего разряда регистра сдвига соединен с установочнымвходом его первого разряда и подключен к суммирующему входу второгореверсивного счетчика, вычитающийвход которого соединен с выходом второго элемента И вычислительного блока, первый вход которого соединенс выходом второго элемента НЕ, входкоторого подключен к выходу третьего дешифратора, вход которого соединен с выходом второго реверсивногосчетчика, входы сдвига регистровсдвига всех вычислительныхблоковподключены к выходу первого элементаИ, выход третьего дешифратора каждого вычислительного элемента блокасоединен с соответствующим входомвторого элемента И, выход которогосоединен с вторым входом первого эле 11 мента И первого вычислительного блока, выход первого дешифратора каждого вычислительного блока, кроме последнего, подключен к второму входу первого элемента И последующего вычислительного блока, третий вход первого элемента И каждого вычислительного блока соединен с выходом генератора тактовых импульсов, выход третьего дешифратора каяцого вычислительного блока, кроме последнего, соединен с вторым входом второго элемента И последующего вычислительного блока, второй вход второго элемента И первого вычислительного блока подключен к выходу реверсивного счетчика, третий вход второго элемента И 2 ОЗ 1каждого вычислительного блока соединен с:выходом генератора тактовых импульсов, выход второго элемента И 1-го вычислительного блока соединен с вторыми входами-х элементов И первой группы Ь вычислительных блоков, выход первого элемента И 1-го вычислительного блока соединен с вторыми входами -х элементов И второй группы и вычислительных блоков (где 1 = 1, , и ), установочные входы регистров сдвига, счетчиков, первого и второго реверсивных счетчиков всех вычислительных блоков объединены и соединены с входом блока задержки,выход которого соединен с входами ми блока кюпчей вычислительных блоков.20 Изобретение относится к вычислительной технике, предназначено для исследования параметров графов, в частности для определения рангов вершин графов, и может быть использо вано для оптимального распределения затрат при построении структурно- сложных систем, оценки значимости элементов при техническом диагностировании и т,д. 10Известно устройство для исследования связности и вероятностного графа, содержащее матрицу триггеров, элементы И по числу строк матрицы триггеров, элементы ИЛИ по числу 15 столбцов матрицы триггеров 1.Наиболее близким к изобретению по технической сущности является устройство для исследования путей в графах, содержащее матрицу П х о триггеров формирования дуг графа и генератор тактовых импульсов, выход которого соединен с первым, входом элемента И, второй вход которого является входом устройства, элементы 25 И дуг, по числу столбцов матрицы элементы ИЛИ, элементы задержки, регистры, первые, вторые и третьи группы элементов И, группа элементов .ИЛИ, многовходовой сумматор, узел 30 выбора максимума, дешифратор, элемент НЕ и реверсивный счетчик, вход которого подключен к выходу элемент И, третий вход которого через эле -мент НЕ подключен к выходу устройства и к выходу реверсивного счетчика,выход которого соединен с входомдешифратора, -й ( 1= 1, 2, , и )выход которого подключен через элемент задержки к управляющему входуэлемента И первой группы 1-го столбца, к управляющему входу элемента И1-го столбца и к первым входам элементов И дуг 1-й строки, выход каждого триггера формирования дуги соединен с вторым входо 1. элемента И дуги, выход каждого из которых подключен к входу элемента ИЛИ одноименно -го 1-го столбца, выход элемента ИЛИсоединен с управляющим входом элемента И второй группы 1 -го столбца,выход которого подключен к соответствующему входу узла выбора максиму,ма, выход последнего соединен с пер,вым входом многовходового сумматора,выход которого подключен к информационным входам элементов И первойгруппы, выход элемента И первой группы 1-го столбца соединен с входомрегистра 1-го столбца, выход которого лодключен к информационномувходу элемента И второй группы 1-гостолбца и к информационному входуэлемента И третьей группы 1-го столбца, выходы элементов И третьей груп-зпы соединены соответственно с входа341 з 112 О ми элементов ИЛИ группы, выходы которых подключены к второму входу многовходового сумматора 2 .Недостатком известных устройств является невозможность вычисления рангов вершин графа.Цель изобретения - расширение функциональных возможностей устройства за счет обеспечения вычисления10 рангов вершин графа.Поставленная цель достигается тем, что в устройство для исследования параметров графа содержащее генератор тактовых импульсов, выход15 которого соединен с первым входом первого элемента И, второй вход которого соединен с вькодом элемента НЕ, вход которого подключен к выходу переполнения реверсивного счетчи 20 ка, вычитающий вход которого соединен с выходом .первого элемента И, введейы второй элемент И, элемент задержки и и вычислительньк блоков, каждый из которых состоит из регистра сдвига, блока ключей, первой и второй групп элементов И, первого и второго, элементов ИЛИ, первого, второго и третьего дешифраторов, перво-го, второго реверсивных счетчиков, счетчика, первого и второго элементов НЕ, первого и второго элементов И, блока информации, причем в каждом вычислительном блоке выходы блока ключей соединены с установочными входами разрядов регистра сдвига, выхо ды разрядов регистра сдвига подключены к первым входам элементов И первой и второй групп, выходы элементов И первой группы соединены с входом первого элемента ИЛИ, вькод которо го соединен с суммирующим входом первого реверсивного счетчика, выход которого через первый дешифратор соединен с входом первого элемента НЕ, выход которого подключен к первому 45 входу первого элемента И вычислительного блока, выход которого соединен с вычитающим входом первого реверсивного счетчика и с вторым входом соответствующего элемента И второй 59 группы, выходы элементов И второй группы соединены с входами второго элемента ИЛИ, выход которого подключен к информационному входу счетчика, выход которого через второй дешифра тор соединен с входом блока индика-ции, выход последнего разряда регистра сдвига соединен с установочным входом его первого разряда и подключен к суммирующему входу второго реверсивного счетчика, вычитающий входкоторого соединен с выходом второгоэлемента И вычислительного блока, первый вход которого соединен с выходомвторого элемента НЕ, вход которогоподключен к выходу третьего дешифратора, вход которого соединен с выходом второго реверсивного счетчика,входы сдвига регистров сдвига всехвычислительных блоков подключены квыходу первого элемента И, выходтретьего дешифратора каждого вычислительного блока соединен с соответствующим входом второго элемента И,выход которого соединен с вторым входом первого элемента И первого вычислительного блока, выход первого дешифратора каждого вычислительногоблока, кроме последнего, подключенк второму входу первого элемента Ипоследующего вычислительного блока,третий вход первого элемента И каждого вычислительного блока соединен свыходом генератора тактовых импульсов, выход третьего дешифратора каждого вычислительного блока, кроме последнего, соединен с вторым входомвторого элемента И последующего вычислительного блока, второй вход второго элемента И первого вычислительно.го блока подключен к выходу реверсивного счетчика, третий вход второгоэлемента И каждого вычислительногоблока соединен с выходом генераторатактовых импульсов, выход второгоэлемента И -го вычислительного блока соединен с вторыми входами-хэлементов И первой группы П вычислительных блоков, выход первого элемента И -го вычислительного блока соединен с вторыми входами -х элементов И второй группы ь вычислительных блоков (где= 1, , ь.), установочные входы регистров сдвига,счетчиков, первого и второго реверсивных счетчиков всех вычислительныхблоков объединены и соединены с входом блока задержки, выход которогосоединен с входами блока ключей вычислительных блоков,Предлагаемое устройство осуществляет вычисление ранга вершин графа в соответствии с функцией Р (Ц,1) Р К) Р (Ц, 1 203411где Р(1) - количество путей длины1( = 3, идущих от элемента (вершины) 1 н и,На чертеже представлено предлагаемое устройство, 5Устройство для исследования параметров графа содержит регистры 11 сдвига, блоки 2 1 - 2 ключей,первая группа элементов И 3 - Зп,вторая группа элементов И 41 - 4 л,10первые элементы ИЛИ 51 - 5 п, вторыеэлементы ИЛИ 6 - 6; второй 7 -7,и первый 8 - 8 реверсивные счетчики, счетчики 9, - 9, вторые дешифраторы 1 С - 1 Г, блоки 11 - 11,индикации, первые дешифраторы 1212, третьи дешифраторы 13 - 13,первые элементы НЕ 14 - 14, первые элементы И 15- 15, вторыеэлементы НЕ 16 - 16, вторые элемен-оты И 17 - 17, второй элемент И 18,элемент 19 задержки, входная шина20 "Сброс", шина 21 записи числа иреверсивный счетчик 22, элементНЕ 23, элемент И 24, генератор 25тактовых импульсов, входная шина 26"Пуск", вычислительные блоки 27,Устройство работает следующим образом,Предварительно н реверсивный ЗОсчетчик 22 по входной шине 21 записывается число, соответствующее количеству разрядов в регистрах 1 - 1сдвига, Количество этих разрядовтакже соответствует числу регистровт.е, и , где и - максимальная размерность матрицы смежности. Затем припомощи блока 2- 2 ключей (например, перемычка, переключатель ит.д.) на вход разрядов регистровкоммутируется выход элемента 19 задержки, причем коммутируются лишьте разряды регистров, которые соответствуют единичным элементам матрицы смежности исследуемого графа.Каждый регистр сдвига соответствует одной соответствующей строке матрицы смежности, а 1-й разряд всех регистров соответствует 1-му столбцу этой матрицы. После коммутации соответствующих разрядов к выхо" ду элемента 19 задержки по входной шине 20 подается импульс сброса на еоответствующие входы сброса регистров 1 - 1 сдвига, реверсивных счет.чиков 7 - 7, реверсивных счетчиков 8 - 8 счетчиков 9 - 9 для приве 1 ьдения их в нулевое состояние. Задержанный элементом 19 задержки импульс сброса записывает через скоммутированные ключи блока 2 - 2 ключей в регистры 1 - 1 матрицу смежности исследуемого графа, После окончания этой операции устройство готово к работе.При подаче разрешающего потенциала "Пуск" по входной шине 6 на первый вход элемента И 24, на его выходе появляются тактовые импульсы с генератора 25 тактовых импульсов, так как на тратьем входе элемента И 24 находится единичный потенциал с выхода элемента НЕ 23, который пропадает лишь при нулевом состоянии счетчика 22, т.е. после л -го тактового импульса Тактовые импульсы поступают на управляющие входы регистров 1 - 1сдвига и информация .с выхода каждого регистра подается на его вход, а также на суммирующий вход соответствующего реверсивного счетчика 7 - 7,1. После прихода о -го тактового импульса на второй (нычитающий) вход реверсивного счетчика 22 он переходит к нулевое состояние, так как в исходном состоянии н него записано число ь, соответствующее максимальной размерности матрицы смежности. На выходе реверсивного счетчика 22 появляется напряжение логической единицы, которое, через элементы НЕ 23 запрещает дальнейшее прохождение тактовых импульсов через элемент И 24. За и тактов информация в регистрах переписывается полностью и соответствует исходной матрице смежности, И соответствующих ренерсивных счетчиках 71 - 7 записывается число единиц, содержащихся н соответствующей строке матрицы смежности. На этом заканчивается первый шаг итер ации.( ь + 1)-й импульс с генератора 25 тактовых импульсов поступает через элемент И 15 на вычитающий вход реверсивного счетчика 7 так как элемент И 15 открыт единичным потенциалом с выхода реверсивного счетчика 22 и выхода дешифратора 12 через элемент НЕ 14, а счетчик 7 находится в нулевом состоянии и на его выходе напряжение логического нуля. Дешифраторы 1- 12 п и 13- 13,1 выдают на своем выходе напряжение ло" гической единицы, лишь и случае нулевого состояния соответствующего11203реверсивного счетчика. Тактовые импульсы, начиная с ( л + 1)-го, черезэлемент И 15 начинают поступать навычитающий вход реверсивного счетчика 7, а также на вторые входы эле - 5ментов И 3 - 3, соответствующихпервым разрядам всех регистров1 - 1 сдвига, на первые входы которых подаются сигналы с выходов пер -вых разрядов соответствующих регист" 10ров сдвига. Поэтому если в первомразряде соответствующего регистрасдвига 1 - 1 записана единица,соответствующий ему элемент И 3 -3открывается и тактовые импульсы через соответствующий элемент И 3, -3,соответствующий элемент ИЛИ 5 1 - 5,поступают на второй суммирующийвход соответствующего реверсивногосчетчика 81 - 8. После того, как , 20на вычитающий вход реверсивного счетчика 7 поступает количество тактовых импульсов, соответствующее числуединиц в первой строке матрицы смежности, счетчик переходит в нулевое 25состояние, на выходе дешифратора 1.",появляется напряжение логическойединицы, которое через элементНЕ 14 запрещает прохождение тактовых импульсов через элемент И 15.В соответствующих реверсивных счетчиках 8 - 8 п записывается число,равное количеству единиц в первойстроке матрицы смежности анализируемого графа. Напряжение логическойединицы с выхода дешифратора 12первой группы открывает элементИ 15., так как на первый вход этогоэлемента подается напряжение логической единицы с элемента НЕ 14. Так в 40товые импульсы через элемент И 15с выхода тактового генератора поступают на вычитающий вход реверсивного счетчика . , а также на вторыевходы всех элементов и 3 1 - Зл, соответствующих вторым разрядам всехрегистров сдвига 1 - 1, и если вних записана единица, то тактовыеимпульсы через соответствующий элемент ИЛИ 5 - 5 поступают на суммирующий вход соответствующего реверсивного счетчика 8 - 8йПосле прохождения тактовых импульсов, количество которых соответствует числу единиц во второй строке матрицы смежности, т.е. числу, записанному в реверсивном счетчике 72 . На выходе дешифратора 122 первой группы 41 8появляется напряжение логической единицы, которое через элемент НЕ 14 запрещает прохождение тактовых импульсов через элемент И 15 и разре 2 шает прохождение тактовых импульсов через следующий элемент И 15 . В даль 3 нейшем работа устройства происходит аналогично до тех пор пока информация из последнего реверсивного счетчика 7 не переписывается в соответствующие реверсивные счетчики 8 8. На этом заканчивается второй шаг итерации.Единичные сигналы с выходов дешифраторов 12 - 12 поступают на выоходы элемента И 18, напряжение с выхода которого открывает элемент И 17, для прохождения тактовых импульсов с выхода генератора 25 тактовых импульсов, так как на второй вход элемента И 17 поступает напряжение логической единицы с выхода элемента НЕ 16, на вход которого подается напряжение логического нуля с выхода дешифратора 13, Тактовые импульсы с выхода генератора 25 тактовых импульсов поступают через элемент И 17 на вычитающий вход реверсивно 1го счетчика 8, а также на первые входы элементов И 4- 4, соответствующих первым разрядам регистров 1 - 1 сдвига, на вторые входы которых подключены выходы первых разрядов регистров 11 - 1сдвига. Элементы И 4 - 4, которым соответствуют первые разряды соответствующих регистров 1 - 1 и сдвига, в которых записана единица, открываются и тактовые импульсы через них и соответствующие элементы ИЛИ 6 - 6записываются в соответствующие счетчики 9 - 9 . При прохождении через эле имент И 17 тактовых импульсов, количество которых соответствует числу, записанному в реверсивном счетчике 8, счетчик 8 переходит в нулевое состояние и на выходе дешифратора 13 появляется напряжение логической единицы. Поэтому на выходе элемента НЕ 16 появляется напряжение логического нуля, которое запрещает дальнейшее прохождение тактовых импульсов через элемент И 17 .Одновременно напряжение логической единицы с выхода дешифратора 13, подается на первый вход и открывает элемент И 17 , через который тактовые импульсы начинают поступать9 11203 на вычитающий вход реверсивного счетчика 8 и первые входы элементов И 4 - 4 , соответствующих вторым разрядам регистров 11 - 1 (второму столбцу матрицы смежйости), на вторые входы которых подключены выходы соответствующих вторых разрядов регистров 11 - 1 сдвига, Напряжение логической единицы с тех разрядов, в которых записана единица, открыва" 10 ет соответствующие элементы И 4 -4ъ и тактовые импульсы с их выхода через соответствующие элементы ИПИ 6 - 6 поступают на запись в соответствующие счетчики 9 - 9. 1 Тактовые импульсы через элемент И 17 проходят до тех пор, пока реверсивный счетчик 8 не переходит в нулевое состояние и не закрывает через дешифратор 13 и элемент 2 О НЕ 16 элемент И 17, Напряжение ло 2гической единицы с выхода дешифратора 13 открывает следующий элемент 41 1 ОИ 17 для прохождения тактовых им 3пульсов и цикл работы протекает аналогично.Устройство функционирует до тех пор, пока информация из последнего реверсивного счетчика 8 не перепиИсывается в соответствующие счетчики 9 - 9 (третий шаг итерации) . После этого прохождение тактовых импульсов на какие-либо элементы устройства запрещается элементами И 15 - 15, 17 - 17 и 24, Информация, записанная в каждом счетчике 9 - 9,соответствует рангу соответствующей вершины исследуемого графа. Эта инФормация дешифрируется соответствующим дешифратором 10 - 10 и отображается на соответствующем блоке 11 - 11 индикации.Предлагаемое устройство благодаря наличию новых блоков и связей между ними позволяет осуществлять вычисление ранга вершин графов.