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

 

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

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

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

РЕСПУБЛИК (я)ю G 06 F 15/419

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

ПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМ

ПРИ ГКНТ СССР

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

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (21) 4441178/24 (22) 14.06,88 (46) 07.10.9.1. Бюл. М 37 (71) Киевский политехнический институт им.50-летия Великой Октябрьской социалистической революции (72) О.Н.Костюк, С.Ю.Бездежский и Д.В.Табачников (53) 681.333(088;8) (56) Авторское свидетельство СССР

ЬЬ 1174937, кл. G 06 F 15/20, 1983.

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

М 1587535, кл, 6 06 F 15/20, 1988, (54)УСТРОЙСТВО ДЛЯ ОПЕРАЦИЙ НАД

ГРАФАМИ (57) Изобретение относится к вычислительной технике и может быть использовано для выполнения математических операций над частями графа. Целью изобретения является расширение функциональных возможностей устройства за счет определения

„„Ы „„1683035 Al произведения частей графа. Устройство для операций над графами содержит блок 1 синхронизации, блок 2 регистрации, первый блок 5 задания матрицы смежности, первый блок 6 определения концевых вершин дуг, второй блок 3 задания матрицы смежности, второй 4 блок определения концевых вершин дуг, вход 7 начальной установки устройства, вход 8 пуска устройства, выход 9 блока

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

1683035

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

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

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

На фиг.3 цифровые обозначения представляют матрицу из В х В элементов И 11, где  — количество вершин в графе, матрицу из В х В триггеров 12, информационные входы 13 первой группы, информационные входы 14 второй группы и вход 15 признака записи, причем вход установки в ноль блока

2 регистрации подключен к входам установки в ноль всех триггеров 12 матрицы, M-й информационнйй вход 13 первой группы (M = 1, ..., В) подключен к первым входам всех элементов И 11 М-й строки матрицы, К-й информационный вход14 второй группы подключен к вторым входам всех элементов

И 11 -ro столбца матрицы, вход 15 признака записи подключен к третьим входам всех элементов И 11 матрицы, выход К-го элемента И 11 M-й строки матрицы подключен к входу установки в единицу -ro триггера

12 M-й строки матрицы, выход которого является выходом признака наличия (К,М)-й дуги в произведении частей графа (не показан).

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

Пусть Н и К вЂ” два графа с одним, и тем же множеством вершин В (т.е..Н и К вЂ” части одного графа). Тогда произведение графов

Г = К х Н есть граф с Г множествами Г(а)=Н(К(а)), Геометрически это означает, что в произведении графов множество соседних с а вершин состоит иэ всех вершин, достижимых из а маршрутом длины 2, первое ребро которого принадлежит К, а второе Н, Перед началом работы обнуляют блок 2 регистрации, в блоки 3 и 5 задания матриц смежности заносится информация о топо10

norw частей графа. На вход 8 устройства подают сигнал уровня логической "1", при этом блок 1 синхронизации формирует последовательность сигналов, предусмотренных временной диаграммой его работы.

Сигнал уровня логической "1" появляется на первом выходе 10 блока синхронизации.

При этом на выходе блока 4 формируется массив вершин, достижимых на К-й маршрутной длины 1 в первой части графа, на выходе блока 6 формируется массив вершин, достижимых иэ каждой вершины первого массива маршрутом длины 1 Во второй части графа. Через время, достаточное для окончания указанных операций, блок 1 синхронизации формирует сигнал уровня логической "1" на выходе 9. При этом блок 2 регистрации фиксирует номера вершин, достижимых из первой вершины маршрутом длины 2 (т.е. дуги, исходящие из первой вершины произведения графов), Через время,. достаточное для регистрации, блок 1 синхронизации снимает сигнал уровня логический "1" со своего выхода 9 и первого выхода 10 группы и формирует сигнал уровня логической "1" на втором выходе 10 группы. Далее устройство работает аналогично и после перебора всех вершин графа в блоке

2 регистрации формируется произведение его частей.

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

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

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

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

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

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

1683035 м .

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

Техред М.Моргентал

Редактор М.Бланар

Корректор А.Осауленко

Заказ 3415 Тираж Подписное

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

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

Производственно-издательский комбинат "Патент", г. Ужгород, ул.Гагарина, 101 блока регистрации, отл и чаю щееся тем, что, с целью расширения функциональных возможностей устройства за.счет определения произведения частей. графа, в него введены второй блок задания матрицы смежности и второй блок определения концевых вершин дуг, причем выход признака наличия (К,М)-й дуги второго блока задания матрицы смежности подключен к одноименному входу второго блока определения концевых вершин дуг., выход признака принадлежности M-й вершины массиву концевых которого подключен к входу опроса M-й начальной вершины первого блока опреде5 ления концевых вершин дуг, К-й выход группы блока синхронизации подключен к К-му информационному входу второй группы блока регистрации и входу опроса К-й начальной вершины второго блока определе10 ния концевых вершин дуг,