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

 

Изобретение относится к облас-- ти вычислительной техники и может быть использовано для решения задач выделения максимальных сильно связных подграфов. Целью изобретения является повышение быстродействия устройства. Это достигается введением в блок управления второй группы элементов И вйесто сдвигающего регистра . Устройство для моделирования графов содержит матрицу п хп моделей дуг, две группы элементов ГШИ, группу элементов И, группу триггеров прямого отображения, группу триггеров обратного отображения, элемент задержки, блок записи, блок управления и генератор тактовых импульсов. 3 ил. о р (О с

СО103 СОВЕТСКИХ

СОЦИАЛИСТИЧЕСКИХ РЕСПУБЛИК ((9) ®U (lIl 1 2 7

m1 4 С 06 Г !5 /20

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

Н Д ВТОРСНОМУ СВИДЕТЕЛЬСТВУ.

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИЙ (21) 3903195/24-24 (22) 31.05 ° 85 (46) 23.12.86. Бюл. Р 47 (72) В,А.Батраков и С.Л.Вилков (53) 681 . 333 (088. 8) (56) Авторское. свидетельство СССР

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

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

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

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

3 ил.

1278880 2

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

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

Цель достигается за счет того, что исследование графа производится по гибкому циклу работы (длительность гибкого цикла работы определяется соотношением Т = 2mT„, где m —количество максимальных сильно связных подграфов в графе, m и) .

На фиг.l представлена структурная схема устройства; на фиг.2— структурная схема блока записи; на фиг.3 — структурная схема блока управления.

Устройство содержит матрицу 1 и хи (и — количество вершин графа) моделей дуг, каждая из которых состоит из элемента ИЛИ 2, триггера 3, первого 4 и второго 5 элементов И, первую 6 и вторую 7 группы элементов

ИЛИ, группы триггеров прямого 8 и обратного 9 отображения, элемент

10 задержки, группу элементов, И 11, блок 12 записи, блок 13 управления, генератор 14 тактовых импульсов.

Блек 12 записи содержит дешифратор

15, и групп элементов И 16, группу регистров 17. Блок 13 управления содержит первый 18, второй 19 и третий 20 элементы И, первую группу элементов И 21, .Т-триггер 22, триггер

23 работы вторую группу элементов

И 24, счетчик 25, регистр 26 состояния.

На чертежах также обозначены вход

27 блока записи, группа 28 адресных входов блока записи, группа 29 информационных входов блока записи, первый 30 вход блока управления, группа 31 входов блока управления, второй 32 вход блока управления, первый

33 выход блока управления, первая 34 и вторая 35 группы выходов блока управления, второй 36 выход блока управления.

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

Первоначально в матрицу заносится информация о топологии графа путем установки соответствующих триггеров

3 в единичное состояние. .риггер 3 ! у (i, j=l ï) определяется пересечением строки с номером i, равным номеру

50 начальной вершины моделируемой дуги и столбца с номером j, равным номеру ее конечной вергцины. Триггеры 8 и 9 находятся в нулевом состоянии.

С подачей пускового импульса на второй вход 32 блока управления (БУ), являющегося входом запуска устройства, осуществляется сброс регистров

17 блока 12 записи, счетчика 25 блока 13 управления и установка в единичное состояние всех разрядов регистра 26 состояния. Высокие потенциалы с единичных выходов всех разрядов регистра 26 состояния через элемент И 19 устанавливают в единичное состояние триггер 23 работы, единичное состояние которого определяет период работы всего устройства, Высокий потенциал с прямого выхода триггера 23 работы разрешает прохождение через элемент И 20 тактовых импульсов, поступающих с ге-. нератора 14 на вход 30 блока 13. Сигналы с вьгхода элемента И 20 поступают на счетный вход триггера 22.

При наличии высокого потенциала на его прямом выходе выполняется цикл выделения очередного максимального сильно связанного подграфа из моделируемого графа, а при наличии высокого потенциала на его инверсном выходе выполняется цикл записи номеров вершин выделенного подграфа в блок 12 записи.

Цикл выделения максимального сильно связного подграфа, содержащего -ю вершину.х;, выполняется путем пересечения прямого i х; и обрат л г

II ного Г х транзитивных замыканий.

Выбор i-й вершины осуществляется элементами И 2! блока 13. Еспи i-и элемент И 21 (в начале работы первый элемент И 21) имеет на обоих входах высокий потенциал, то сигнал с его выхода через i-й выход 34 блока 13 . подается на входы 1-х элементов ИЛИ

6 и 7 и далее на единичные входы триггеров 8, и .9;, единичное состояние i-x триггеров 8 и 9 означает вы; бор 1-й вершины графа, для которой будет осуществляться выделение максимального силь IQ связного подграфа. л+.

Построение множества Г х; осуществляется подачей высокого потенциала с единичного выхода триггера 8, на вторые вхоДы элементов

И 4 одноименной строки матрицы 1, 12 за счет чего при наличии дуги из 1-й вершины графа в j-ю (i, j = l,и), что соответствует единичному состоянию триггера 3;, высокий потенциал р с выхода элемента И 4 через эле1,) мент ИЛИ 6 перебрасывает в единич3 ное состояние триггер 8, с выхода которого высокий потенцйал поступает на вторые входы элементов И 4 -й ,1 строки матрицы 1, и так до .тех пор, пока существует путь из j-и вершины в очередную и т.д. Вершинам, образующим прямое транзитивное замыкание для i-й вершины графа, соответствуют единичные состояния тригге ров 8. построение множества Г tx;1 производится одновременно подачей высокого потенциала с выхода триггера

9 на вторые входы элементов И 5 од4 ноимен toro столбца матрицы 1, за счет чего при наличии дуги в i-ю вершину из k-й (i, k=1, п) высокий потенциал с выхода элемента ИЛИ 7 перебрасывает в единичное состояние триггер 9„, с выхода которого высокий потенциал поступает на вторые входы элементов И 5 k-го столбца матрицы 1, и так до тех пор, пока имеются дуги из предшествующих . вершин в данную. Вершинам, образующим обратное транзитивное замыкание для -й вершины графа, соответствуют единичные состояния триггеров 9.

Далее выполняется цикл записи.

По приходу следующего тактового импульса на элемент И 20 блока 13 триггер 22 перебрасывается в противоположное состояние. Сигнал запи и с инверсного выхода триггера 22 через выход 33 блока 13 подается на вход элемента 10 задержки и на третьи входы элементов И 11. Пересечение прямого и обратного транзитивных замыканий осуществляется совпадением высоких потенциалов на входах соответствующих элементов И 11. Вершины, входящие в выделенный максимальный сильно связный подграф, определяются высокими потенциалами на выходах одноименных элементов И 11.

Эти сигналы поступают на группу информационных входов 29 блока 12, которая соединена с первыми входами соответствующих элементов И группы !

6. Запись информации осуществляется в тот регистр 17р (1=1, m, где m— количество максимальных сильно связ78880 4 ных подграфов в графе), входные элементы И 16 которого открыты сигналом с выхода дешифратора 15 (в начале работы в первый регистр 17). Еди5 ничное значение j -ro разряда регистра 17Р показывает, что j-я вершина графа входит в выделенньп максимальный сильно связньп подграф с номером

10 Высокий потенциал с выхода i-го элемента И 11 через элементы ИЛИ 2. осуществляет сброс триггеров 3 i-й строки и i-го столбца матрицы 1, искл|очая тем самым i-ю вершину rpaf5 фа из дальнейшего рассмотрения. Высокие потенциалы, появляющиеся на выходах тех элементов И 11, номера которых соответствуют вершинам исходного графа, выделенным в максимальный сильно связный подграф, через группу входов 31 блока 13 поступают на входы установки в нуль соответствующих разрядов регистра 26. УстановленньпЧ в нулевое состояние i-й разряд ре25 гистра 26 указывает, что 1 я вершина исходного графа входит в один нз выделенных подграфов. Задержанный элементом 10 задержки сигнал записи поступает на нуяевые входы всех триг30 геров 8 и 9, осуществляя тем самым . подготовку для последующей работы у-стройства. Единичный сигнал cинверсного выхода триггера 22 поступает также на вход счетчика 25 (причем на входе счетчика подключен элемент задержки, обеспечивающий задержку сигнал на время цикла записными увеличивает зпачение счетчика на единицу, . новый адрес записи с второй группы

4р выходов 35 блока 13 через группу адресных вхсдов 28 блока 12 поступает на дешифратор 15. Сигнал с выхода дешифратора 15 подается на входы тех элементов И 16, номер строки которых совпадает с адресом записи.

На этом цикл записи кончается.

По следующему тактовому импульсу триггер 22 блока 13 устанавливается в единичное состояние и выполняется

5р следующий цикл выделения максимального сильно связного подграфа. При этом>так как высокий потенциал появляется на выходе только того i-го элемента И 21, для которого соответ55 ствующий элемент И 24 имеет па выходе также высокий потенциал очередной

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

50 фы и имеющей наименьц ий порядковый номер.

Процесс продолжается до тех пор, пока все разряды регистра 26 блока

13 не будут установлены в нулевое состояние. При наличии высоких потенциалов на инверсных выходах всех разрядов регистра 26 на выходе элемента И 18 блока 13 формируется сигнал, который поступает на вход установки в нуль триггера 23 и сбрасывает его, устройство прекращает работу.

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

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

И каждой i-й модели дуги 1-га столбца (i, j=l,n) матрицы моделей дуг соединен с i-м rxopoM j-го элемента ИЛИ первой группы, выход которого подключен к входу установки в

"1" j--га триггера прямого отображения группы, выход которого соединен с вторыми входами первых элементов

И i-и строки матрицы моделей дуг (i=j) и первым входом j-го элемента И группы, выход второго элемента

И каждой j-й модели дуги i-й строки матрицы моделей дуг соединен с ;-м входам i-го элемента ИЛИ второй группы, выход которого подключен к входу установки в "1" 1-гo триггера

o6paHoro отображения группы, выход которого соединен с вторыми входами вторых элементов И j-ro столбца матрицы моделей дуг (3=1) и вторым

f5

30 входом одноименного элемента И группы, в блоке управления разрядные выходы первой группы выходов регистра состояния соединены с одноименными входами второго элемента И блока управления, выход которого подключен к входу установки в "1" триггера работы, разрядные выходы в1орой группы выходов регистра состояния соединены с одноименными входами первого элемента И блока управления, выход которого подключен к входу установки в "0" триггера работы, выход которого соединен с первым входом третьего элемента И блока управления, выход которого подключен к счетному входу Т-триггера, прямой выход которого соединен с первыми входами элементов И первой группы блока управления, инверсный выход Т-триггера соединен со счетным входом счетчика, с входом элемента задержки и с третьими входами элементов И группы, выход каждого i-го элемента И группы подключен к х-му входу первой груп— пы информационных входов регистра состояний, второй вход третьего элемента И блока управления подключен к выходу генератора тактовых импульсов, установочный вход счетчика, входы второй группы информационных входов регистра состояний и первые группы информационных входов всех регистров группы блока записи объедииены и являются входом запуска устройства, выход каждого i-ro элемента И псрвой группы блока управления подключен к (и+1)-м входам i-x элементов ИЛИ первой и второй групп, выход элемента задержки подключен к входам установки в "0 триггеров обратного отображения группы и триггеров прямого отображения группы, выход i-го элемента И группы подключен к первым входам элементов ИЛИ иоделей дуг i-й строки матрицы моделей дуг и к вторым входам элементов ИЛИ моделей дуг i-ro столбца матрицы моделей дуг, выход i-го элемента И группы подключен к первому, входу

i ãо элемента И каждой из групп блока записи, вторые входы элементов

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

78880 8 второму входу (i+1)-ro элемента И первой группы блока управления, первый разрядный выход первой группы выходов регистра состояния соединен с вторым входом первого элемента И первой группы блока управления, рачрядпые выходы второй группы выходов регистра состояния, кроме последнего, подключены к соответствующим входам элементов И второй группы блока управления.

1278880

Сос.тавитель Т. Сапунова

Техред Л.Кравчук Корректор О.Луговая

Редактор В.Кванова

Заказ 6841/49 Гираж 671 Подписное

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

1!3035, 11сскна, 7 -35, Рауиская наб., д. 4 /5

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