Модель ребра графа Советский патент 1983 года по МПК G06F15/173 G06G7/122 

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

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

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

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

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

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

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

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

Модель ребра содержит регистры 1 и 2, схемы 3 и 4 сравнения, элеенты И 5 и б, группы элементов И 7 и 8, группу элементов ИЛИ 9. Полюса 10-14 являются входами и выходами модели.

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

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

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

где М - количество узлов.

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

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

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

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

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

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

0 выполняется операция отображения, имеет связь с несколькими узлами.

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

5 реализации оператора отображения.

1дн