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

 

Изобретение относится к вычислительной технике, может быть испольt зовано для исследования сетевых графов без циклов ипетель и позволяет определить суммарное количество дуг, входящих и выходящих в каждую вершину графа. Устройство содержит матрицу 1 формирователей дуг, каждый из которых содержит триггер 2 и.элемент .ИЗ, группу из Р элементов ИЛИ 4, где Р - количество вершин в графе, группу из Р элементов И 5, группу из Р счетчиков 6, группу из Р схем сравнения, вторую группу из Р счетчиков 9, первый счетчик 10, первый элемент И 11, генератор 12 тактовых импульсов, триггер 13, второй элемент И 14, второй счетчик 15, дешифратор 16, вход 17 пуска устройства, выход 18 признака окончания работы, первую группу сумматоров 19, вторую группу сумматоров 20 и группу блоков 21 элементов И. Введение в базовое устройство группы сумматоров 19 позволяет определять количество дуг, входящих в каждую вершину графа, а введение группы блоков 21 элементов И и группы сумматоров 20 позволяет определять значение суммарного количества входящих и выходящих дуг для каждой вершины графа. 1 ил. Q Ф «Л со о о ;о О) ТЧ)

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

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

РЕСПУБЛИН ф ; а » р Я к

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

И ASTGPCHO5AY СВИДЕТЕЛЬСТВУ

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИЙ (61) 959090 (21) 4105333/24-24 (22) 03.06.86 .(46) 23.02.88. Бюл. У 7. (72) M.Ï. Медиченко, Г.В. Буряк, Г.П. Азбукин, С.В. Артюшенко, Г.А. Кочуевский и В.Н. 1Троскуров (53) 681.333(088.8) (56) Авторское свидетельство СССР

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

СЕТЕВЫХ ГРАФОВ (57) Изобретение относится к вычис-! лительной технике может быть испольЭ зовано для исследования сетевых графов без циклов и.петель и позволяет определить суммарное количество дуг, входящих и выходящих в каждую вершину графа. Устройство содержит матрицу 1 формирователей дуг, каждый из которых содержит триггер .2 кэлемент

„„Я0„„1376096 А 2 (51) 4 G 06 F 15/20

И 3, группу из Р элементов ИЛИ 4, где P — количество вершин в графе, группу из P элементов И 5, группу из Р счетчиков 6, группу из Р схем сравнения, вторую группу из P счетчиков 9, первый счетчик 10, первый элемент И 11, генератор 12 тактовых импульсов, триггер 13, второй элемент И 14, второй счетчик 15, дешифратор 16, вход 17 пуска устройства, выход 18 признака окончания работы, первую группу сумматоров 19, вторую группу сумматоров 20 и группу блоков 21 элементов И. Введение в базовое устройство группы сумматоров 19 позволяет определять количество дуг, входящих в каждую вершину графа, а введение группы блоков 21 элементов

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

1376096

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

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

На чертеже представлена функциональная схема устройства.

Устройство содержит матрицу 1 формирователей дуг, каждый из которых содержит триггер 2 и элемент И 3, группу из Р элементов ИЛИ 4, где Р— количество вершин в графе, группу из

Р элементов И 5, группу из Р счетчиков 6, группу из P схем 7 сравнения, группу из P элементов ИЛИ 8,вторую группу из Р счетчиков 9,первый счетчик 10, первый элементИ 11,генератор 12 тактовых импульсов, триггер 13,второй эле- 25 мент И14,второй счетчик 15,дешифратор

16, вход 17 пуска устройства, выход

18 признака окончания работы, первую группу из Р сумматоров 19, вторую группу из Р сумматоров 20 и группу из 30

Р блоков 21 элементов И.

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

В триггеры 2 матрицы 1 заносится информация о топологии моделируемого графа. При этом триггеры 2, .соответствующие ветвям графа, устанавливаются в единичное состояние согласно матрице смежности графа. 40

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

Счетчики 6 и 9, 10 и 15 устанавливаются в нулевое состояние.

После пуска устройства триггер 13 находится в нулевом состоянии и на его инверсном выходе присутствует высокий потенциал. Поэтому импульсы с выхода генератора 12 через открытый

55 элемент И t4 поступают на вход счетчи. ка 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 устройства не появится сигнал окончания моделирования, который свидетельствует о том, что все вершины моделируемого графа распределены по рангам. Иаксимальное число последо1376096

Составитель А. Мишин

Редактор С. Патрушева Техред <.Кравчук Корректор С. Черни

Заказ 789/48 Тираж 704 Подписное

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

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

Производственно-полиграфическое предприятие, г. Ужгород, ул. Проектная, 4 нательных шагов при работе устройства не превышает 2 P при этом число импульсов, зафиксированное в счетчиках 6, соответствует номеру ранга каждой вершины.

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

Устройство для моделирования сетевых графов.по авт.св. У 959090, о т - 10 л и ч а ю ш е е с я тем, что, с целью расширения функциональных возможностей устройства за счет определения суммарного количества входящих и выходящих дуг для каждой вершины моделируемого графа, в него введены две группы по Р сумматоров,где

P — - количество вершин в графе, и

O группа из Р блоков элементов И, причем выход К-го элемента И (К=1,...,P) ,формирователя дуги М-й строки матрицы подключен к входу М-го слагаемого

К-ro сумматора первой группы, выход которого подключен к входу первого слагаемого К-го сумматора второй группы, выход М-го счетчика второй группы подключен к первому входу М-го блока элементов И группы, выход которого подключен к входу второго слагаемого М-го сумматора второй группы, выход признака переполнения второго счетчика подключен к второму входу всех блоков элементов И группы.