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

( )3а 1ЬИБДйЛЕНА ИСАНИЕ ИЗОБРЕТЕТОРСКОМУ СВИДЕТЕЛЬСТВУ ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССР ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИ(56) Авторское свидетельство СССР У 807836, кл. С 06 Г 15/20, 1978.Авторское свидетельство СССР У 913389, кл. С 06 Г 15/20, 1980,(54) УСТРОЙСТВО ДЛЯ МОДЕЛИРОВАНИЯГРАФОВ(57) Изобретение относится к вычислительной технике и может быть использовано при решении на графах задач выделения максимальных сильносвязных подграфов. Цель изобретениясостоит в расширении функциональныхвозможностей за счет разбиения графа на сильно связные подграфы. Устройство содержит матрицу 1 И 1.(Ичисло вершин графа) моделей дуг,каждая из которых состоит из элемента ИЛИ 2, триггера 3, первого 4 ивторого 5 элементов И, первую 6 ивторую 7 группы элементов ИЛИ, группы триггеров прямого 8 и обратного9 отображений, элемент задержки 1 О,группу элементов И 11, блок 12 записи, блок 13 управления, генератор14 тактовых импульсов, Блок 12 содержит дешифратор 15, группу элементов И 16, группу регистров 17, блок 121839213 содержит первый 18, второй 19 и третий 20 элементы И, группу элементов И 21, Т-триггер 22, триггер 23 работы, сдвигающий регистр 24, счетчик 25, регистр 26 состояния. Входами блока 12 являются полюса 27, 28, 29, входами и выходами блока 13 - полюса 30-36. Задача разбиения графа на сильно связные подграфы решается путем определения пересечения прямого и обратного замыканий, 3. ил.1Изобретение относится к вычислительной технике и может быть использовано для решения задач выделениямаксимальных сильно связных подграфов.Цель изобретения - расширениефункциональных возможностей за счетразбиения графа на сильно связныеподграфы,На фиг.1 представлена структурнаясхема устройства; на фиг.2 - структурная схема блока записи; на фиг.3 -структурная схема блока управления.Устройство содержит матрицу1 Ь х ь и-число вершин графа моделейдуг, каждая из которых состоит изэлемента ИЛИ 2, триггера 33первого 4 и второго 5 элементов И,первую 6,6, и вторую 7,7 игруппы элементов ИЛИ, группы триггеров прямого 818и обратного99, отображений, элемент задержки 1 О, группу элементов И 111,11,блок 12 записи, блок 13 управления, генератор 14 тактовых импульсов. Блок 12 содержит дешифратор 3, группу элементов И 16 .16, группу регистров Блок 13 содержит первый 18, вто рой 19 и третий 20 элементы И, группу элементов И 2121, Т-триггер 22, триггер 23 работы, сдвигающий регистр 24124, счетчик 25, регистр 26126состояния,Входами блока 12 являются полюса 27, 28,28 з, 2929 входами 5 10 15 20 25 30 35 1и выходами блока 13 - полюса 30, 33, 3434, 35,355, 36.Первоначально в матрицу 1 заносится информация о топологии графа путем установки соответствующих триггеров 3 в единичное состояние. Триггер 3;6,3=1,н)определяется пересечением строки с номером , равным номеру начальной вершины моделируемой дуги, и столбца с номером д, равным номеру ее конечной вершины, Триггеры 8 и 9 находятся в нулевом состоянии.Устройство работает следующим образом.С подачей пускового импульса на вход 32 осуществляется сброс регистров 17 блока 2, счетчика 25 блока 13, установка в единичное состояние всех разрядов регистра 26 и установка в единичное состояние первого разряда регистра 24. Высокие потенциалы с единичных выходов всех разрядов регистра 26 через элемент И 19 устанавливают в единичное состояние триггер 23, единичное состояние которого определяет период работы всего устройства, Высокий потенциал с единичного выхода триггера 23 разрешает прохождение через элемент И 20 тактовых импульсов, поступающих с генератора 14 на вход 30 блока 13. Сигналы с выхода элемента И 20 поступают на счетный вход триггера 22. При наличии высокого потенциала на его единичном выходе выполняется цикл вьщеления максимального сильно связного подграфа из моделируемого графа, а при наличиивысокого потенциала на его инверсном выходе выполняется5 10 15 20 3 1 цикл записи номеров вершин вьщеленного подграфа в блок 12.Цикл вьщеления максимального силь но связного подграфа, содержащего -ю вершину х;, выполняется путем определения пересечения прямого л лГ+(хД и обратного г хД транзитивных замыканий. Выбор-й вершины осуществляется элементами И 21 блока 13. При совпадении всех трех высоких потенциалов на 1-м элементе И 21 сигнал с его выхода через 1-й выход 34 блока 13 подается на входы -х элементов ИЛИ 6,7 и далее - на единичные входы триггеров 8 и 9; единичное состояние 1-х триггеров 8 и 9 означает выбор -й вершины графа, для которой будет осуществляться вьщеление максимального сильно связного подграфа. 1Построение множества Гфх; осуществляется подачей высокого потенциала с единичного выхода триггера 8; на вторые входы элементов И 4 одноименной строки матрицы 1, за счет чего при наличии дуги из (-й вершины графа в-ю (1, = 1,), что соответствует единичному состоянию триггера 3;, высокий потенциал с выхода элемента И 4 через элемент ИЛИ 6 перебрасывает в единичное состояние триггер 8,;, с выхода которого высокий потенциал поступает на вторые входы элементов И 4-й строки матрицы 1, и так до тех пор, пока существует путь из"й вершины в очередную, и т.д. Вершинам образующим прямое транзитивное замыкание для с-й вершины графа, соответствуют единичные состояния триггеров 8. Построение множества Г 1 х; производится одновременно подачей высокого потенциала с выхода триггера 9; на вторые входы элемента И 5 одноименного столбца матрицы 1, за счет чего при наличии дуги в 1-ю вершину из к-й (1,к=1,и) высокий потенциал с выхода элемента ИЛИ 7 перебрасывает в единичное состояние триггер 9 к, с выхода которого высокий потенциал поступает на вторые входы элементов И 5 к-го столбца матрицы 1, и так до тех пор, пока имеются дуги иэ предшествующих вершин в данную. Вершинам, образующим обратное транзитивное замыкание для 1-й вершины графа, соответствует единичное состояние триггеров 9. 218392 4 Далее выполняется цикл записи.По приходу следующего тактового импульса на элемент И 20 блока 13 триггер 22 перебрасывается в противоположное состояниеЕдиничный сигнал с инверсного выхода триггера 22 поступает на регистр 24 блока 13 и осуществляет сдвиг единицы в следующий разряд, Этот же единичный сигнал с инверсного выхода триггера 22 поступает на выход 33 блока 13 и на вход счетчика 25 (причем на входе счетчика подключен элемент задержки, обеспечивающий задержку сигнала на время цикла записи). Значение счетчика 25 увеличивается на единицу, и новый адрес записи с вьпсодов 35 блока 13 поступает через вход 28 блока 12 на дешифратор 15. Сигнал с выхода дешифратора 15 подается на входы тех ,элементов И 16, номер строки которых совпадает с адресом записи. Сигнал записи с выхода 33 блока13 подается на вход элемента задержки 1 О и на третьи входы элементов И 11. Пересечение прямого Г 1 хД илобратного Г ( х;) транзитивных замыканий осуществляется совпадением вы.соких потенциалов на входах соответствующих элементов И 11, Вершины, входящие в выделенный максимальный сильно связный подграф, определяются высокими потенциалами на выходах одноименных элементов И 11. Эти сигЗ 5 налы поступают на входы 29 блока 12,которые соединены с первьщи входами элементов И 13. Запись информации осуществляется в тот регистр 17;, входные элементы И 16 которого откры ты сигналом с выхода дешифратора 15.Единичное значение 3 -го разряда регистра 17 показывает, что-я вершина графа входит в выделенный максимальный сильно связный подграф с но.мером 1 . Высокий потенциал с выхода-го элемента И 11 через элементы ИЛИ 2 осуществляет сброс триггеров 3-й строки и -го столбца матрицы 1, исключая тем самым 1 -ю вершину гра Фа из дальнейшего рассмотрения.Высокие потенциалы, появляющиесяна выходах тех элементов И 11, номера которых соответствуют вершинам исходного графа, выделенным в макси мальный сильно связный подграф, через входы 32 блока 13 поступанУг на входы установки в нуль соответствующих разрядов регистра 26. Установлен"ный в нулевое состояние-й разрядрегистра 26 указывает, что-я вершина исходного графа входит в один извыделенных подграфов.Задержанный элементом задержки 1 Осигнал записи поступает на нулевыевходы всех триггеров 8 и 9, осуществляя тем самым подготовку для последующей работы устройства. На этомцикл записи заканчивается,По следующему тактовому импульсутриггер 22 блока 13 устанавливаетсяв единичное состояние, и выполняетсяследующий цикл выделения максимального сильно связного подграфаПроцесс продолжается до тех пор, покавсе разряды регистра 26 блока 13 небудут установлены в нулевое состояние,При наличии высоких потенциаловна инверсных выходах всех разрядоврегистра 26 на выходе элемента И 18блока 13 формируется сигнал, которыйпоступает на вход установки в нультриггера 23 и сбрасывает его, Устройство прекращает работу,1 О 15 20 25 Формула изобретения Устройство для моделирования гра 30 фов, содержащее матрицу н н (ь -число вершин графа,1 моделей дуг, каждая из которых состоит из триггера, первого и второго элементов И, первую и вторую группы элементов ИЛИ, группу триггеров прямого и группу триггеров обратного отображения, группу элементов И, блок управления и генератор тактовых импульсов, причем в каждой модели дуги единичный выход триггера подключен к первым входам первого и второго элементов И, выходы первых элементов И каждой модели дуги-го столбца ( =1, )матрицы моделей дуг соединены с соответствующими входами 1-го элемента ИЛИ первой группы, выход каждого из которых подключен к единичному входу соответствующего триггера прямого отображения группы, выход которого соединен с вторыми входами первых элементов И 1 -й строки матрицы моделей дуг, выходы вторых элементов И каждой модели дуги ) -й строки 1,) =1 п)матрицы моделей дуг соединены , с соответствующими входами ) -го элемента ИЛИ второй группы, выход которого подключен к единичному входу соответствующеготриггера обратного отображения, выход которого соединен с вторыми входами вторых элементов И-го столбца матрицы моделей дуг, о т л и ч а ю щ е е с я тем,что, с целью расширения функциональных возможностей ус.тройства за счетрешения задачи разбиения графа насильно связные подграфы, в устройство введены элемент задержки, блокзаписи, состоящий иэ группы элементов И, группы регистров и дешифратора, блок управления содержит регистрсостояния, первый, второй и третий элементы И, группу элементов И, Т- триггер, триггер работы, сдвигающий регистр и счетчик, а в каждую модель дуги введен элемент ИЛИ, выход которого подключен к единичному входу триггера, в блоке управления разрядные выходы первой группы регистра состояния соединены с первыми входами элементов И группы и с входами второго элемента И, выход которого подключен к единичному входу триггера работы, разрядные выходы второй группы регистра состояния соединены с входами первого элемента И, выход которого подключен к нулевому входу триггера работы, выход которого соединен с первым входом третьего элемента И, выход третьего элемента И подключен к счетному входу Т-триггера, единичный выход которого соединен с вторыми входами элементов И группы, инверсный выход Т-триггера соединен со счетным входом счетчика и,с входом синхронизации сдвигающего регистра, разрядные выходы которого соединены с третьими входами элементов И группы, в блоке записи выходы дешифратора подключены к первым входам соответствующих элементов И группы, выходы которых соединены с соответствующими информационными входами первой группы регистров группы, выходытриггеров прямого отображения группы подключены к первым входам соответст.вующих элементов И группы, вторыевходы которых соединены с выходамисоответствующих триггеров обратногоотображения группы, выход ) -го элемента И группы подключен к первымвходам элементов ИЛИ моделей дуг 1-йстроки матрицы моделей дуг, вторымвходам элементов ИЛИ моделей дуг -го столбца матрицы моделей дуг, ксоответствующему информационному вхо.ду первой группы регистра состоянияи к вторым входам соответствующихэлементов И группы блока записи, инверсный выход Т-триггера блока управления соединен с третьими входамиэлементов И группы и входом элементазадержки, выход которого подключен кнулевым входам триггеров обратногоотображения группы и триггеров прямого отображения группы, выход генератора тактовых импульсов соединенс вторым входом третьего элемента Иблока управления, выходы элементовИ группы блока управления подключены к входам соответствующих элементовИЛИ первой и второй групп, выходысчетчика блока управления соединеныс соответствующими входами дешифратора блока записи, информационные входывторой группы регистров группы блоказаписи обьединены с установочным вщ"дом счетчика блока управления, с10 информационными входами второйгруппы регистра состояния блокауправления и с информационньмвходом первого разряда сдвигающего регистра блока управления 15 и яВляются пускоВым входом устройства./57 Тираж 673ИИПИ Государственного комите по делам изобретений и откр 113035, Москва, Ж, Раушск ПодписноСССРий