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

)5 6 06 Р 15/419 РЕТЕНИ Е ОСУДАРСТВЕННЫЙ КОМИТЕТО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯРИ ГКНТ СССР АВТОРСКОМУ СВИДЕТЕЛ(71) Киевский политехнический институт им. 50-летия Великой Октябрьской социалистической революции(56) Авторское свидетельство СССР М 1174937, кл, 6 06 Р 15/20, 1983.Авторское свидетельство СССР М 1587535, кл. 6 06 Г 15/20, 26.04,88, (54) УСТРОЙСТВО ДЛЯ РЕШЕНИЯ ЗАДАЧ НА ГРАФАХ(57) Изобретение относится к вычислительной технике и может быть использовано для анализа связности графов. Целью изобретения является расширение функциональных возможностей устройства путем определения конденсации графа, Устройство содержит блок 1 синхронизации, блок 2 определения компонент сильной связности, блок 3 стягивания вершин, блок 4 задания матрицы смежности, вход 5 пуска устройства, группу выходов 6 блока 1 синхронизации и выходы 7-10 блока синхронизации. Перед началом работы в блок 4 задания матрицы смежности заносят информацию о топологии графа. На вход 5 пуска устройства подают импульс уровня логической единицы, При этом блок 1 формирует на своих выходах 6 и 10 последовательность сигналов, под управлением которой в блоке 4 формируется конденсация графа. 2 ил,Изобретение относится к вычислительной технике и может быть использовано для анализа связности графов.Целью изобретения является расширение функциональных возможностей устройства путем определения конденсации графа.На фиг.1 представлена функциональная схема предлагаемого устройства, на фиг.2 - временная диаграмма работы блока синхронизации.Устройство содержит блок 1 синхронизации, блок 2 определения компонент сильной связности, блок 3 стягивания вершин, блок 4 задания матрицы смежности, вход 5 пуска устройства, группу выходов 6 блока 1 синхронизации, выходы 7-10 блока 1 синхронизации,Устройство работает следующим образом,Пусть требуется определить конденсацию ориентированного графа. При этом под конденсацией понимается такой граф, в котором каждая из его вершин соответствует одной из компонент сильной связности(КСС) исходного графа, а дуга, соединяющая вершины графа коденсации, существует тогда, когда существует хотя бы одна дуга, соединяющая соответствующие вершинам КСС исходного графа.Перед началом работы в блок 4 задания матрицы смежности заносят информацию о топологии графа. На вход 5 пуска устройства подают импульс уровня логической единицы, При этом блок 1 синхронизацииформирует последовательность импульсов, предусмотренную временной диаграммой его работы (фиг.2). Ьлок 1 синхронизации формирует потенциал уровня логической единицы на первом выходе 6 группы и черезвремя, достаточное для его установления, - на своем выходе 7, При этом блок 2 формирует на своих выходах потенциалы уровня логической единицы в соответствии с составом КСС графа (с текущей топологией),включающей первую вершину. Через время, достаточное для определения КСС, блок 1 формирует потенциал уровня логической единицы на своем выходе 8, При этом блок3 стягивания вершин фиксирует на своихвыходах состав дуг, инцидентных первой вершине (текущей точке стягивания) при стягиваниии в нее всех вершин текущей КСС графа. Через время, достаточное для 5 10 15 203040 стягивания вершин, блок 1 снимает потенциалы с первого выхода 6 группы и выходов 7 и 8 и формирует импульс уровня логической единицы на своем выходе 9. При этом блок 4 удаляет из текущей топологии графа все дуги, инцидентные вершинам из текущей КСС графа. Через время, достаточное для удаления дуг, блок 1 формирует импульс уровня логической единицы на своем выходе 10, При этом блок 4 добавляет к текущей топологии графа дуги, инцидентные текущей точке стягивания, Через время, достаточное для выполнения операции добавления дуг, блок 1 формирует потенциал уровня логической единицы на втором выходе 6, после чего работа устройства повторяется, По завершении В циклов работы (В - количество вершин в графе) в блоке 4 будет сформирована конденсация исходного графа,Формула изобретения Устройство для решения задач на графах, содержащее блок синхронизации и блок задания матрицы смежности, причем вход пуска устройства подключен к входу пуска блока синхронизации, первый и второй выходы которого подключены к входу признака удаления дуг и входу признака добавления дуг блока задания матрицы смежности соответственно, о т л и ч а ю щ е ес я тем; что, с целью расширения функциональных возможностей устройства путем определения конденсации графа, в него введены блок определения компонент сильной связности и блок стягивания вершин, причем К-й выход группы блока синхронизации (К=1,.,В, где В - количество вершин в граФе) подключен к входу опроса К-й вершины - носителя компонент сильной связности блока определения компонент сильной связности и К-му входу задания точки стягивания блока стягивания вершин, выход признака наличия (К,М)-й дуги которого (М=1В) подключен к входу разрешения добавления (К,М)-го элемента блока задания матрицы смежности, выход значения (К,М)-го элемента которого подключен к входу признака наличия (К,М).й дуги блока стягивания вершин и входу признака наличия (К,М)-й дуги блока определения компонент сильной связности, выход признака принадлежности М-й вершины множеству вершин компоненты сильной связности которого подключен к М-му входу задания множества стягиваемых вершин и входу разрешения удаления дуг, инцидентных М-й вершине блока задания матрицы смежности, третий и четвертый выходы блока синхронизации подключены к тактовым входам блока определения компонент сильной связности и блока стягивания вершин соответственно.1681311 Составитель А,МашинТехред М,Моргентал Корректор М,Максимишинец актор А,Лежнина оизводственно-издательский комбинат "Патент", г, Ужгород, ул,Гагарина, 10 Заказ 3313 Тираж Подписное ВНИИПИ Государственного комитета по изобретениям и открытиям при 113035, Москва, Ж, Раушская наб., 4/5