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

СОЮЗ СОВЕТСКИХ СОЦИАЛИСТИЧЕСКИХРЕСПУБЛИН 9) (111 35 1)5 С 06 Р 15/2 ВТОРСНОМУ инсти- рьской че скин й Октя ов ССР983.Р988. ьство5/20,тво СС5/20,ГРА г,ер- регистГОСУДАРСТВЕННЫЙ КОМИТЕТПО ИЗОБРЕТЕНИЯМ И ОТНРЫТИЯПРИ ГКНТ СССР. ПИСАНИЕ ИЗО(54) УСТРОЙСТВО ДЛЯ ОПЕРАЦИЙ НА ФАХ (57) Изобретение относится к вычислительной технике и может быть использовано для исследования систем,описываемых графами. Целью изобретения является расширение функциональных возможностей устройства за счет решения задачи стягивания вершин ори-" ентированного графа. Устройство содержит блок 1 синхронизации, блок 2 определения концевых вершин ду блок 3 определения начальных в шин дуг, блок 4 удаления дуг,1 ры 6 и 7, ключ 8 и имеет вход 9 начальной установки, вход 10 пуска, с первого по В-й входы 11 признаков принадлежности вершин массиву стягиваемых (В - количество вершин в графе), выход 12 признака окончания работы, выходы 13 признаков наличия дуг в исходном графе, выходы 14 признаков наличия дуг, исходящих из (В+1)-й вершины, выходы 15 признаков наличия дуг, заходящих в (В+1)-ю вершину, выходы 16-19 блока 1 синхронизации, При подаче на вход 10 импульса уровня логической единицы блок 1 Формирует последовательность сигналов, под управлением которой устройство определяет концевые вершины для дуг, исходящих из стягиваемых вершин, заносит признаки наличия дуг из (В+1)-й в указанные концевые вершины в регистр 6, удаляет дуги, исходящие иэ стягиваемых вершин, определяет начальные вершины для дуг, заходящих в стягиваемые вершины,заносит признаки наличия дуг в (В+1)-ю иэ указанных начальных вершин дуг и удаляет дуги, заходящие в стягиваемые вершины, 5 илфЭф 1 Ю йу50 Изобретение относится к вычислительной технике и может быть использовано для исследования систем, описываемых графами.5Цель изобретения - расширение функциональных воэможностей устройства за счет решения задачи стягивания вершин ориентированного графа.На Фиг,1 представлена функциональО ная схема устройства; на фиг,2 - временная диаграмма работы блока синхронизации; на Фиг.З - функциональная схема блока определения концевых вершин дуг; на фиг.4 - функциональная схема блока определения начальных вершин дуг; на Фиг.5 - функциональная. схема блока удаления дуг.Устройство содержит блок 1 синхронизации, блок 2 определения концевых вершин дуг, блок 3 определения начальных вершин дуг, блок 4 удаления дуг, разряды 5 информационного входа первого регистра, регистры 6 и 7, ключ 8, вход 9 начальной уста новки, вход 10 пуска с первого по В-й входы 11 признаков принадлежности вершин массиву стягиваемых, где В - количество вершин в графе, выход 12 признака окончания работы, выходы 13 признаков наличия дуг в исходном графе устройства, выходы 14 признаков наличия дуг, исходящих из (В+1)-й вершины устройства, выходы 15 признаков наличия дуг, заходящих в (В+1)-ю вершину, выходы 16-19 блока 1 синхро 35 низации.На Фиг.З цифровые обозначения представляют матрицу из ВхВ элементов И 20, группу из В элементов ИЛИ 21, входы 22 признаков наличия дуг блока 2, входы 23 опроса началь. ных вершин блока 2, выходы 24 признаков принадлежности вершин массиву концевых, причем вход 23 опроса 45 М-й начальной вершины (М = 1В) подключен к первым входам всех элементов И 20 М-й строки матрицы, вход 22 признака наличия (К, М)-й дуги блока 2 (К = 1В) подключен к второму входу К-го элемента И 20 М-й строки матрицы, выход которого подключен к К-му входу М-го элемента ИЛИ 21 группы, выход которого является выходом признака принадлежности М-й вершины массиву концевых.55На фиг.4 представлены: матрица из ВхВ элементов И 25, группа,из В элементов ИЛИ 26, входы 27 опроса концевых вершин, входы 28 признаков наличия дуг и выходы 29 признаков принадлежности вершин массиву начальных,причем вход 27 опроса К-й концевойвершины подключен к первым входамвсех элементов И 25 К-го столбца матрицы, вход 28 признака наличия (К,М)-й дуги подключен к второму входуК-го элемента И 25 М-й строки матрицы, выход которого. подключен к Кму входу М-го элемента ИЛИ 26, выходкоторого является выходом 29 признака принадлежности М-й вершины массиву начальных блока 3.На Фиг.5 представлены: матрица изВхВ элементов ИЛИ 30, матрица из ВхВэлементов 31 памяти, ключи 32 и 33,входы 34 установки признаков наличиядуг блока 4, входы 35 задания концевых точек удаляемых дуг, вход 36 признака удаления исходящих дуг, вход37 признака удаления заходящих дуги выходы 38 признаков наличия дугблока 4, причем вход 35 задания К-йконцевой точки удаляемых дуг подключен к К-му разряду информационноговхода ключа 32 и к К-му разряду информационного входа ключа 33, К-йразряд информационного выхода которого подключен к первым входам всехэлементов ИЛИ 30 К-го столбца матрицы, М-й разряд информационного выхода ключа 32 подключен к вторымвходам всех элементов ИЛИ 30 М-йстроки матрицы, выход К-го элемента 30 ИЛИ М-й строки матрицы подключен к входу установки в ноль К-гоэлемента 31 памяти М-й строки матрицы, выход которого является выходом38 признака наличия (К, М)-й дугиблока 4, вход 34 установки признака наличия (К, М)-й дуги которогоподключен к входу установки в единицу К-го элемента памяти М-й строкиматрицы, входы 36 и 37 блока 4 подключены к управляющим входам (входамвключения) ключей 32 и 33 соответственно. На фиг,5 не показан вход начальной установки элементов 31 памяти, но он может быть реализован объединением третьих входов элементовИЛИ 30.Устройство работает следующим образом,Пусть необходимо стянуть одну илинесколько вершин графа во внешнююточку или, считая что исходный графимеет В вершин, в (В+1)-ю вершину,5 158753Перед на.алом работы, подавая навход 9 импульс уровня логической единицы, обнуляют регистры 6 и 7,В блок 4 удаления дуг заносят информацию о топологии графа (его ма 5трицу смежности), по входам 11 признаков принадлежности вершин массиву стягиваемых задают состав стягиваемых вершин графа, 10На вход 10 пуска подают импульсуровня логической единицы, При этомблок 1 синхронизации формирует последовательность сигналов уровня логической единицы., предусмотреннуювременной диаграммой его работы,Через время, достаточное для определения концевых вершин дуг блоком 2, отсчитанное от момента выдачи информации на входы 11, блок 1 формирует 2 Ссигнал уровня логической единицы навыходе 16, При этом в регистр 6 заносится информация с выхода блока 2(т,е. происходит формирование дуг,исходящих из (В+1)-й вершины), Через 25время, достаточное для записи, блок1 синхронизации снимает сигнал .с выхода 16 и формирует сигнал уровня логической единицы на своем выходе 17При этом блок 4 удаляет иэ топологии графа все дуги, исходящие из стягиваемьм вершин. Одновременно регистр 6 устанаьливает в ноль те своиинформационные разряды, номера которых соответствуют номерам стягиваемых вершин (тем самым из топологииграфа исключают дуги, соединяющие стястягиваемые вершины),Через время, достаточное для окончани указанных процессов, блок 1 син Охронизации снимает сигнал с выхода17 и через время, достаточное для определения начальньм вершин дуг в блоке З,считая от момента завершения операции удаления в блоке 4, формирует 45сигнал уровня логической единицы навыходе 18. При этом регистр 7 фиксирует (записывает) информацию, поступившую на его информационный вход.Теи самым происходит Формированиедуг, заходящих в (В+1)-ю вершину графа. Через время, достаточное дляокончания записи, блок 1 синхронизации снимает сигнал со своего выхода18 и формирует сигнал уровня логической единицы на сзоем выходе 19. Приэтои блок 4 удаления дуг удаляетиз топологии графа все дуги заходящие в стягиваемые,5 6Через время, достаточное для удаления заходящих дуг, блок 1 синхронизации снимает сигнал со своего выхода 19 и формирует сигнал уровня логической .единицы на выходе 12 признака окончания работы. В этот момент времени информация о составе стягиваеиых вершин может быть снята с входов 11. К этому моменту времени на выходах 13 находится информация о наличии дуг в топологии исходного графа (т,е, графа, .нумерация вершин которого совпадает с нумерацией вершин исходного граФа) .Блок 4 удаления дуг работает следуницим образом.Перед началом работы подачей сигнала на вход 9 обнуляют все элементы 31 памяти (цепи начальной установки на фиг.5 не показаны).По входам 34 задают информацию о топологии графа (задают его матрицу смежности). На входы 35 подают информацию (набор нулей и/или единиц) о концевых точках удаляемых дуг (т,е. о номерах вершин, в которые заходят или из которых исходят удаляемые дуги) .На вход Зб подают сигнал уровня логической единицы, При этом открывается ключ 32 и сигналы уровня логической единицы с его информационного выхода обнуляют соответствующие строки элементов 31 памяти (тем самым удаляются все дуги, исходящие из вершин, заданных по входам 35)На вход 37 подают. сигнал уровня логической единицы При этом открывается ключ 33 и сигналы уровня логической единицы с его информационного выхода обнуляют элементы 31 памяти соответствующих столбцов матрицы (тем самым удаляют все дуги, заходящие в вершины, заданные по входам 35). формул а,из об ре тения устройство для операций на графах, содержащее блок синхронизации, блок опрецеления концевых вершин дуг и первый регистр, о т л и ч а ю - щ е е с я тем, что, с целью расширения функциональных возможностей устройства за счет решения задачи стягивания вершин ориентированного графа, в него введены второй регистр, ключ, блок удаления дуг и блок опре 1587535деления начальных верши дуг, причемвход начальной установки устройстваподключен к входам установки в "О"блока удаления дуг и первого и второго регистров, вход признака принадлежности К й вершины массиву отягиваемых (К = 1В, где В - количество вершин в графе) подключен кК-му РазРяду информационного входаключа, к входу задания К-й концевойточки блока удаления дуг, к входуопроса К-й концевой вершины дугиблока определения, начальных вершиндуг и к входу опроса К-й начальнойвершины дуги блока определения концевых вершин дуг, выход признакапринадлежности М-й вершины массивуконцевых которого (М = 1,.;.,В) подключен к Мму разряду информационного входа первого регистра, вход пуска устройства подключен к входупуска блока синхронизации, первыйвыход которого подключен. к входупризнака записи первого регистра,второй выход блока синхронизации подключен к входу признака удаления исходящих дуг блока удаления дуг и к управляющему входу ключа, К-й разряд информационного выхода которого подклю-чен к входу установки в "О" К-го разряда первого регистра, М-й разряд информационного выхода которого является выходомпризнака наличия (В+1,М)-йдуги графа устройства, третий выходблока синхронизации подключен к входупризнака записи второго регистра,четвертый выход блока синхронизацииподключен к входу признака удалениязаходящих дуг блока удаления дуг,выход признака наличия (К, М)-й дугикоторого подключен к одноименным входам блока определения концевых вершин дуг и блока определения начальных вершин дуг, выход признака при-надлежности М-й вершины массиву начальных которого подключен к М-му разряду информационного входа второгорегистра, М-й разряд информационного выхода которого является выходомпризнака наличия (М, В+1)-й дуги графа устройства, пятый выход блокасинхронизации является выходом признака окончания работы устройства,КНТ СССР изводственно-издательский комбинат "Патент", г, Ужгород Гагарина, 1 Заказ 2422 Тираж 568 ПодписноеВНИИПИ Государственного комитета по изобретениям .и открытиям при113035, Москва, Ж, Раушская наб д. 4/5