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

01 ОЗ СОВЕТСКИХ ОЦИАЛИСТИЧЕСНИХРЕСПУБЛИК С 06 Г 5/20 ТЕЛЬСТВУ,Р 47С.Л.Вилк ельство СС 15/20, 198 ьство СССР 15/20, 198(54) УСТРОЙСТВГРАФОВ ОДЕЛИРОВАН 1 зобретение относ ислительной техн спользовано для тся к обласки и может ти в быть ения зад Ф ГОСУДАРСТНЕННЫИ КОМИТЕТ СССР ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИ Д ВТОРСНОМУ С(56) Авторское,свидеКф 913389, кл, С 06 ГАвторское свидетеР 1218392, кл, С 06 Р 1%ЯОШ) 1 27 выделения максимальных сильно связных подграФов, Целью изобретения является повышение быстродействияустройства. Это достигается введением в блок управления второй группыэлементов И вместо сдвигаюцего регистра. Устройство для моделирования графов содержит матрицу и хп моделей дуг, две группы элементов ИЛИ,группу элементов И, группу триггеровпрямого отображения, группу триггеров обратного отображения, элементзадержки, блок записи, блок управления и генератор тактовых имгульсов.Изобретение относится к вычисли тельной технике и может быть использовано для решения задач выделениямаксимальных сильно связных подграФов.Целью изобретения является повышение быстродействия устройстваЦель достигается за счет того,что исследование графа производитсяпо гибкому циклу работы (длительность гибкого цикла работы определяется соотношением Т = 2 шТц, гдеш -количество максимальных сильно связных подграфов в графе, ш п).На Фиг,1 представлена структурная схема устройства; на Фиг,2 -структурная схема блока записи; нафиг.З - структурная схема блока управления.Устройство содержит матрицу 1и хп (г 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 в единичное состояние. .риггер 311 (1,З=11 п) определяется пересечением строки с номером , равным номеру 5 10 15 20 25 30 35 40 45 50 начальной вершины моделируемой дуги и столбца с номером 1, равным номе" ру ее конечной вергцины, Триггеры 8 и 9 находятся в нулевом состоянии.С подачей пускового импульса на второй вход 32 блока управления (БУ), являющегося входом запуска устройства, осуществляется сброс регистров 17 блока 12 записи, счетчика 25 блока 13 управления и установка в единичное состояние всех разрядов регистра 26 состояния, Высокие потенциалы с единичных выходов всех разрядов регистра 26 состояния через элемент И 19 устанавливают в единичное состояние триггер 23 работы, единичное состояние которого определяет период работы всего устройства,Высокий потенциал с прямого выхода триггера 23 работы разрешает прохождение через элемент И 20 тактовых импульсов, поступающих с генератора 14 на вход ЗО блока 13, Сигналы с выхода элемента И 20 поступают на счетный вход триггера 22, При наличии высокого потенциала на его прямом выходе выполняется цикл выделения очередного максимального сильно связанного подграфа из моделируемого графа, а при наличии высокого потенциала на его инверсном выходе выполняется цикл записи номеров вершин выделенного подграфа в блок 12 записи.Цикл выделения максимального сильно связного подграфа, содержащего -ю вершину.х;, выполняется путем пересечения прямого1 х; и обратил гного Г хтранзитивных замыканий, Выбор 1-й вершины осуществляется элементами И 21 блока 13, Еспи х-и элемент И 21 (в начале работы первый элемент И 21) имеет на обоих входах высокий потенциал, то сигнал с его выхода через 1.-й выход 34 блока 13 . подается на входы 1.-х элементов ИЛИ 6 и 7 и далее на единичные входы триггеров 8, и 9;, единичное состояние 1.-х триггеров 8 и 9 означает вы; бор 1-й вершины графа, для которой будет осуществляться выделение максимального сильно связного подграФа. л+.Построение множества Г 1 х;) осуществляется подачей высокого потенциала с единичного выхода триггера 8, на вторые вхоДы элементов И 4 одноименной строки матрицы 1,за счет чего при наличии дуги из 1-й вершины графа в 1-ю (1.,= 1,и), что соответствует единичному состоянию триггера 3; , высокий потенциалрс выхода элемента И 4 через элемент ИЛИ 6 перебрасывает в единичное состояние триггер 8, с выхода которого высокий потенцйал поступает на вторые входы элементов И 4-й,1 строки матрицы 1, и так до .тех пор, пока существует путь из 1-и вершины в очередную и т.д. Вершинам, образующим прямое транзитивное замыкание для -й вершины графа, соответствуют единичные состояния триггеров 8.построение множества Г х;1 производится одновременно подачей высокого потенциала с выхода триггера 9 на вторые входы элементов И 5 одноименного столбца матрицы 1, за счет чего при наличии дуги в х-ю вершину из 1 с-й (1, 1 с=1, п) высокий потенциал с выхода элемента ИЛИ 7 перебрасывает в единичное состояние триггер 9, с выхода которого высокий потенциал поступает на вторые входы элементов И 5 1 с-го столбца матрицы 1, и так до тех пор, пока имеются дуги из предшествующих вершин в данную. Вершинам, образующим обратное транзитивное замыкание для -й вершины графа, соответствуют единичные состояния триггеров 9. Далее выполняется цикл записи, По приходу следующего тактового импульса на элемент И 20 блока 13 триггер 22 перебрасывается в противоположное состояние. Сигнал эапци с инверсного выхода триггера 22 через выход 33 блока 13 подается на вход элемента 10 задержки и на третьи входы элементов И 11. Пересечение прямого и обратного транзитивных замыканий осуществляется совпадением высоких потенциалов на входах соответствующих элементов И 11, Вершины, входящие в выделенный максимальный сильно связный подграф, определяются высокими потенциалами на выходах одноименных элементов И 11.Эти сигналы поступают на группу инФормационных входов 29 блока 12, которая соединена с первыми входами соответствующих элементов И группы 6. Запись информации осуществляется в тот регистр 17 (1=1, ш, где ш - количество максимальных сильно связ 78880 4ных подграфов в граФе), входные элементы И 16 которого открыты сигналомс выхода дешифратора 15 (в началеработы в первый регистр 17). Единичное значение 1 -го разряда регистра 17 показывает, что 1-я вершинаграфа входит в выделенньп максимальный сильно связньп подграф с номером 1.О Высокий потенциал с выхода 1-гоэлемента И 11 через элементы ИЛИ 2.осуществляет сброс триггеров 3 1-йстроки и -го столбца матрицы 1,исклочая тем самым 1-ю вершину гра фа из дальнейшего рассмотрения. Высокие потенциалы, появляющиеся на выходах тех элементов И 11, номера которых соответствуют вершинам исходного графа, выделенным в максимальныйсильно связный подграф, через группувходов 31 блока 13 поступают на входы установки в нуль соответствующихразрядов регистра 26. УстановленньпЧв нулевое состояние 1-й разряд ре гистра 26 указывает,что -я вершинаисходного графа входит в один нз выделенных подграфов. Задержанный элементом 10 задержки сигнал записи поступает на нуяевые входы всех триг геров 8 и 9, осуществляя тем самым .подготовку для последующей работыустройства. Единичный сигнал синверсного выхода триггера 22 поступаеттакже на вход счетчика 25 (причем навходе счетчика подключен элемент задержки, обеспечнвающии задержку сигнал на время цикла записи 7 и увеличивает значение счетчика на единицу,новый адрес записи с второй группы 40 выходов 35 блока 13 через группуадресных вхсдов 28 блока 12 поступает на дешифратор 15. Сигнал с выхода дешифратора 15 подается на входы тех элементов И 16, номер строкикоторых совпадает с адресом записи.На этом цикл записи кончается.По следующему тактовому импульсутриггер 22 блока 13 устанавливаетсяв единичное состояние и выполняется 50 следующий цикл выделения максимального сильно связного подграфа. Приэтом так как высокий потенциал появляется на выходе только того 1.-гоэлемента И 21, для которого соответ ствующий элемент И 24 имеет па выходетакже высокий потенциал очередной1максимальный сильно связный подграфбудет выделяться для вершины х , невошедшей в ранее выделенные подгра 1278880фы и имеющей наименьший порядковыйномер.1Процесс продолжается до тех пор,пока все разряды регистра 26 блока13 не будут установлены в нулевоесостояние. При наличии высоких потенциалов ца инверсных выходах всехразрядов регистра 2 б на выходе элемента И 18 блока 13 Формируется сигнал, который поступает на вход установки в нуль триггера 23 и сбрасывает его, устройство прекращает работу,Формула изобретенияУстройство для моделирования графов, содержащее матрицу и х и (и - количество вершин графа) моделей дуг, каждая из которых состоит из триггера, первого и второго элементов И, элемента ИЛИ, первую и вторую группы элементов ИЛИ, группу триггеров прямого и группу триггеров обратного отображений, группу элементов И, элемент задержки, генератор тактовых импульсов, блок записи, состоящий из и групп элементов И, группы регистров и дешифратара, блок . управления, состоящий из регистра состояния, первого, второго и третьего элементов И, первой группы элементов И, Т-триггера, триггера рабаты и счетчика, причем в каждой модели дуги выход элемента ИЛИ подключей к входу установки в "1" триггера, прямой выход которого соединен с первыми входами первого и второго элементов И, выход первого элемента И каждой 1-й модели дуги 1-га столбца (х, 1=1,п) матрицы моделей дуг соединен с -м входам 3-го элемента ИЛИ первой группы, выход которого подключен к входу установки в "1" 3 -га триггера прямого отображения группы, выход которого соединен с вторыми входами первых элементов И -и строки матрицы моделей дуг (х=3) и первым входом 1-го элемента И группы, выход второго элемента И каждой 3-й модели дуги -й строки матрицы моделей дуг соединен с ,-м входам -га элемента ИЛИ второй группы, выход которого подключен к входу установки в "1" 1.-га триггераабра ного отображения группы, выход которого соединен с вторыми входами вторых элементов И 3-га столбца матрицы моделей дуг (3=1.) и вторымвходом одноименного элемента И группы, в блоке управления разрядные выходы первой группы выходов регистрасостояния соединены с одноименнымивходами второго элемента И блокауправления, выход которого подключен к входу установки в "1" триггера работы, разрядные выходы второйгруппы выходов регистра состояния соединены с одноименными входами первого элемента И блока управления,выход которого подключен к входу установки в 0" триггера работы, выходкоторого соединен с первым входомтретьего элемента И блока управления, выход которого подключен к счетному входу Т-триггера, прямой выходкоторого соединен с первыми входами элементов И первой группы блокауправления, инверсный выход Т-триггера соединен со счетным входом счетчика, с входом элемента задержки и стретьими входами элементов И группы,выход каждого ь-го элемента И группыподключен к х-му входу первой груп -пы информационных входов регистрасостояний, второй вход третьего элемента И блока управления подключенк выходу генератора тактовых импульсов, установочный вход счетчика, входы второй группы информационных входов регистра состояний и первые груп"пы информационных входов всех регистров группы блока записи объедицены и являются входом запуска устройства,выход каждого -га элемента И псрвой группы блока управления подключен к (и+1)-м входам -х элементов ИЛИ первой и второй групп, выход элемента задержки подключен к входам установки в цО" триггеров обратного отображения группы и триггеров прямого отображения группы, выход з.-го элемента И группы подключен к первым входам элементов ИЛИ иоделей дуг -й строки матрицы моделейдуг и к вторым входам элементов ИЛИмоделей дуг -го столбца матрицы моделей дуг, выход -го элемента И5 10 15 20 25 30 группы подключен к первому, входу -го элемента И каждой из групп блока записи, вторые входы элементов И -й группы блока записи объединены и подключены к 1.-му выходу дешифратора, группа входов которого подключена к группе выходов счетчика, выход каждого 3-го элемента И -й группы блока записи подключен к 1-му входу второй группыинформационных входов .-го регистрагруппы блока записи, о т л и ч а ю -щ е е с я тем, что, с целью повышения быстродействия, в блок управления.введена вторая группа элементов И, причем д-й разрядный выходпервой группы выходов регистра состояния, кроме первого разрядного выхода, соединен с первым входом -гоэлемента И второй группы блока управления, выход которого подключен к 78880 8второму входу (х+1)-го элемента Ипервой группы блока управления, первый разрядный выход первой группывыходов регистра состояния соединен 5 с вторым входом первого элемента Ипервой группы блока управления, рачрядпые выходы второй группы выходоврегистра состояния, кроме последнего, подключены к соответствующим входам элементов И второй группы блокауправленияизводственно - полн гратческое предприятие, г. Ужгород, ул. Проек Гираж осудлрстье лам изсбре 11 оскна, 1 ного коиит ений и отк 5, Рауьска