Устройство для решения задач на графах

СОЮЗ СОВЕТСНИХСОЦИАЛИСТИЧЕСНИХРЕСПУБЛИК 9) (И) 7534 А АНИ АВТОРСКОМ ЕТЕЛЬСТВУ еотехни СССР 1984. ССР 1987. к вычис ыть исния являьных В оз ет разбиГОСУДАРСТ 8 ЕННЫЙ НОМИТЕТПО ИЗОБРЕТЕНИЯМ И ОТНРЫТИЯМПРИ ГКНТ ССОР 21) 4374149/24-24(71) Московский институт радэлектроники и автоматики(54) УСТРОЙСТВО ДЛЯ РЕШЕНИЯ ЗАДАЧНА ГРАФАХ(57) Изобретение относитсялительной технике и может бпользовано дпя исследования связности графов. Целью изобретеется расширение функционалможностей устройства за счения множества вершин графа на под множества вершин одного поколения.Устройство содержит накапливающийблок логического сложения, блок 2 задания матрицы смежности, блок 3 опрделения полустепеней захода, блок4 регистрации матрицы расслоения,блок 5 синхронизации, вход 6 пускаустройства, первый и второй выходы7 и 8 блока 5 синхронизации, выходы9 группы блока 5 синхронизации ивыход 10 признака окончания работыустройства, Установив в "0" разрядыблока 3, в блок 2 заносят информацию о топологии графа. На вход 6пуска устройства подают импульс уровня логической единицы. При этом блок5 синхронизации формирует последовательность сигналов, предусмотреннуювременной диаграммой его работы,подуправлением которой в блоке 4 фиксируются все слои вершин одного поколения. 2 ил.Изобретение относится к вычислительной технике и может быть использов ано для исследования св язностиграфов.5Цель изобретения - расширениефункциональных возможностей устройства за счет разбиения множества вершин графа на подмножества вершин одного поколения, 1 ОНа фиг. 1 представлена функциональная схема устройства; на фиг.2 - временная диаграмма работы блока синхронизации,Устройство содержит накапливающий 15блоК 1 логического сложения, блок 2задания матрицы смежности, блок 3определения полустепеней захода, блок4 регистрации матрицы расслоения, блок5 синхронизации, вход 6 пуска устройст ва, первый и второй выходы 7 и 8 блока 5 синхронизации, выходы 9 группыблока 5 синхронизации и выход 10 признака окончания работы устройства,Устройство работает следующим образом.Пусть необходимо разбить все вершины графа (без циклов и петель) наслои таким образом, чтобы вершиныпредки и вершины-потомки оказапись 30в различных слоях (подмножества,множества вершин графа) или, другимисловами, чтобы каждый слой содержалвершины одного поколения.Перед началом работы устанавлива.Э.)ют в ноль разряды блока 3, в блок 2заносят информацию о топологии графа. При этом блок 3 выдает на своивыходы состав вершин, полустепени захода которых равны нулю (т.е. состав 40вершин не имеющих предков), На вход6 пуска устройства подают импульсуровня логической единицы, При этомблок 5 синхронизации формирует последовательность сигналов, предусмотренную временной диаграммой егоработы. Потенциал уровня логическойединицы появляется на первом выходе9 группы блока 5 синхронизации. Приэтом блок 4 регистрации подготавливается к записи первой строки матрицырасслоения (первого слоя вершин),Через время, достаточное для окончания операции определения полустепеней захода, блок 5 синхронизацииформирует импульс уровня логическойединицы на выходе 7, При этом блок4 фиксирует данные, поступившие наего информационный вход, накапливающий блок 1 логического сложения добавляет (по ИЛИ) к ранее накопленному значению данные, поступившие на его информационный вход. Через время, достаточное для выполнения укаэанных операций, блок 5 снимает потенциал уровня логической единицы с первого выхода 9 и формирует импульс уровня логической единицы на выходе 8, При этом блок 10 фиксирует на своем выходе накопленное значение. При этом блок 2 задания матрицы смежности устанавливает в ноль (удаляет) столбцы матрицы смежности, а блок 3 определения полустепеней захода блокирует опрос тех вер-. шин, соответствующие которым разряды информационного выхода 1 О блока установлены в единицу (тем самым удаляются дуги, исходящие иэ вершин вошедших во все уже выделенные слои, и запрещается определение полустепени захода для этих вершин). При этом блок 3 выдает на свои выходы состав вершин, полустепени захода которых равным единице, Далее блок 5 синхронизации выдает потенциал уровня логической единицы на второй выход 9, и работа устройства повторяется,После того, как все слои вершин будут найдены, на выходе 10 признака окончания работы устройства появится потенциал уровня логической единицы, При этом в блоке 4 регистрации будут зафиксированы все слои вершин одного поколения.Формула изобретенияУстройство для решения задач на графах, содержащее блок задания матрицы смежности, блок синхронизации и блок регистрации матрицы расслоения, причем вход пуска устройства подключен к входу пуска блока синхронизации, выход которого подключен к входу признака записи блока регистрации матрицы расслоения, Р-й выход группы блока синхронизации (Р = 1.С, где С - количество слоев в графе) подключен к Р-му адресному входу блока регистрации матрицы расслоения, о т л и ч а ю щ е е с я тем, что, с целью расширения функциональных возможностей устройства за счет разбиения множества вершин графа на подмножества вершин одного поколе1587534 Составитель А,Мишиндактор С.Патрушева Техред А.Кравчук. Корре М,Кучерявая ираж 56 Заказ 2422 НИИПИ Государстве одписн ГКНТ СС ретениям и открытиямушская наб., д. 4/5 ого комитета по и 35, москва, Ж,енно-издательский комбинат "Патент", г.ужгород, ул. Гагарина,Произво ния, в него введены блок определенияполустепеней захода и накапливающийблок логического сложения, причемпервый выход блока синхронизацииподключен к тактовому входу накапливающего блока логического сложения,К-й разряд информационного выхода которого (К = 1В, где В - количество вершин в графе) подключен к входу блокировки опроса К-й вершины блока определения полустепеней заходаи к входу признака удаления (К-гостолбца блока задания матрицы смежности, вьмод признака наличия (К,М)го элемента которого (М = 1В) подключен к входу признака наличия(К,М)-й дуги блока определения полустепеней захода, выход признака равенства нулю полустепени захода (К-й 5вершины которого подключен к К-муразряду информационного входа накапливающего блока логического сложения и к К-му информационному входублока регистрации матрицы расслоения, второй выход блока синхронизации подключен к входу опроса накапливающего блока логического сложения,выход признака заполнения разряднойсетки которого является выходом признака окончания работы устройства.