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

второго регистра, выход которого соединен с первым входом j-ro элемён та И четвёртой группы, вторые входы элементов И третьей и четвертой групп подключены к инверсному выходу третьего триггера блока управления, выход j-ro элемента И четвертой группы соединен с первыми входами элементов ИЛИ формирователей признаков одноименной строки третьей модели графа, выход t-ro элемента И третьей групйы подключен к вторым входам элементов ИЛИ формирователей признаков одноименного столбца третьей модели графа и i-му входу эле,мента И, выход которого соединен с входами второго триггера и первого элемента ИЛИ блока управления, вы96891

ход первого элемента ИЛИ блока управления подключен к запрещающему входу генератора импульсов, выход и запускающий вход которого соединены соответственно со счетным входом третьего триггера и выходом элемента задержки блока управления, выход счетчика подключен к вторым входам первого и второго элементов ИЛИ блока управления, выход второго элемента ИЛИ блока уп-равления соединен с входом первого триггера блока управления, первый вход второго элемента ИЛИ подключен к выходу элемента ИЛИ, i-й вход которого соединен с выходом элемента ИЛИ j-ro формирователя произведения t -и строк матрицы блока формирования произведения.

УСТРОЙСТВО ДЛЯ ИССЛЕДОВАНИЯ ГРАФОВ, содержащее четыре группы элементов И, элемент ИЛИ, два N-разрядных регистра, блок управления и две модели графа, каждая из которых состоит из матрицы N-N формирователей дуг, выполненных в виде триггеров, причем блок управления содержит счетчик, генератор импульсов и два триггера, отличающееся тем, что, с целью повышения быстродействия, в него введены элемент И, блок формирования произведения и третья модель графа, состоящая из NN формирователей признаков, каждьй из которых содержит элемент ИЛИ и триггер, блок формирования произведения содержит матрицу N-N формирователей произведений, каждый из которых состоит из N элементов И и элемента ИЛИ, в блок управления введены элемент задержки, первьм и второй элементы ИЛИ и третий триггер, причем выход j-ro ( 1, 2,.. .,N) триггера i-й (-« 1,2,,.., N) строки первой модели графа соединен с первым входом -го элемента И каждого формирователя произведения -й строки матрицы блока формирования произведения, выход 1-го триггера j-ro столбца второй модели графа подключен к второму входу i-ro элемента И каждого формирователя произведения j-ro столбца матрицы блока формирования произведения, третий вход j-ro элемента И каждого формирователя произведения соединен с входом элемента задержки блока управления и является входом устройства, выход J-ro элемента И каждого формирователя произведения подклю- 5S чей к j-y входу элемента ИЛИ соответ(Л ствующего формирователя произведения, выход элемента .ИЛИ j-ro формирователя произведения i-й строки матрицы блока формирования произведения соединен с единичным входом триггера j-ro формирователя признака i-й строки третьей модели графа, нулевой СО вход которого подключен к выходу а элемента ИЛИ этого формирователя 00 признака, а нуле.вой выход - к j-y со входу «--го элемента ri первой группы и к t-y входу -го элемента И второй группы, (М+О-е входы элементов И первой и второй групп соединены со счетным входом счетчика блока управления и подключены к прямому выходу третьего триггера блока управления, выхОд i-ro элемента И первой группы соединен с единичным входом.i-го разряда первого регистра, выход которого соединен с первым входом i-ro элемента И третьей группы, выход j-ro элемента И второй группы Подключен к единичному входу j-ro разряда

1

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

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

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

Устройство содержит блок 1 управления, первую 2 и вторую 3 модели графа, первую 4, вторую 5, третью 6 ичетвертзпо 7 группы из N элементов И (N I -, К - число вершин графа), элемент ИЛИ 8, элемент И 9, первый 10 и второй 11 N-разрядные регистры, блок 12 формирования произведе1яия, третью модель графа 13, состоящую из N«N формирователей 14 признаков пути длины два, каждый из которых содержит элемент ИЛИ 15 и триггер 16,

Блок 1 управления содержит счетчик 17 по модулю N-1, генератор 18 импульсов, первый 19, второй 20 и третий 21 триггеры, элемент 22 задержки, первьй 23 и второй 24 элементы ИЛИ. Первая 2 и вторая 3 мо1дели графа состоят из NN формирователей дуг, каждая из которых содержит триггеры 25 и 26 соответственно . Блок 12 содержит N-N формирователей 27 произведений, каждый из которых состоит из М элементов И 28 и одного элемента ИЛИ 29,

На структурных схемах обозначены: первый 30 и второй 31 входы блока управления, первый вход 32 блока 12, первый выход 33 блока управления, второй 34 и третий 35 выходы блока управления, третий вход 36 блока управления, группа выходов 37 первой модели графа, .группа выходов 38 второй модели графа, первая 39 и вторая 40 группы входов блока 12 и группа выходов 41 блока 12,

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

Первоначально триггеры 16 формирователей 14 признаков, регистры 10 и 11, счетчик 2, триггеры 19-21 устанавливаются в нулевое состояние, в первую.2 и вторую 3 модели графа заносится информация о топологии исследуемого графа. При этом триггеры 25 и 26, моделирующие дуги графа, устанавливаются в единичное состояние. Соответствующий триггер определяется пересечением строки с номером, равным номеру начальной вершины дуги, и столбца с номером, равным номеру конечной вершины дуги.

При поступлении пускового сигнала на вход устройства 30 на выходе 33 блока 1 управления появляется сигнал, который через вход 32 блока 12, элементы И 28 „ ,,.. ,28 , 28,,... 128, элементы ИЛИ 29, ,,..,29 формирователей 27 ,, ,, ,27f произведений обуславливает формирование значений элементов матрицы произведения и через группу выходов А1 занесение их в триггеры 16 ,..., 16 (Ъормирователей 14 ,.,,, признаков. Через элемент 22 задержки пусковой сигнал поступает на запускающий вход генератора 18 импульсов. Если на выходе одного из формирователей 27 произведений главной диагонали блока 12 вырабатывается единичный сигнал, то он, кроме третьей модели графа 13, через элемент ИЛИ 8, вход 3 блока 1 управления, элемент ИЛИ 24 устанавливает в единичное состояние триггер 19, что свидетельствует о наличии в графе хотя бы одного цикла

Работа устройства по обнаружению циклов в двухдольном ориентированном графе и выделению вершин графа, образующих циклы, основана на сокращении матрицы произведения и завершается не более чем за (N-1) тактов. Каждый такт работы устройства определяется парой выходных импульсов генератора 18,поступа1ацих на счетный вход триггера 21 .Нечетный импульс генератора 18 (например, первый) устанавливает триггер 21 в единичное состояние, и сигнал с его прямого выхода поступает на счетный вход счетчика 17 и, кроме того, через выход 34 блока 1 управления поступает на (N+1)-e входы всех элементов И 4 и 5, на остальные Н входов которых поступают потенциальные сигналы с нулевых выходов триггеров 16 формирователей 14 признаков соответствующей строки (для элемента И 4) или столбца (для элементов И 5). Сигнал с выхода элемента И соответствующего строке третьей модели графа 13, все триггеры 16 которой находятся в нулевом состоянии (в группе элементов И 4), устанавливает в единичное состояние соответствующий разряд регистра 10, сигнал с выхода элемента И, отвечающего столбцу третьей модели графа 13, все триггеры 16 которого находятся в нулевом состоянии (в группе элементов И 5),устанавливает в единичное состояние соответствующий разряд

регистра 11. Четньш импульс генератора 18 (например, второй) устанавливает триггер 21 в нулевое состояние. Сигнал с нулевого выхода триггера 21 через выход 35 блока управления поступает на вторые входы всех элементов И 6 и 7, первые входы которых соединены с единичными выходами соответствующих разрядов регистров 10 и 11, Сигнал с выхода

д-го элемента И 6 поступает на вторые входы всех элементов ИЛИ 15 формирователей 14 признаков -го столбца третьей модели графа 13 и устанавливает соответствующие триггеры 16 в нулевое состояние.

Сигнал t выхода /-го элемента И 7 поступает на первые входы всех элементов ИЛИ 15 формирователей 14 признаков j-ой строки третьей модели графа 13 и устанавливает соответствующие триггеры 16 в нулевое состояние. Кроме того, выходные сигналы всех элементов И 6 поступают на входы элементов И 9. В случае совпадения сигналов на входах элемента И 9 (все триггеры 16 третьей модели графа 13 находятся в нулевом состоянии, все разряды регистра 10 установлены в единичное состояние) на его выходе вырабатывается импульс, который поступает на вход 36 блока 1 управления, устанавливает в единичное состояние триггер 20 и через элемент ИЛИ 23 поступает на запрещающий вход генератора 18 импульсов, останавливая работу уст ройства, которая завершается не более чем saN-l тактовВ (N-I)-ом такте на выходе переполнения счетчика 17 вырабатывается сигнал, который через элемент ИЛИ 24 устанавливает в единичное состояние триггер 19 и через элемент ИЛИ 23 поступает ни запрещающий вход генератора 18 импульсов, останавливая работу устройства.

Работа устройства по обнаружению циклов в двудольном ориентированном графе и выделению вершин графа, образующих циклы, заканчивается с остановкой работы генератора 18 импульсов, при этом по состоянию триггеров 19 и 20 можно установить, имеются ли в исследуемом графе циклы,. а по состоянию разрядов регистра 10 (11) однозначно определяются вершины графа, образующие циклы. Если триггер 20 находится в единичном состоянии, то в исследуемом графе циклов

511968916

нет. Если триггер t9 находится в еди- ва вершин графа, образующих циклы, ничном состоянии, то в исследуемом равны номерам разрядов регистра 10 графе имеется не.менее одного цикла, (11), которые находятся в нулевом и номера вершин первого попцпожест- состоянии.

Г