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

 

Изобретение относится к вычислительной технике и может быть использовано при решении на графах задач вьщеления максимальных сильно связных подграфов. Цель изобретения состоит в расширении функциональных возможностей за счет разбиения графа на сильно связные подграфы . Устройство содержит матрицу 1 Ь«ьХь (Л 00 со to

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

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

РЕСПУБЛИК (19) (}1) (51) 4 G 06 F 15/20

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

К ABTOPCHOMY СВИДЕТЕЛЬСТВУ

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ (21) 3753095/24-24 (22) 15.06.84 (46 ) 15.03,86. Бюл. )1- 10 (72) С.Л.Вилков, С.В.Назаров, А.С.Омельченко, В.И.Сущев и С.С.Черенщиков (53) 681.333(088.8) (56) Авторское свидетельство СССР

У 807836, кл. G 06 F 15/20, 1978.

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

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

ГРАФОВ (57) Изобретение относится к вычислительной технике и может быть использовано при решении на графах saдач выделения максимальных сильно связных подграфов. Цель изобретения состоит в расширении функциональных возможностей за счет разбиения графа на сильно связные подграфы. Устройство содержит матрицу 1 h >.(Ичисло вершин графа) моделей дуг, каждая из которых состоит из элемен. та ИЛИ 2, триггера 3, первого 4 и второго 5 элементов И, первую 6 и вторую 7 группы элементов ИЛИ, группы триггеров прямого 8 и обратного

9 отображений, элемент задержки 10, группу элементов И ll блок 12 записи, блок 13 управления, генератор

14 тактовых импульсов. Блок 12 содержит дешифратор 15, группу элементов И 16, группу регистров 17, блок

1218392

13 содержит первый 18, второй 19 и третий 20 элементы И, группу элементов И 21, Т-триггер 22, триггер 23 работы, сдвигающий регистр 24, счетчик 25, регистр 26 состояния. Входами блока 12 являются полюса 27, 28, 29, входами и выходами блока 13— полюса 30-36. Задача разбиения графа на сильно связные подграфы решается путем определения пересечения прямого и обратного замыканий.

3. ил.

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

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

Устройство содержит матрицу

1 h х h(h-число вершин графа моделей дуг, каждая из которых состоит из элемента ИЛИ 2, триггера 3„,...,3,„„, первого 4 и второго 5 элементов И, первую 6,,...,6,„ и вторую 7,,...7. группы элементов ИЛИ, группы триггеров прямого 8,...,8 „ и обратного

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

Блок 12 содержит дешифратор 13, группу элементов И 16,,...,16, группу регистров 17,„э ° ° °,17 „°

Блок 13 содержит первый 18, вто рой 19 и третий 20 элементы И, группу элементов И 21„,...,21„, Т-триггер 22, триггер 23 работы, сдвигающий регистр 241,...,24„, счетчик 25, регистр 26» 26 „ состояния.

Входами блока 12 являются полюса

27, 28„...,28 g, 29„,...,29 входами

2 и выходами блока 13 — полюса 30,... 33, 34 ° ° ° 34н, 35 355 36

Первоначально в матрицу 1 заносится информация о топологии графа путем установки соответствующих триггеров 3 в единичное состояние. Триггер 3;„ (i,i=1,н)определяется пересечением строки с номером, равным номеру начальной вершины моделируемой дуги, и столбца с номером, равным номеру ее конечной вершины. Триггеры

8 и 9 находятся в нулевом состоянии.

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

С подачей пускового импульса на вход 32 осуществляется сброс регистров 17 блока 12, счетчика 25 блока

l3, установка в единичное состояние всех разрядов регистра 28 и установка в единичное состояние первого разряда регистра 24. Высокие потенциалы с единичных выходов всех разрядов регистра 26 через элемент И 19 устанавливают в единичное состояние триггер

23, единичное состояние которого определяет период работы всего устройства. Высокий потенциал с единичного выхода триггера 23 разрешает прохождение через элемент И 20 тактовых импульсов, поступающих с генератора

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

его инверсном выходе выполняется

3 1 цикл записи номеров вершин вьщеленного подграфа в блок 12.

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

n+ л

Г+{х;} и обратного Г х;} транзитивных замыканий. Выбор -й вершины осуществляется элементами И 21 блока 13. При совпадении всех трех высоких потенциалов на j-ì элементе

И 21 сигнал с его выхода через -й выход 34 блока 13 подается на входы

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

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

8i на вторые входы элементов И 4 одноименной строки матрицы 1, за счет чего при наличии дуги из (-й вершины графа в j --ю (i,i = l,h ), что соответствует единичному состоянию триггера 3;„ высокий потенциал с выхода элемента И 4;; через элемент

ИЛИ 6 перебрасывает в единичное состояние триггер 8,;, с выхода которого высокий потенциал поступает на вторые входы элементов И 4 -й строки матрицы 1, и так до тех пор, пока существует путь из "й вершины в очередную, и т.д. Вершинам, образующим прямое транзитивное замыкание для с-й вершины графа, соответствуют единичные состояния триггеров 8. Построение множества Г 1х;) производится одновременно подачей высокого потенциала с выхода триггера 9; на вторые входы элемента И 5 одноименного столбца матрицы 1, за счет чего при наличии дуги в i-ю вершину из к-й (i K=1,è) высокий потенциал с выхода элемента ИЛИ 7< перебрасывает в единичное состояние триггер 9к, с выхода которого высокий потенциал поступает на вторые входы элементов

И 5 к-го столбца матрицы 1, и так до тех пор, пока имеются дуги иэ предшествующих вершин в данную. Вер шинам, образующим обратное транзитивное замыкание для -й вершины графа, соответствует единичное состояние триггеров 9.

218392 4

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

По приходу следующего тактового импульса на элемент И 20 блока 13 триггер 22 перебрасывается в противоположное состояние ° Единичный сигнал с инверсного выхода триггера 22 поступает на регистр 24 блока 13 и осуществляет сдвиг единицы в следующий разряд. Этот же единичный сигнал с инверсного выхода триггера 22 посту- . пает на выход 33 блока 13 и на вход счетчика 25 (причем на входе счетчика подключен элемент задержки, обеспечивающий задержку сигнала на время цикла записи). Значение счетчика 25 увеличивается на единицу, и новый адрес записи с выходов 35 блока 13 поступает через вход 28 блока 12 на дешифратор 15. Сигнал с выхода дешифратора 15 подается на входы тех ,элементов И 16, номер строки которых совпадает с адресом записи.

Сигнал записи с выхода 33 блока

13 подается на вход элемента задерж25 ки 10 и на третьи входы элементов

И 11. Пересечение прямого Г х,"} и и обратного Г (х;) транзитивных замыканий осуществляется совпадением вы.соких потенциалов на входах соответствующих элементов И 11. Вершины, входящие в выделенный максимальный сильно связный подграф, определяются высокими потенциалами на выходах одноименных элементов И 11. Эти сигЗ5 налы поступают на входы 29 блока 12, которые соединены с первьпчи входами элементов И 13. Запись информации осуществляется в тот регистр 17;, входные элементы И 16 которого откры40 ты сигналом с выхода дешифратора 15.

Единичное значение j -ro разряда регистра 17 показывает, что j -я вершина графа входит в выделенный максимальный сильно связный подграф с но45.мером I. Высокий потенциал с выхода

i-ro элемента И 11 через элементы

ИЛИ 2 осуществляет сброс триггеров 3

-й строки и -ro столбца матрицы 1, исключая тем самым 1 -ю вершину гра50 фа из дальнейшего рассмотрения.

Высокие потенциалы, появляющиеся на выходах тех элементов И 11, номера которых соответствуют вершинам исходного графа, выделенным в макси55 мальный сильно связный подграф, через входы 32 блока 13 поступаюг на входы установки в нуль соответствующих разрядов регистра 26. Установлен1218392 ный в нулевое состояние j --й "разряд регистра 26 указывает, что i -я вершина исходного графа входит в один из выделенных подграфов.

Задержанный элементом задержки 10 сигнал записи поступает на нулевые входы всех триггеров 8 и 9, осуществляя тем самым подготовку для последующей работы устройства. На этом цикл записи заканчивается.

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

20

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

Устройство для моделирования гра30 фов, содержащее матрицу h H (ь -число вершин графа) моделей дуг, каждая из которых состоит из триггера, первого и второго элементов И, первую и вторую группы элементов ИЛИ, группу триггеров прямого и группу триггеров обратного отображения, группу элементов И, блок управления и генератор тактовых импульсов, причем в каждой модели дуги единичный выход триггера подключен к первым входам первого и второго элементов И, выходы первых элементов И каждой модели дуги -го столбца (=l,n )матрицы моделей дуг соединены с соответствующими входами t-ãî элемента ИЛИ первой группы, выход каждого из которых подключен к единичному входу соответствующего триггера прямого отображения группы, выход которого соединен с вторыми входами первых элементов И i --й "строки матрицы моделей дуг, выходы вторых элементов

И каждой модели дуги j --й "строки (j =l>ï)матрицы моделей дуг соединены, с соответствующими входами 3 -ro элемента ИЛИ второй группы, выход которого подключен к единичному входу соответствующего триггера обратного отображения, выход которого соединен с вторыми входами вторых элемен тов И J --ro столбца матрицы моделей дуг, отличающееся тем, что, с целью расширения функциональных возможностей ус.тройства за счет решения задачи разбиения графа на сильно связные подграфы, в устройство введены элемент задержки, блок записи, состоящий иэ группы элементов И, группы регистров и дешифратора, блок управления содержит регистр состояния, первый, второй и третий элементы И, группу элементов И, Ттриггер, триггер работы, сдвигающий регистр и счетчик, а в каждую модель дуги введен элемент ИЛИ, выход которого подключен к единичному входу триггера, в блоке управления разрядные выходы первой группы регистра состояния соединены с первыми входами элементов И группы и с входами второго элемента И, выход которого подключен к единичному входу триггера работы, разрядные выходы второй группы регистра состояния соединены с входами первого элемента И, выход которого подключен к нулевому входу триггера работы, выход которого соединен с первым входом третьего элемента И, выход третьего элемента И подключен к счетному входу Т-триггера, единичный выход которого соединен с вторыми входами элементов И группы, инверсный выход Т-триггера соединен со счетным входом счетчика и,с входом синхронизации сдвигающего регистра, разрядные выходы которого соединены с третьими входами элементов И группы, в блоке записи выходы дешифратора подключены к первым входам соответствующих элементов И группы, выходы которых соединены с соответствующими информационными входами первой группы регистров группы, выходы триггеров прямого отображения группы подключены к первым входам соответствующих элементов И группы, вторые входы которых соединены с выходами соответствующих триггеров обратного отображения группы, выход -го элемента И группы подключен к первым входам элементов ИЛИ моделей дуг 1-й строки матрицы моделей дуг, вторым входам элементов ИЛИ моделей дуг

c-ro столбца матрицы моделей дуг, к

1218392

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

И группы блока управления подключены к входам соответствующих элементов

ИЛИ первой и второй групп, выходы счетчика блока управления соединены с соответствующими входами дешифратора блока записи, информационные входы второй группы регистров группы блока записи объединены с установочным вщ>дом счетчика блока управления, с

1О информационными входами второй группы регистра состояния блока управления и с информационньм входом первого разряда сдвигающего регистра блока управления

15 и являются пусковым входом устройства.

1218392

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

Редактор М.Бандура Техред О.Неце Корректор Е. Сирохман

Заказ 1 133/57 Тираж 673 Подписное

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

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

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