Устройство для операций над графами Советский патент 1991 года по МПК G06F15/173 

V

О 00

со

о

00

ел

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

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

На фиг. 1 представлена функциональная схема устройства; на фиг.2 - временная диаграмма работы блока синхронизации; на фиг.З - функциональная схема блока регистрации.

Устройство содержит (фиг. 1) блок 1 синхронизации, блок 2 регистрации, второй блок 3 задания матрицы смежности, второй блок А определения концевых вершин дуг, первый блок 5 задания матрицы смежности, первый блок б определения концевых вершин дуг, вход 7 начальной установки устройства, вход 8 пуска устройства, выход 9 блока 1 синхронизации, выходы 10 группы блока 1 синхронизации.

На фиг.З цифровые обозначения представляют матрицу из В х В элементов И 11, где В - количество вершин в графе, матрицу из В х В триггеров 12, информационные входы 13 первой группы, информационные входы 14 второй группы и вход 15 признака записи, причем вход установки в ноль блока 2 регистрации подключен к входам установки в ноль всех .триггеров 12 матрицы, М-й информационный вход 13 первой группы (М 1, ..., В) подключен к первым входам всех элементов И 11 М-й строки матрицы, К-й информационный вход14 второй группы подключен к вторым входам всех элементов И 11 К-ro столбца матрицы, вход 15 признака записи подключен к третьим входам всех элементов И 11 матрицы, выход К-го элемента И 11 М-й строки матрицы подключен к входу установки в единицу К-го триггера 12 М-й строки матрицы, выход которого является выходом признака наличия (К,М}-й дуги в произведении частей графа (не показан).

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

Пусть И и К - два графа с одним, и тем же множеством вершин В (т.е. Н и К - части одного графа). Тогда произведение графов Г К х Н есть граф с Г множествами Г(а) Н(К(а)), Геометрически это означает, что в произведении графов множество соседних с а вершин состоит из всех вершин, достижимых из а маршрутом длины 2, первое ребро которого принадлежит К, а второе Н. Перед началом работы обнуляют блок 2 регистрации, в блоки 3 и 5 задания матриц смежности заносится информация о топологии частей графа. На вход 8 устройства подают сигнал уровня логической 1, при этом блок 1 синхронизации формирует последовательность сигналов, предусмотренных временной диаграммой его работы. Сигнал уровня логической 1 появляется на первом выходе 10 блока синхронизации. При этом на выходе блока 4 формируется массив вершин, достижимых на К-й марш0 рутной длины 1 в первой части графа, на выходе блока 6 формируется массив вершин, достижимых из каждой вершины первого массива маршрутом длины 1 во второй части графа. Через время, достаточное для

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

0 длины 2 (т.е. дуги, исходящие из первой вершины произведения графов). Через время,- достаточное для регистрации, блок 1 синхронизации снимает сигнал уровня логический 1 со своего выхода 9 и первого

5 выхода 10 группы и формирует сигнал уровня логической 1 на втором выходе 10 группы. Далее устройство работает аналогично и после перебора всех вершин графа в блоке 2 регистрации формируется произведение

0 его частей.

Блок 2 регистрации работает следующим образом.

На вход установки в О блока 2 подают сигнал уровня логической 1. При этом все

5 триггеры 12 матрицы устанавливаются в О. На вход 15 признака записи подают сигнал уровня логической 1. При этом устанавливаются в 1 те триггеры 12, которые находятся на пересечении строк и столбцов,

0 выбранных единичными потенциалами на входах 13 и 14.

Формула изобретения Устройство для операций над графами, содержащее блок синхронизации, блок ре5 гистрации, первый блок задания матрицы смежности и первый блок определения концевых вершин дуг,, причем выход признака наличия (К,М}й дуги первого блока задания матрицы смежности (К 1В, М 1,.... В, где В

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

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

0

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

Изобретение относится к вычислительной технике и может быть использовано для выполнения математических операций над частями графа. Целью изобретения является расширение функциональных возможностей устройства за счет определения 8 произведения частей графа. Устройство для операций над графами содержит блок 1 синхронизации, блок 2 регистрации, первый блок 5 задания матрицы смежности, первый блок 6 определения концевых вершин дуг, второй блок 3 задания матрицы смежности, второй 4 блок определения концевых вершин дуг, вход 7 начальной установки устройства, вход 8 пуска устройства, выход 9 блока 1 синхронизации, выходы 10 группы блока 1 синхронизации. Перед началом работы обнуляют блок 2 регистрации, в блоки 3 и 5 задания матриц смежности заносят информацию о топологии частей графа. На вход 8 пуска устройства подают сигнал уровня логической единицы, при этом блок 1 синхро- низаЦии формирует последовательность сигналов, предусмотренных временной диаграммой его работы, под управлением которой в блоке 2 регистрации формируется произведение частей графа. 3 ил. w Ё

8

а

-Г}- .

Ji