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

СОЮЗ СОВЕТСНИХСОЦИАЛИСТИЧЕСНИХРЕСПУБЛИН 6 И КОМИТЕТ СССРТЕНИЙ ИОТНРЫТИЙ ОСУДАРСТВЕНН ПО ДЕЛАМ ИЗОБ Е ИЗОБРЕТЕНИЯСВИДЕТЕЛЬСТВУ ИСА АВТОРСК(57) Изобретениелительной техник ДЛЯ МОДЕЛИРОВАН ычисотносится ол может ования петель ыть тевь позв ано для иссл без цикловяе ое количе опред входя ить ую вершиит матрищих втво соей дуг выхо ну графа. Устроисцу 1 формирователкоторых содержит из емент,ЯО 13761) 4 6 06 Р 15/20 И 3, группу из Р элементов ИЛИ 4,где Р - количество вершин в графе,группу из Р элементов И 5, группуиз Р счетчиков 6, группу из Р схемсравнения, вторую группу из Р счетчиков 9, первый счетчик 10, первый элемент И 11, генератор 12 тактовыхимпульсов, триггер 13, второй элемент И 14, второй счетчик 15, дешифратор 16, вход 17 пуска устройства,выход 18 признака окончания работы,первую группу сумматоров 19, вторуюгруппу сумматоров 20 и группу блоков 21 элементов И. Введение в базовое устройство группы сумматоров 19позволяет определять количество дуг,входящих в каждую вершину графа, авведение группы блоков 21 элементовИ и группы сумматоров 20 позволяетопределять значение суммарного количества входящих и выходящих дуг длякаждой вершины графа. 1 ил.Изобретение относится к вычислительной технике, может быть использовано при исследовании сетевых графов и является усовершенствованием изобретения по авт.св. Бф 959090.Цель изобретения - расширение функциональных возможностей устройства за счет определения суммарного количества входящих и выходящих дуг для каждой вершины моделируемого графа.На чертеже представлена функциональная схема устройства.Устройство содержит матрицу 1 формирователей дуг, каждый из которых содержит триггер 2 и элемент И 3, группу из Р элементов ИЛИ 4, где Р - количество вершин в графе, группу из Р элементов И 5, группу из Р счетчиков 6, группу из Р схем 7 сравнения, группу из Р элементов ИЛИ 8,вторую группу из Р счетчиков 9,первый счетчик 10, первый элементИ 11,генератор 12 тактовых импульсов, триггер 13,второй эле мент И 14,второй счетчик 15,дешифратор 16, вход 17 пуска устройства, выход 18 признака окончания работы, первую группу из Р сумматоров 19, вторую группу из Р сумматоров 20 и группу из 30 Р блоков 21 элементов И.Устройство работает следующим образом. В триггеры 2 матрицы 1 заноситсяинформация о топологии моделируемогографа. При этом триггеры 2, .соответствующие ветвям графа, устанавливаются в единичное состояние согласноматрице смежности графа. 40После занесения исходной информации на выходах элементов ИЛИ 4,объединяющих выходы триггеров 2 в столбцах, соответствующих начальным узламмоделируемого графа, будут низкиепотенциалы, так как в однонаправленномграфе без циклов и петель начальныеузлы не содержат входящих ветвей.Счетчики 6 и 9, 10 и 15 устанавливаются в нулевое состояние,50После пуска устройства триггер 13находится в нулевом состоянии и наего инверсном выходе присутствуетвысокий потенциал. Поэтому импульсыс выхода генератора 12 через открытый55элемент И 14 поступают на вход счетчика 15Благодаря этому на выходе де;шифратора 16 поочередно возбуждаютсявыхеды.Ф,Каждый выход дешифратора 16 подключен к первому входу элемента И 3 одноименного столбца матрицы. Поэтому с приходом на вход счетчика 15 первого импульса возбуждается первый выход дешифратора 16 и через элементы ИЛИ.8 на входы счетчиков 9, соответствующих вершинам, связанным с первой вершиной, поступают импульсы. В то же время сигналы с выходов элементов И 3 первого столбца матрицы поступают на входы первого сумматора 19, в котором формируется количество входящих в первую вершину. дуг. Подобным образом процесс повторяется для всех вершин моделируемого графа. Сигнал переполнения счетчика 15 свидетельствует о завершении этапа определения количества дуг, выходящих из данной вершины. Этот же сигнал разрешает прохождение через элементы И блоков 21 на вторые входы сумматоров 20 значений количества дуг, выходящих из вершин моделируемого графа,. обеспечивая тем самым формирование на сумматорах значений суммарного количества дуг,входящих и выкодящих из каждой вершины моделируемого графа.Кроме того, сигнал переполнения счетчика 15 поступает на вход триггера 13, который переходит в единичное состояние, после чего импульсы с выхода генератора 12 начинают поступать через элемент И 11 на входы элементов И 5 и вход счетчика 10 - начинается этап распределения вершин графа по рангам. При этом импульсы не поступают на входы счетчиков 6 тех столбцов, все триггеры которых находятся в нулевом состоянии. Содержимое счетчиков 6 поступает на первые .входы одноименных схем 7 сравнения, на другие входы которых поступает информация.с выхода счетчика 10.При несовпадении показаний счетчиков 6 и 10 схемы 7 вырабатывают импульс, который устанавливает в нулевое состояние триггеры 2 формирователей дуг строки с номером, равным номеру столбца, в схеме сравнения которого не произошло сравнение.Вычислительный процесс продолжается до тех пор, пока на выходе 18 устройства не появится сигнал окончания моделирования, который свидетельствует о том, что все вершины моделируемого графа распределены по рангам. Иаксимальное число последоЗаказ 789/48 Тираж 704 ПодписноеВНИИПИ Государственного комитета СССРпо делам изобретений и открытий113035, Москва, Ж, Раушская наб., д. 4/5 Производственно-полиграфическое предприятие, г. Ужгород, ул. Проектная, 4 нательных шагов при работе устройства не превышает 2 Р, при этом число импульсов, зафиксированное в счетчиках 6, соответствует номеру ранга каждой вершины.5 формула изобретенияУстройство для моделирования сетевых графов,по авт.св. У 959090, о т - 10 л и ч а ю щ е е с я тем, что, с целью расширения функциональных возможностей устройства за счет определения суммарного количества входящих и выходящих дуг для каждой вершины моделируемого графа, в него введены две группы по Р сумматоров,где Р - количество вершин в графе, игруппа из Р блоков элементов И, причем выход К-го элемента И (К=1Р),формирователя дуги М-й строки матрицы подключен квходу М-го слагаемогоК-го сумматора первой группы, выходкоторого подключен к входу первогослагаемого К-го сумматора второйгруппы, выход М-го счетчика второйгруппы подключен к первому входу М-гоблока элементов И группы, выход которого подключен к входу второго слагаемого М-го сумматора второй группы,выход признака переполнения второгосчетчика подключен к второму входувсех блоков элементов И группы.