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

 

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

СОЮЗ СОВЕТСКИХ

В

РЕСПУБЛИК

09) (12) gg 4 G 06 F 15/20

ВСЕЮж 1

Ц и:.., 13!

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ

ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССР

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОЧ:КРЫТИЙ (21) 4236213/24-24 (22) 16.03;87 (46) 23.09.88. Бюл. Р 35 (72) П.В.Денисович (53) 681.333(088.8) (56) Авторское свидетельство СССР

У 913389, кл. G 06 F 15/20, 1980.

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

В 1075268, кл, С 06 F 15/20, 1982. (54) УСТРОЙСТВО ДЛЯ МОДЕЛИРОВАНИЯ

ГРАФОВ (57) Изобретение относится к вычислительной технике и может быть использовано для исследования параметров графов, в частности для определения матрицы достижимостей графа. Цель изобретения — повышение быстродействия достигается тем, что в устройстве, содержащем генератор импульсов и матричную модель графа, каждый узел матричной модели графа содержит с первого по четвертый триггеры, группу триггеров, группу элементов

ИЛИ, с первого по пятый элементы

И-НЕ и с первого по четвертый элементы И. 2 ил, 1 1425705 2

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

Цель изобретения — повыше|пге быстродействия устройства.

Ня фиг. 1 представлена схема узла матричной модели графа; ня фиг. 2 схема предлагаемого устройства. узел ij матричной модели графа (i,j = 1, ..., К) содержит девять входов 1-9 для связи с соседними узлами матричной модели графя и вход

10 для связи с генератором тактовых импульсов, девять ньгходов 11-19 для связи с соседними узлами матричной модели графа и выход 20, являющийся

ij ì выходом устройства, триггер 21 (формиронатель дуг), на установочный вход которого всегда подан единичный сигнал, триггеры 22-32, элементы

ИЛИ 33-40, элементы И 41-44, элементы И-НЕ 45-49. Устройство содержит 25 матричную модель 50 графа, представляющую собой матрицу К х К узлон матричной модели графа, где К вЂ” максимальное число вершин исследуемого графа и генератор 51 тактовых импульсов. Выходы с 11-го по 19-й и входы с 1-го по 9-й узлов, выходящие на границу матрицы К х К, не задействованы (кроме входа 9 узла 1.1) и на схеме не показаны.

Узел матричной модели графа работает следующим образом.

Если в узел ij с нулевым значением триггера 21 на один из входон 2, 6 и 8 поступает единичный сигнал, то через один такт генератора тактовых импульсов этот сигнал устанавливается на соответствующем из выходов 12, 14, 16 и 18.

Если в узел ij с произвольным зна-. чением триггера 21 на один из входов

1, 3, 5 и 7 поступает единичный сигнал, то через один такт генератора тактовых импульсов этот сигнал устанавливается на соответствующем из выходов 11, 13, 15 и 17.

5О

Если н узел ij с единичным значением триггера 21 на один из входов

2, 4, 6 и 8 поступает единичный сигнал, то через один такт генератора тактовых импульсов этот сигнал уста55 навливается ня соответствующем из выходов 12, 14, 16 и 18 и, кроме того, формируются единичные сигналы на вьгхолях 1 и 5 „3 и 7, 1 и 5, 3 и 7 соответственно, Если н узел ij с ггроизвольным зна— чением триггера 21 ня одну из пяр входов 1 и 3, 3 и 5, 5 и 7, 7 и 1 поступают единичные сигналы на выходах 11 и 13, 13 и 15, 15 и 17, 17 и

11 соответственно единичные сигналы и, кроме того, значение триггера 21 единичное.

Если н узел ij поступает единичный сигнал на вход 9, то через три такта генератора тактовых импульсов он устанавливается на выходах 19 и, кроме того, формируются единичные сигналы на выходах 12, 14, 16 и 18.

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

Пусть исследуемый граф представлен матрицей смежностей А = (я" ) ! 1 3 размера К х К, К вЂ” число вершин в графе, где а, = 1, если в графе имеется ребро, ведущее иэ вершины в вершину j и я; = 0 в противном 1

+ случае. Матрица достижимостей А — (я; ) определяется условиями а,.

1, если н графе имеется путь иэ и j,и я = О, если такого пути

Р нет, Матрицу А можно вычислить йо матрице - А, определяя последовательность матриц А = (я; ), А (я;; 1, ..., А = (я .". ) следующим (н (<) образом: (о) (Е) я = a" а.

11 е-t!

h ae

) ф- (й)

При этом Л А

Настройка устройства на решаемую задачу осуществляется путем установки в ij ì узле матричной модели графа триггера 21 и единичное положение, если я = 1 или установки его в

У нулевое положение, если a = О, Запуск решения производится подачей единичного сигнала на вход 9 узла

1.1. Через три такта узел 1,1 формирует единичные сигналы на выходах

12, 14, 16, 18 и 19, Сигнал с 12-го выхода распространяется по 12 выходам узлон первой строки, смещаясь на один узел за один такт. Если этот сигнал проходит y3eJi 1,1, у KoTopoI состояние триггера 21 единичное, то вниз„ ло 13-м выходам j-го столбца узлов начинает распространяться единичный сигнал. Сигнал с 14-ro выхода

1425705

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

У с тр ой ство для моделир ов ания гр афов, содержащее генератор импульсов и матричную модель графа, содержащую

P x P (где число P — число вершин графа) узлов матричной модели графа, содержащих первый триггер и первый и второй элементы И, о т л и ч а ющ е е с я тем, что, с целью повьппения быстродействия, каждый узел матричной модели графя содержит с перузла 1.1 распространяется по 14-и выходам узлов первого столбца. Если этот сигнал проходит узел х,1, у которого состояние триггера 21 единич5 ное, то вправо по 11-м выходам i-й, строки узлов начинает распространяться единичный сигнал. При этом единичный сигнал, посланный вниз из узла

1,j, и единичный сигнал, посланный 10 вправо из узла i,1, одновременно достигают узла i,j в котором устанавливается единичное состояние триггера 21. За прямой, соединяющей сигналы, распространяющиеся по 12-м выходам узлов первой строки и 14-м выходам узлов первого столбца, состояния триггеров 21 соответствуют матрице A т.е. в ij-м узле тригИ гер 21 имеет единичное состояние, если а .. = 1, и триггер 21 имеет ну(i)

;) 1 (1) левое состояние если а(= О. Через

Э

1) три такта после испускания сигналов узлов 1.1 элемент а уже сосчитан, (<) т.е. состояние триггера 21 в узле 25

2.2 соответствует элементу а . B (1) этот момент узел 2,2, получивший тремя тактами раньше по входу 9 единичный сигнал, формирует единичные сигналы на выходах 12, 14, 16, 18 и

19. Внутри квадрата с вершинами в первых четырех распространякщихся сигналах остаются сосчитанными элементы матрицы А ) и т.д. Через 31К тактов единичные сигналы на выходах

12» 16, 18 и 19 формирует узел

К,К, а еще через 2 ° К тактов все сигналы покидают матричную модель графа. При этом состояние триггера 21 в ij-м узле матричной модели графа-. (и) 40 соответствует элементу а. матрицы (n)

А(), которая является матрицей транзитивного замыкания А исследуемого

+ графа. Значение элемента а; матрицы А снимается с выхода 20 ij-ro

Ф

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

И-HE второй вход седьмого элемента

ИЛИ гругпы соединен с вторыми входами третьего и четвертого элементов

И-НЕ, выходы с первого по четвертый элементов И-НЕ соединены с соответствующими входами пятого элемента

И-НЕ, выход которого соединен с тактовым входом первого триггера, прямой выход которого соединен с первыми входами с первого по четвертый элементов И и является десятым выходом узла матричной модели графа, второй вход первого элемента И соеди- нен с восьмым входом узла матричной модели графа, второй вход второго элемента И соединен с шестым входом узла матричной модели графа, второй вход третьего элемента И соединен с четвертым входом узла матричной модели графа, второй вход четвертого элемента И соединен с вторым входом узла матричной модели графа, выход первого элемента И соединен с вто5 1425705 6 рым входом первого элемента ИЛИ третьим и четвертым входами (К+1 группы, с выходом третьего элемента M)-ro узла матричной модели графа

И и вторым входом пятого элемента соответственно, пятый и шестой выхоИЛИ группы, выход второго элемента ды К М-го узла матричной модели гра5

И соединен с вторыми выходами третье- фа соединены с пятым и шестым входаго и седьмого элементов ИЛИ группы ми (К, M-1) -го узла матричной модели и с выходом четвертого элемента И, графа соответственно, седьмой и тактовые входы всех узлов матричной восьмой выходы К,M-го узла матричной модели графа объединены и соединены 1л модели графа соединены с седьмым и с выходом генератора импульсов, пер- восьмым входами (K-1,М)-го узла матвый и второй выходы К,M-го узла мат- ричной модели графа соответственно, ричной модели графа (где К,И = I, девятый выход К,M-ro узла матричной

P) соединены с первым и вторым модели графа соединен с девятым вховходами соответственно (К,M+1)-ro >g дом (К+1, И+ 1)-го узла матричной моузла матричной модели графа, третий дели графа, десятые выходы узлов и четвертый выходы К,M-го узла мат- матричной модели графа являются инричной модели графа соединены с формационными выходами устройства.

1425705

Составитель О.Гручехина

Техред М. Ходанич ° Корректор С.йекмар

Редактор О. Головач

Тираж 704 Подписное

ВНИИПИ Государственного комитета СССР по делам изобретений и открытий

113035, Москва, Ж-35, Раушская наб., д. 4/5

Заказ 4772/48

Производственно-полиграфическое предприятие, г. Ужгород, ул. Проектная, 4