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

 

УСТРОЙСТВО ДЛЯ ИССЛЕДОВАНИЯ ГРАФОВ, содержащее четыре группы элементов И, элемент ИЛИ, два 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 разряда

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

СОЦИАЛИСТИЧЕСКИХ

РЕСПУБЛИК (19) SU(ii) (5D 4

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИЙ

ОПИСАНИЕ ИЗОБРЕТЕНИ ":

К ABTOPCKOMY СВИДЕТЕЛЬСТВУ (21) 3761862/24-24 (22) 25.06.84 (46) 07.12.85. Бюл. 11 - 45 (72) А,С,Омельченко, С.В ° Назаров, С.Л.Вилков, В.И.Сущев и С.С,Черенщиков (53) 681.33 (088.8) (56) Зиновьев Э.В, и др, Обнаружение тупиковых ситуаций при взаимодействии информационных процессов в вычислительных сетях. — Автоматика и вычислительная техника, 1981, 11 - 3, с, 11-17.

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

1 991434, кл, G 06 F 15/20, 1981. (54) (57) УСТРОЙСТВО ДЛЯ ИССЛГДОВАНИЯ

ГРАФОВ, содержащее четыре группы элементов И, элемент ИЛИ, два N -разрядных регистра, блок управления и две модели графа, каждая из которых состоит из матрицы N N формирова.телей дуг, выполненных в виде триггеров, причем блок управления содержит счетчик, генератор импульсов и два триггера, о т л и ч а ю щ е е с я тем, что, с целью повышения быстродействия, в него введены элемент И, блок формирования произвеI дения и третья модель графа, состоящая из N.N формирователей признаков, каждый из которых содержит элемент ИЛИ и триггер, блок формирования произведения содержит матрицу N-N формирователей произведений, каждый из которых состоит из N элементов И и элемента ИЛИ, в блок управления вве- дены элемент задержки, первый и второй элементы ИЛИ и третий триго гер, причем выход 1-го (1=1, 2,...,М) триггера 1-й (+=1,2,..., N) строки первой мбдели графа соединен с первым входом j-го элемента И каждого формирователя произведения -й строки матрицы блока формирования произведения, выход i-ro триггера j-ro столбца второй модели графа подключен к второму входу >-го элемента И каждого формирователя произведения 1-го столбца матрицы блока формирования произведения, третий вход j-го элемента И каждого формирователя произведения соединен с входом элемента задержки блока управления и является входом устройства, выход ) -го элемента И каждого формирователя произведения подклю- 9 чен к 1-у входу элемента ИЛИ соответ- уу ствующего формирователя произведения, Ф выход элемента .ИЛИ j-го формировате- С ля произведения i-й строки матрицы

Ф блока формирования произведения сое- .Я динен с единичным входом триггера

j-го формирователя признака i -й строки третьей модели графа, нулевой вход которого подключен к выходу элемента ИЛИ этого формирователя признака, а нулевой выход — к 1-у входу < — го элемента И первой группы и к

-c-у входу g-го элемента И второй группы, (И+1)-е входы элементов И первой и второй групп соединены со счетным входом счетчика блока управления и подключены к прямому выходу третьего триггера блока управления, выход )

1-го элемента И первой группы соединен с единичным входом,i --ro разряда первого регистра, выход которого соединен с первым входом 1-го элемента И третьей группы, выход 1 -го элемента И второй группы подключен к единичному входу j-го разряда

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

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

Устройство содержит блок 1 управления, первую 2 и вторую 3 модели графа, первую 4, вторую 5, третью 6 и четвертую 7 группы из и элементов И (М= — К вЂ” число вершин rpeK. фа), элемент ИЛИ 8, элемент И 9, 2п первый 10 и второй 11 и »разрядные регистры, блок 12 формирования произведения, третью модель графа 13, состоящую из H N формирователей 14 признаков пути длины два, каждый из 25 которых содержит элемент ИЛИ 15 и триггер 16, Блок 1 управления содержит счетчик 17 по модулю N -1, генератор 18 импульсов, первый 19, второй 20 и третий 21 триггеры, элемент 22 задержки, первый 23 и второй 24 элементы ИЛИ. Первая 2 и вторая 3 мо- дели графа состоят из Н М формироход первого элемента ИЛИ блока управления подключен к запрещающему входу генератора импульсов выходи запускающий вход которого соединены соответственно со счетным входом третьего триггера и выходом элемента задержки блока управления, выход счетчика подключен к вторым входам первого и второго элементов ИЛИ блока управления выход второго элемента ИЛИ блока уп-. равления соединен с .входом первого триггера блока управления, первый вход второго элемента ИЛИ подключен к выходу элемента ИЛИ, <-й вход которого соединен с выходом элемента ИЛИ у-го формирователя произведения с -й строк матрицы блока формирования произведения. вателей дуг, каждая из которых содержит триггеры 25 и 26 соответственно. Блок 12 содержит NH формирователей 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, моделирующие дуги графа, устанавливаются в единичное состояние, Соответствующий триггер определяется пересечением строки с номером, равным номеру начальной вершины дуги, и столбца с номером, равным номеру конечной вершины дуги, 3 11

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

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

96891 4

45

30 регистра 11. Четный импульс генератора 18 (например, второй) устанавливает триггер 21 в нулевое состояние, Сигнал с нулевого выхода триг- гера 21 через выход 35 блока управления поступает на вторые входы всех элементов И 6 и 7, первые входы которых соединены с единичными выходами соответствующих разрядов регистров 10 и 11, Сигнал с выхода ,»;го элемента И 6 поступает на вторые входы всех элементов ИЛИ 15 формирователей 14 признаков »-го столбца третьей модели графа 13 и устанавливает соответствующие триггеры 16 ъ в нулевое состояние.

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

ИЛИ 23 поступает на запрещающий вход генератора 18 импульсов, останавливая работу устройства, которая завершается не более чем за N -1 тактов..

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

% 1196891 d нет. Если триггер 19 находится в еди- ва вершин графа, обраэующих циклы нич ом состоянии, то в исследуемом н равны номерам раэрядов регистра 10

В ° графе имеется не.менее одного цикла, (11), которые находятся в нулевом и номера вершин первого подмножест- состоянии.

1196891

1196891

Составитель А,Шеренков

Редактор А,Шандор Техред J1Лратяшова Корректор Е.Рошко, Заказ 7566/49 Тираж 709 Подписное

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

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

Филиал ППП "Патент", г, Ужгород, ул. Проектная, 4