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

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

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

На фиг. 1 представ-пена схема узла матричной модели графа; на фиг, 2 - схема предлагаемого устройства.

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

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

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

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

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

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

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

выходах 1и5, Зи7, 1и5, Зи7 соответственно.

Если в узел ij с произвольным знчением триггера 21 на одну из пар входов 1иЗ, Зи5, 5и7, 7и1 поступают единичные сигналы на выходах 11 и 13, 13 и 15, 15 и 17, 17 и 11 соответственно единичные сигналы и, кроме того, значение триггера 21 единичное.

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

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

Пусть исследуемый граф представлен матрицей смежностей А я;- размера К х К, К - число вершин в графе, где а;: 1, если в графе имеется ребро, ведущее из вершины i в вершину J, и а;; О в противном

J-Кслучае. Матрица достижимостей А

Г 1

определяется условиями а,.

1, если в графе имеется путь из

i в j, и а. 0, если такого пути

j нет. Матрицу А можно вычислить по

матрице-А, определяя последовательvC l

ность матриц А

J , . ,

образом:

(0)-1

Г

А j следующим

(01 (е)

1) ч ij (Е-О

- -Ч(а7

Л а

е;

.()

При этом А А

Настройка устройства на решаемую задачу осуществляется путем установки в ij-M узле матричной модели графа триггера 21 в единичное положение,, если а 1, или установки его в нулевое положение, если а,-; 0. Запуск решения производится подачей единичного сигнала на вход 9 узла 1.1. Через три такта узел 1,1 формирует единичные сигналы на выходах 12, 14, 16, 18 и 19. Сигнал с 12-го выхода распространяется по 12 выходам узлов первой строки, смещаясь на один узел за один такт. Если этот сигнал проходит узел 1,jj у которого состояние триггера 21 единичное, то вниз, по 13-м выходам j-ro столбца узлов начинает распространяться единичный сигнал. Сигнал с 14-го выхода

узла 1.1 распространяется по 14-м выходам узлов первого столбца. Если этот сигнал проходит узел i,1, у которого состояние триггера 21 еди1-1ич- ное, то вправо по 11-м выходам i-й -строки узлов начинает распространяться единичный сигнал. При этом единичный сигнал, посланный вниз из узла 1,j, и единичный сигнал, посланный вправо из узла 1,1, одновременно достигают узла i,j, в котором устанавливается единичное состояние триггера 21. За- прямой, соединякщей сигналы, распространяющиеся по 12-м выходам узлов первой строки и 14-м выходам узлов первого столбца, состояния триггеров 21 соответствуют матрице А , т.е. в ij-M узле триггер 21 имеет единичное состояние, если aq 1, и триггер 21 имеет нулевое состояние, если 0. Через три такта после испускания сигналов узлов 1.1 элемент уже сосчитан т.е. состояние триггера 21 в узле

Сч гг.

В

2.2 соответствует элементу а этот момент узел 2,2, получивший тремя тактами раньше по входу 9 единичный сигнал, формирует единичные сигналы на выходах 12, 14, l6, 18 и 19. Внутри квадрата с вершинами в первых четырех распространяющихся сигналах остаются сосчитанными элементы матрицы А и т.д. Через З К тактов единичные сигналы на выходах 12, 14, 16, 18 и 19 формирует узел К,К, а еще через 2.К тактов все сигналы покидают матричную модель графа. При этом состояние триггера 21 в узле матричной модели графа, соответствует элементу а|- матрицы А , которая является матрицей транзитивного замыкания А исследуемого граЛа. Значение элемента а-; натри 1,J I

цы А снимается с выхода 20 ij-ro узла устройства.

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

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

10

14257054

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

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

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

45

50

55

рым входом первого элемента HJUi группы, с выходом третьего элемента И и вторым входом пятого элемента ИЛИ группы, выход второго элемента И соединен с вторыми выходами третьего и седьмого элементов ИЛИ группы и с выходом четвертого элемента И, тактовые входы всех узлов матричной модели графа объединены и соединены с выходом генератора импульсов, первый и второй выходы К,М-го узла матричной модели графа (где 1, ..., Р) соединены с первым и вторым входами соответственно (К,М+1)-го узла матричной модели графа, третий и четвертый выходы К, узла матричной модели графа соединены с

237056

третьим и четвертым входами (К+1 , М)-го узла матричной модели графа соответственно, пятый и шестой выхо- g ды К,М-го узла матричной модели графа соединены с пятым и шестым входами (К,М-1)-го узла матричной модели графа соответственно, седьмой и восьмой выходы К,М-го узла матричной

10 модели графа соединены с седьмым и восьмым входами (К-1,М)-го узла матричной модели графа соответственно, девятый выход К,М-го узла матричной модели графа соединен с девятым вхо15 дом (Кч-1, М+1)-го узла матричной модели графа, десятые выходы узлов матричной модели графа являются информационными выходами устройства.

фиг. г

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