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

число вершин графа) моделей дуг, каждая из которых состоит из элемента ИЛИ 2, триггера 3, первого А и второго 5 элементов И, первую 6 и вторую 7 группы элементов ИЛИ, группы триггеров прямого 8 и обратного 9 отображений, элемент задержки 10, группу элементов И 11, блок 12 записи, блок 13 управления, генератор 14 тактовых импульсов. Блок 12 содержит дешифратор 15, группу элементов И 16, группу регистров 17, блок

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

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

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

Устройство содержит матрицу Ih X h(h-число вершин графа} моделей дуг, каждая из которых состоит из элемента ИЛИ 2, триггера 3, ...,3, первого 4 и второго 5 элементов И, первую 6,... ,6 и вторую 7, ,.. .7.и группы элементов ИЛИ, группы триггеров прямого 8,...,8нИ обратного 9i,...,9f, отображений, элемент задержки 10, группу элементов И 11,.. 11н,блок 12 записи, блок 13 управления, генератор 14 тактовых импульсов.

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

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

Входами блока 12 являются полюса 27, 28i,...285, 29., ,...,29h входами

18392.

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

и выходами блока 13 - полюса 30,.. .33,

36.

, 35,...,35д,

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

дуги, и столбца с номером J , равным номеру ее конечной вершины. Триггеры 8 и 9 находятся в нулевом состоянии. Устройство работает следующим образом.

С подачей пускового импульса на вход 32 осуществляется сброс регистров 17 блока 12, счетчика 25 блока 13, установка в единичное состояние всех разрядов регистра 26 и установка в единичное состояние первого разряда регистра 24. Высокие потенциалы с единичных выходов всех разрядов регистра 26 через элемент И 19 устанавливают в единичное состояние триггер

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

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

3

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

Цикл вьщеления максимального силь но связного подграфа, содержащего i-ю вершину X;, выполняется путем определения пересечения прямого и обратного r {xj} транзитивных замыканий. Выбор i-и вершины осуществляется элементами И 21 блока 13. При совпадении всех трех высоких потенциалов на i-м элементе И 21 сигнал с его выхода через -и выход 34 блока 13 подается на входы i-x элементов ИЛИ 6,7 и далее - на единичные входы триггеров 8 и 9; единичное состояние i-х триггеров 8 и 9 означает выбор i-и вершины графа, для которой будет осуществляться выделение максимального сильно связного подграфа.

Построение множества осуществляется подачей высокого потенциала с единичного выхода триггера 8| на вторые входы элементов И 4 одноименной строки матрицы 1, за счет чего при наличии дуги из (-и вершины графа в j -ю (,1 1,}, что соответствует единичному состоянию триггера 3iJ , высокий потенциал с выхода элемента И 4;; через элемент ИЛИ 6J перебрасывает в единичное состояние триггер 8.J , с выхода которого высокий потенциал поступает на вторы входы элементов И 4 j-и строки матрицы 1, и так до тех пор, пока существует путь из J-и вершины в очередную, и т.д. Вершинам, образующим прямое транзитивное замыкание для t-й вершины графа, соответствуют единичные состояния триггеров 8. Построение множества г {х-,} производится одновременно подачей высокого потенциала с выхода триггера 9; на вторые входы элемента И 5 одноименного столбца матрицы 1, за счет чего при наличии дуги в t-ю вершину из к-й (i,,h) высокий потенциал с выхода элемента ИЛИ 7 перебрасывает в единичное состояние триггер 9,, с выхода которого высокий потенциал поступает на вторые входы элементов И 5 к-го столбца матрицы 1, и так до тех пор, пока имеются дуги из предшествующих вершин в данную. Вер- шинам, образующим обратное транзитивное замыкание для i-и вершины графа, соответствует единичное состояние триггеров 9.

18392

Далее выполняется цикл записи. По приходу следующего тактового импульса на элемент И 20 блока 13 триггер 22 перебрасывается в противоположное состояние. Единичный сигнал с инверсного выхода триггера 22 поступает на регистр 24 блока 13 и осуществляет сдвиг единицы в следующий разряд. Этот же единичный сигнал с

fO инверсного выхода триггера 22 посту- пает на выход 33 блока 13 и нз вход счетчика 25 (причем на входе счетчика подключен элемент задержки, обеспечивающий задержку сигнала на время

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

Сигнал записи с выхода 33 блока 13 подается на вход элемента задержки 10 и на третьи входы элементов И 11. Пересечение прямого Г(х,} и обратного транзитивных замыканий осуществляется совпадением высоких потенциалов на входах соответствующих элементов И 11, Вершины, входящие в вьщеленный максимальный сильно связный подграф, определяются высокими потенциалами на выходах одноименных элементов И 11. Эти сиг- налы поступают на входы 29 блока 12, которые соединены с первыми входами элементов И 13. Запись информации осуществляется в тот регистр 17|, входные элементы И I6 которого открыты сигналом с выхода дешифратора 15. Единичное значение j -го разряда регистра 17 показывает, что j-я вершина графа входит в вьщеленный максимальный сильно связный подграф с но- мером i . Высокий потенциал с выхода I-го элемента И 11 через элементы ИЛИ 2 осуществляет сброс триггеров 3 I -и строки и ( -го столбца матрицы 1, исключая тем самым ( -ю вершину гра- фа из дальнейшего рассмотрения.

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

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

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

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

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

Устройство для моделирования графов, содержащее матрицу и«и(и -число вершин графа, моделей дуг, каждая из которых состоит из триггера, первого и второго элементов И, первую и вторую группы элементов ИЛИ, группу триггеров прямого и группу триггеров обратного отображения, группу элементов И, блок управления и генератор тактовых импульсов, причем Ь каждой модели дуги единичный выход триггера подключен к первым входам первого и второго элементов И, выходы первых элементов И каждой модели дуги I -го столбца (i l,-i ) матрицы моделей дуг соединены с соответствующими входами I -го элемента ИЛИ- первой группы, выход каждого из которых подключен к единичному входу соответствующего триггера прямого отображения группы, выход которого соединен с вторыми входами первых элементов И ( -и строки матрицы моделей дуг, выходы вторых элементов И каждой модели дуги j-и строки (j 1|Ь) матрицы моделей дуг соединены с соответствующими входами j-го элемента ИЛИ второй группы, выход которого подключен к единичному входу

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

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

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

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

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

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

Фи1.2

J5r 35z

J5s

/5

.

r I г

J/

Wcocro 6n

I

31 J/

Фиг.З

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