Модель ребра графа

 

„„SU„„1064281 A

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

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

РЕСПУБЛИН

3(6В 6 06 F 15/20

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

Н ABTOPCHOMV СВИДЕТЕЛЬСТЕЙб

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЬП ИЙ (21) 3339283/18-24 (22) 23.09.81

;(46) 30.12.83. Бюл. Р 48 (72) В.В. Васильев, E.A. Ралдугин и Н.В. Федотов (71) Институт проблем моделирования в энергетике AH УССР (53) 681.333 (088.8) (56) 1. Авторское свидетельство СССР

Р 714402, кл. С 06 F 15/20, 1977.

2. Авторское свидетельство СССР

Р 708367, кл. G 06 5 7/48, 1977 I:прототип ) . (541 (57) МОДЕЛЬ РЕБРА ГРАФА, содер- жащая первый и второй регистры, первую и вторую схемы сравнения,два элемента И, информационные входы регистров объединены и являются группой информационных входов модели, выходы первого и второго регист ров соединены с первыми входами соответственно первой и второй схем сравнения, отличающаяся тем, что, с целью расширения функциональных возможностей путем обес-, печения моделирования оператора" отображения, в модель введены пер-:вая и вторая группы элементов И и группа элементов ИЛИ, причем выходы первого и второго регистров соединены с первыми входами элементов И. соответственно первой и второй групп, первые входы элементов ИЛИ группы соединены с выходами элементов И первой группы, а вторые вхо-, ды — с выходами элементов И второй группы, выходы элементов ИЛИ группы являются группой информационных выходов модели, вторые входы схем сравнения подключены к информационным входам регистров, выходы схем сравнения подключены соответственно к первым входам первого и второго элементов И, вторые входы которых объединены и являются синхронизирующим входом модели, выход первого элемента И соединен с объединенными вторыми входами элементов И второй . группы, выход второго элемента И соединен с объединенными вторыми входами элементов И первой группы,,а входы записи регистров являются

:первым и вторым управляющими- входами модели.

1064281

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

Известна модель ветви графа, содержащая счетчик импульсов, счетчик регенерации, триггера, элементы И, элемент НЕ и блок индикации, кото- 1О рая может использоваться при моделировании графов с циклическими участками (1 7 ..

Недостатком указанного устройства является низкое быстродействие, 15 обусловленное последовательным во времени процессом формирования связей моделируемого графа.

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

Недостатком известного устройства является невозможность моделирования оператора отображения.

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

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

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

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

Модель ребра содержит регистры

1 и 2, схемы 3 и 4 сравнения, элементы И 5 и 6, группы элементов

И 7 и 8, группу элементов ИЛИ 9.

Полюса 10-14 являются входами и выходами модели.

В качестве регистров 1 и 2 могут быть применены регистры с параллельным входом и выходом, причем занесение информации должно быть возможно только при наличии разрешающего сигнала на полюсах 10 или 11.

Схемы 3 и 4 сравнения предназначены для выдачи сигнала сравнения в случае, если код, хранимый в одном из регистров 1 или 2, совпадает с кодом, установленным на входных полюсах.

Входными полюсами 13 модель ребра подключена к информационному входу устройства, а выходными 14 к информационному выходу. Количество шин К .в магистралях входа и выхода устройства зависит от размерности моделируемого графа и должно быть равно

К г012м где Й вЂ” количество узлов.

Каждая шина магистрали служит для передачи одного разряда кода номера узла графа. Первая магистраль, с которой соединены входные полюса моделей ребер, служит для передачи кода узла, для которого моделируется оператор отображения. Вторая магистраль, с которой соединены выходные полюса всех моделей ребер, передает коды узлов, которые являются отображением.

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

1064281

Составитель С. Назаров

Техред Ж. Кастелевич

Редактор A.Âëàñåíêî

Корректор Г.Р шетник

Заказ 10533/50

Тираж 70б Подписное

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

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

Филиал ППП "Патент", г. Ужгород, ул. Проектная-,.4

Предварительно в регистры моделей ребер по первой магистрали заносятся коды номеров узлов, которые связывают каждое ребро графа. Осущест» вляется это с помощью сигналов записи на полюсах 10 и 11.

В процессе. моделирования на первую магистраль поступает код номера узла,для которого необходимо выпол- . нить операцию отображения. Схемы

3 и 4 сравнения сравнивают .эту информацию с содержимым регистров 1 и 2. Если сравнение произошло, то выходной сигнал одной иэ схем сравнения проходит через один из элементов И 5 или б при наличии сигнала на полюсе 12 и разрешает выдачу кода, хранимого в одном из регистров, через группу элементов И и

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

Сигнал на полюсе 12 предназначен для разнесения во времени моментов выдачи кодов на выходные полюса сразу от нескольких моделей ребер в g случае, когда узел, для которого выполняется операция отображения, имеет связь с несколькими узлами.

Использование изобретения позволяет сократить время моделирования путем распараллеливания решения при реализации оператора отображения,