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

(55 О 06 Р САНИЕ ИЗОБРЕТЕНИЯ ЕТЕЛЬСТВУ АВТОРСКОМУ нсти лилительано для ций над являет- можно елен ия ГОСУДАРСТВЕННЫЙ КОМИТЕТПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМПРИ ГКНТ СССР Д 21) 4441178/24Д 22) 14.06,88Д 46) 07.10.9.1. Бюл. М 37д 71) Киевский политехнический иим.50-летия Великой Октябрьской сстической революциид 72) О.Н.Костюк, С.Ю.Бездежский ибачниковД 53) 681.333 Д 088;8)Д 56) Авторское свидетельство СССРВ 1174937, кл. 6 06 Р 15/20, 1983.Авторское свидетельство СССРМ 1587535, кл, 6 06 Р 15/20, 1988,Д 54)УСТРОЙСТВО ДЛЯ ОПЕРАЦИГРАФАМИД 57) Изобретение относится к вычисной технике и может быть использоввыполнения математических операчастями графа. Целью изобретенияся расширение функциональных возстей устройства за счет опред произведения частей графа. Устройство для операций над графами содержит блок 1 синхронизации, блок 2 регистрации, первый блок 5 задания матрицы смежности, первый блок 6 определения концевых вершин дуг, второй блок 3 задания матрицы смежности, второй 4 блок определения концевых вершин дуг, вход 7 начальной установки устройства, вход 8 пуска устройства, выход 9 блока 1 синхронизации, выходы 10 группы блока 1 синхронизации. Перед началом работы обнуляют блок 2 регистрации, в блоки 3 и 5 задания матриц смежности заносят информацию о топологии частей графа. На вход 8 пуска устройства подают сигнал уровня логической единицы, при этом блок 1 синхронизации формирует последовательность щ сигналов, предусмотренных временной диаграммой его работы, под.управлением которой в блоке 2 регистрации формируется произведение частей графа. 3 ил.Изобретение относится к вычислительной технике и может быть использовано для выполнения математических операций над .частями графа.Целью изобретения является расширение функциональных возможностей устройства за счет определения произведения частей графа.На фиг,1 представлена функциональная схема устройства; на фиг.2 - временная диаграмма работы блока синхронизации; на фиг,З - функциональная схема блока регистрации,Устройство еодержит (фиг.1) блок 1 синхронизации, блок 2 регистрации, второй блок 3 задания матрицы смежности, второй блок 4 определения концевых вершин дуг, первый блок 5 задания матрицы смежности, первый блок 6 определения концевых вершин дуг, вход 7 начальной установкиустройства, вход 8 пуска устройства, выход 9 блока 1 синхронизации, выходы 10 группы блока 1 синхронизации.На фиг,З цифровые обозначения представляют матрицу из В х В элементов И 11, где В - количество вершин в графе, матрицу из В х В триггеров 12, информационные входы 13 первой группы, информационные входы 14 второй группы и вход 15 признака записи, причем вход установки в ноль блока 2 регистрации подключен к входам установки в ноль всех, триггеров 12 матрицы, М-й информационнйй вход 13 первой группы (М = 1, , В) подключен к первым входам всех элементов И 11 М-й строки матрицы, К-й информационный вход 14 второй группы подключен к вторым входам всех элементов И 11 К-го столбца матрицы, вход 15 признака записи подключен к третьим входам всех элементов И 11 матрицы, выход К-го элемента И 11 М-й строки матрицы подключен к входу установки в единицу К-го триггера 12 М-й строки матрицы, выход которого является выходом признака наличия (К,М)-й дуги в произведении частей графа (не показан),Устройство работает следующим образом.Пусть Н и К - два графа с одним, и тем же множеством вершин В (т,еН и К - части одного графа). Тогда произведение графов Г = К х Н есть граф с Г множествами Г(а)- =Н(К(а, Геометрически это означает, что в произведении графов множество соседних с а вершин состоит иэ всех вершин, достижимых из а маршрутом длины 2, первое ребро которого принадлежит К, а второе Н,Перед началом работы обнуляют блок 2 регистрации, в блоки 3 и 5 задания матриц смежности заносится информация о топо 1015 2025 ЗО 35 логии частей графа. На вход 8 устройстваподают сигнал уровня логической "1", при этом блок 1 синхронизации формирует последовательность сигналов, предусмотренных временной диаграммой его работы. Сигнал уровня логической "1" появляется на первом выходе 10 блока синхронизации. При этом на выходе блока 4 формируется массив вершин, достижимых на К-й маршрутной длины 1 в первой части графа, на выходе блока 6 формируется массив вершин, достижимых иэ каждой вершины первого массива маршрутом длины 1 во второй части графа. Через время, достаточное дляокончания указанных операций, блок 1 синхронизации формирует сигнал уровня логической "1" на выходе 9. При этом блок 2 регистрации фиксирует номера вершин, достижимых из первой вершины маршрутом длины 2 (т.е. дуги, исходящие из первой вершины произведения графов), Через время, достаточное для регистрации, блок 1 синхронизации снимает сигнал уровня логический "1" со своего выхода 9 и первоговыхода 10 группы и формирует сигнал уровня логической "1" на втором выходе 10 группы. Далее устройство работает аналогично и после перебора всех вершин графа в блоке 2 регистрации формируется произведение его частей.Блок 2 регистрации работает следующим образом.На вход установки в "0" блока 2 подают сигнал уровня логической "1", При этом все триггеры 12 матрицы устанавливаются в "0". На вход 15 признака записи подают сигнал уровня логической "1". При этом устанавливаются в "1" те триггеры 12,.которые находятся на пересечении строк и столбцов,выбранных единичными потенциалами на входах 13 и 14,Формул а изобретен ия Устройство для операций над графами, содержащее блок синхронизации, блок регистрации, первый блок задания матрицы смежности и первый блок определения концевых вершин дугпричем выход признака наличия (К,М).й дуги первого блока задания матрицы смежности (К = 1, , В, М - 1, , В, где В 50 - количество вершин в графе) подключен кодноименному входу первого блока определения концевых вЕршин дуг, выход признака принадлежности К-й вершины массиву концевых которого подключен к К-му информационному входу первой группы блока регистрации, вход установки в "О" которого является входом начальной установки устройства, вход пуска устройства подключен к входу пуска блока синхронизации, выход которого подключен к входу признака записи1683035 Составитель А.Мишинехред М.Моргентал дактор М.Блан рректор А.Осауленко Тираж Подписноеенного комитета по изобретениям и открытиям при ГКНТ СССР 13035, Москва, Ж, Раушская наб 4/5 аз 3415ВНИИПИ оизводственно-издательский комбинат "Патент", г. Уж агарина, 101 блока регистрации, отл и чаю щееся тем, что, с целью расширения функциональных возможностей устройства за счет определения произведения частей. графа, в него введены второй блок задания матрицы смежности и второй блок определения концевых вершин дуг, причем выход признака наличия (К,М)-й дуги второго блока задания матрицы смежности подключен к одноименному входу второго блока определения концевых вершин дуг выход признака принадлежности М-й вершины массиву концевых которого подключен к входу опроса М-й начальной вершины первого блока опреде.5 ления концевых вершин дуг, К-й выход группы блока синхронизации подключен к К-му информационному входу второй группы блока регистрации и входу опроса К-й начальной вершины второго блока определе ния концевых вершин дуг,