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

х 06 Р 15/2 ый комитет сс оьеетяний и отнът(ть 131ЩБЯЯцт, ю ИЙ И ПИСАНИЕ ИЗОБРЕТ Я ИДЕТЕЛЬСТВУ ТОР СКОМ ть исполь раметров ределения а. Цель стродейст" устройст- мпульсов тельство ССС 15/20, 1980 льство СССР Р 15/20, 198(57) Изобретение относится к вычи тельной технике и может бызовано для исследования паграфов, в частности для опматрицы достижимостей графизобретения - повышение бывия достигается тем, что вве, содержашем генератор ии матричную модрль графа, каждыйузел матричной модели графа содержитс первого по четвертый триггеры,группу триггеров, группу элементовИЛИ, с первого по пятый элементы)И-НЕ и с первого по четвертый элементы И, 2 ил,Изобретение относится к вычислительной технике и может быть испольэоняно для исследования паряметронграфов, в частности для определенияматрицы достижимостей графа.Цель изобретения - повышение быстродействия устройства,Ня фиг. 1 представлена схема узламатричной модели графя; ня Фиг. 2схема предлагаемого устройства,Узел 13 матричной модели графа(1,3 = 1, , К) содержит девятьвходов 1-9 для связи с соседними узлами матричной модели графа и вход10 для связи с генератором тактовыхимпульсов, девять выходов 11-19 длясвязи с соседними узлами матричноймодели графа и выход 20, являющийся13-м выходом устройства, триггер 21(формирователь дуг), на установочныйвход которого всегда подан единичныйсигнал, триггеры 22-32, элементыИЛИ 33-40, элементы И 41-44, элементы И-НЕ 45-49, Устройство содержит 25матричную модель 50 графа, представляющую собой матрицу К х К узлов матричной модели графа, где К - максимальное число вершин исследуемогографа и генератор 51 тактовых импульсов. Выходы с 11-го по 19-й ивходы с 1-го по 9-й узлов, выходящие на границу матрицы К х К, не задействованы (кроме входа 9 узла 1.1)и на схеме не показаны,Узел матричной модели графа работает следующим образом,Если в узел 3 с нулевым значениемтриггера 21 на один из входон 2,б и 8 поступает единичный сигнал, точерез один такт генератора тактовыхимпульсов этот сигнал устанавливается на соответствующем из выходов 12,14, 16 и 18,Если в узел Ц с произвольным значением триггера 21 на один из входов1, 3, 5 и 7 поступает единичный сигнал, то через один такт генераторатактовых импульсов этот сигнал устанавливается на соответствующем извыходов 11, 13, 15 и 17.БОЕсли н узел Ц с единичным значением триггера 21 на один из входов2, 4, 6 и 8 поступает единичный сигнал, то через один такт генераторатактовых импульсов этот сигнал уста 55навливается на соотнетствукицем извыходов 12, 14, 16 и 18 и, кроме того, Формируются единичные сигналы наУстройство работает следующим образом.Пусть исследуемый граф представлен матрицей смежностей А = я" 11,3 размера К х К, К - число вершин в графе, где а, = 1, если в графе имеется ребро, ведущее иэ вершины в вершину ), и я; = 0 в противном11+ случае. Матрица достижимостей А - )я; ) определяется условиями а,.1, если н графе имеется путь иэв 1,и я = О, если такого путиРнет, Матрицу А можно вычислить йо матрице А, определяя последовательность матриц А = я 1, Ая,; 1, , А = я.".следующимн 1 (и)образом; 1 о) (Е) я =я" а; Еб а,- а 1(а, Л (е- ) Се-) ) 1 Е М (о)При этом ЛАНастройка устройства на решаемую задачу осуществляется путем установки в 3-м узле матричной модели граФа триггера 21 в единичное положение, если я = 1 или установки его вУнулевое положение, если а; = О, Запуск решения производится подачей единичного сигнала на вход 9 узла 1.1, Через три такта узел 1,1 формирует единичные сигналы на выходах 12, 14, 16, 18 и 19, Сигнал с 12-го выхода распространяется по 12 выходам узлов первой строки, смещаясь на один узел за один такт. Если этот сигнал проходит узел 1,1, у которого состояние триггера 21 единичное, то вниз по 13-м выходам 3-го столбца узлов начинает распространяться единичный сигнал. Сигнал с 14-го выхода выходах 1 и 5 3 и 7, 1 и 5, 3 и 7соответственно,Если н узел ) с произвольным зна -чением триггера 21 ня одну из пярнходон 1 и 3, 3 и 5, 5 и 7, 7 и 1гпоступают единичные сигналы на выходах 11 и 13, 13 и 15, 15 и 17, 17 и11 соответственно единичные сигналыи, кроме того, значение триггера 21единичное.Если н узел Ц поступает единичныйсигнал на вход 9, то через три такта генератора тактовых импульсов онустанавливается на выходах 19 и,кроме того, Формируются единичныесигналы на выходах 12, 14, 16 и 18,1425705 20 узла 1. 1 распространяется по 14-и выходам узлов первого столбца. Если этот сигнал проходит узел ,1, у которого состояние триггера 21 единич 5 ное, то вправо по 11-м выходам 1-й ,строки узлов начинает распространяться единичный сигнал, При этом единицный сигнал, посланный вниз из узла 1,1, и единичный сигнал, посланный вправо из узла ,1, одновременно достигают узла ,1, в котором устанавливается единичное состояние триггера 21, За прямой, соединяющей сигналы, распространяющиеся по 12-м выходам узлов первой строки и 14-м выходам узлов первого столбца, состояния триггеров 21 соответствуют матрице А , т,е. в Ц-м узле тригй 1гер 21 имеет единичное состояние, если а = 1, и триггер 21 имеет нуИлевое состояние если а= О , ЧерезФ 11три такта после испускания сигналов узлов 1.1 элемент а уже сосчитан,т , е , состояние триггера 2 1 в узле 25 2 , 2 соответствует элементу а . В11 этот момент узел 2,2, получивший тремя тактами раньше по входу 9 единичный сигнал, формирует единичные сигналы на выходах 12, 14, 16, 18 и 19. Внутри квадрата с вершинами в первых четырех распространякщихся сигналах остаются сосчитанными элементы матрицы А и т.д. Через 31 К тактов единичные сигналы на выходах 12, 14, 16, 18 и 19 формирует узел35 К,К, а еще через 2К тактов все сигналы покидают матричную модель графа. При этом состояние триггера 21 в д 1-м узле матричной модели графа,Ф 40 соответствует элементу а. матрицы (а 11А 1, которая является матрицей транзитивного замыкания А исследуемого+ графа. Значение элемента а, матрицы А снимается с выхода 20 Ц-гоФ45 узла устройства. Формула из обретения Устройство для моделирования графов, содержащее генератор импульсов и матричную модель графа, содержащую Р х Р (где число Р - число вершин графа) узлов матричной модели графа, содержащих первый триггер и первый и второй элементы И, о т л и ч а ющ е е с я тем, что, с целью повьппения быстродействия, каждый узел матричной модели графа содержит с первого по пятый элементы И-НЕ, с второго по четвертый триггеры, группуиз восьми элементов ИЛИ, третий ичетвертый элементы И, группу из восьми триггеров, прямые выходы которыхявляются соответственно с первоголо восьмой выходами узла матричноймодели графа, тактовые входы триггеров группы и с второго по четвертый триггеров соединены с тактовымвходом узла матричной модели графа,информационные входы триггеров группы соединены с выходами соответствующих элементов ИЛИ группы, первыевходы второго, четвертого, шестогои восьмого элементов ИЛИ группы соединены с прямым выходом третьеготриггера и информационным входом чет-вертого триггера, прямой выход которого является девятым выходом узла,информационный вход третьего триггера соединен с прямым выходом второго триггера, информационный вход которого является девятым входом узла,вторые входы элементов ИЛИ группыявляются соответствующими входамиустройства, второй выход первогоэлемента ИЛИ группы соединен с первыми входами первого и четвертого элементов И-НЕ, второй вход пятого элемента ИЛИ группы соединен с первымивходами второго и третьего элементов И-НЕ, второй вход третьего элемента ИЛИ группы соединен с вторымивходами первого и второго элементовИ-НЕ, второй вход седьмого элементаИЛИ группы соединен с вторыми входами третьего и четвертого элементовИ-НЕ, выходы с первого по четвертыйэлементов И-НЕ соединены с соответствующими входами пятого элементаИ-НЕ, выход которого соединен с тактовым входом первого триггера, прямой выход которого соединен с первыми входами с первого по четвертыйэлементов И и является десятым выходом узла матричной модели графа,второй вход первого элемента И соеди-нен с восьмым входом узла матричноймодели графа, второй вход второгоэлемента И соединен с шестым входомузла матричной модели графа, второйвход третьего элемента И соединен счетвертым входом узла матричной модели графа, второй вход четвертогоэлемента И соединен с вторым входомузла матричной модели графа, выходпервого элемента И соединен с вто 5 1425705 6рым входом первого элемента ИЛИ третьим и четвертым входами (К+1 группы, с выходом третьего элемента М)-го узла матричной модели графа И и вторым входом пятого элемента соответственно, пятый и шестой выхо- ИЛИ группы, выход второго элемента ды К М-го узла матричной модели гра 5 фИ соединен с вторыми выходами третье- фа соединены с пятым и шестым входаго и седьмого элементов ИЛИ группы ми (К, М) -го узла матричной модели и с выходом четвертого элемента И, графа соответственно, седьмой и тактовые входы всех узлов матричной восьмой выходы К,М-го узла матричной модели графа объединены и соединены 10 модели графа соединены с седьмым и с выходом генератора импульсов, пер- восьмым входами (К,М)-го узла матвый и второй выходы К,М-го узла мат- ричной модели графа соответственно, ричной модели графа (где К,М = 1, девятый выход К,М-го узла матричнойР) соединены с первым и вторым модели графа соединен с девятым вховходами соответственно (К,М+1)-го 1 ч дом (К+1, М+ 1)-го узла матричной моузла матричной модели графа, третий дели графа, десятые выходы узлов и четвертый выходы К,М-го узла мат- матричной модели графа являются инричной модели графа соединены с Формационными выходами устройства.1625705 ставитель хред М. Хо олова едакт сное 772/ ектная,город, ул Производственно.-полиграфическое предприяти ВНИИПИ Госуд по делам и13035, Москва,ираж 704ственногобретении и-35, Раушс Гручехинаич Корректор С.йек Подпиомитета СССРоткрытийая наб., д. 4/