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

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

Иллюстрации

Показать все

Реферат

 

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

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

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

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

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

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

ПРИ ГКНТ СССР

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

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (21) 4425142/24 (22) 12.05,88 (46) 30.09.91. Бюл. М 36 (71) Киевский политехнический институт им. 50-летия Великой Октябрьской социали- стической революции (72) О.Н. Костюк (53) 681.333 (088.8) (56) Авторское свидетельство СССР

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

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

М 1587535, кл. G 06 F 15/20, 26.04,88. (54) УСТРОЙСТВО ДЛЯ РЕШЕНИЯ ЗАДАЧ

НА ГРАФАХ (57) Изобретение относится к вычислительной технике и может быть использовано для анализа связности графов. Целью изобрете„„ Ы„„1б81311 А1 ния является расширение функциональных возможностей устройства путем определения конденсации графа, Устройство содержит блок 1 синхронизации, блок 2 определения компонент сильной связности, блок 3 стягивания вершин, блок 4 задания матрицы смежности, вход 5 пуска устройства, группу выходов 6 блока 1 синхронизации и выходы 7-10 блока синхронизации. Перед началом работы в блок 4 задания матрицы смежности заносят информацию о топологии графа. На вход 5 пуска устройства подают импульс уровня логической единицы, При этом блок 1 формирует на своих выходах 6 и 10 последовательность сигналов, под управлением которой в блоке 4 формируется конденсация графа. 2 ил.

1681311

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

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

На фиг.1 представлена функциональная схема предлагаемого устройства, на фиг.2— временная диаграмма работы блока синхронизации.

Устройство содержит блок 1 синхронизации, блок 2 определения компонент сильной связности, блок 3 стягивания вершин, блок 4 задания матрицы смежности, вход 5 пуска устройства, группу выходов 6 блока 1 синхронизации, выходы 7-10 блока 1 синхронизации, Устройство работает следующим образом.

Пусть требуется определить конденсацию ориентированного графа. При этом под конденсацией понимается такой граф, в котором каждая из его вершин соответствует одной из компонент сильной связности (КСС) исходного графа, а дуга, соединяющая вершины графа коденсации, существует тогда, когда существует хотя бы одна дуга, соединяющая соответствующие вершинам

КСС исходного графа.

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

его работы (фиг.2). Ьлок 1 синхронизации формирует потенциал уровня логической единицы на первом выходе 6 группы и через

Bp8MR, достаточное для его установления,— на своем выходе 7. При этом блок 2 формирует на своих выходах потенциалы уровня логической единицы в соответствии с составом КСС графа (с текущей топологией), включающей первую вершину. Через время, достаточное для определения КСС, блок

1 формирует потенциал уровня логической единицы на своем выходе 8, При этом блок

3 стягивания вершин фиксирует на своих выходах состав дуг, инцидентных первой вершине (текущей точке стягивания) при стягиваниии в нее всех вершин. текущей

КСС графа. Через время, достаточное для

40 стягивания вершин, блок 1 снимает потен- 55 циалы с первого выхода 6 группы и выходов

7 и 8 и формирует импульс уровня логической единицы на своем выходе 9. При этом блок 4 удаляет из текущей топологии графа все дуги, инцидентные вершинам из текущей КСС графа. Через время, достаточное для удаления дуг, блок 1 формирует импульс уровня логической единицы на своем выходе |0, При этом блок 4 добавляет к текущей топологии графа дуги, инцидентные текущей точке стягивания. Через время, достаточное для выполнения операции добавления дуг, блок 1 формирует потенциал уровня логической единицы на втором выходе 6, после чего работа устройства повторяется, По завершении В циклов работы ( — количество вершин в графе) в блоке 4 будет сформирована конденсация исходного графа, Формула изобретения

Устройство для решения задач на графах, содержащее блок синхронизации и блок задания матрицы смежности, причем вход пуска устройства подключен к входу пуска блока синхронизации, первый и второй выходы которого подключены к входу признака удаления дуг и входу признака добавления дуг блока задания матрицы смежности соответственно, о т л и ч а ю щ е ес я тем; что, с целью расширения функциональных возможностей устройства путем определения конденсации графа, в него введены блок определения компонент сильной связности и блок стягивания вершин, причем К-й выход группы блока синхронизации (К=1,.„,В, где  — количество вершин в графе) подключен к входу опроса К-й вершины — носителя компонент сильной связности блока определения компонент сильной связности и K-му входу задания точки стягивания блока стягивания вершин, выход признака наличия (К,M)-й дуги которого (М=1,...,В) подключен к входу разрешения добавления (К,M)-го элемента блока задания матрицы смежности, выход значения (К,M)-го элемента которого подключен к входу признака наличия (К,M)-й дуги блока стягивания вершин и входу признака наличия (К,М)-й дуги блока определения компонент сильной связности, выход признака принадлежности M-й вершины множеству вершин компоненты сильной связности которого подключен к М-му входу задания множества стягиваемых вершин и входу разрешения удаления дуг, инцидентных M-й вершине блока задания матрицы смежности, третий и четвертый выходы блока синхронизации подключены к тактовым входам блока onðåделения компонент сильной связности и блока стягивания вершин соответственно.

1681311

° ° е

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

Техред М,Моргентал Корректор М.Максимишинец

Редактор А,Лежнина

Производственно-издательский комбинат "Патент", г, Ужгород, ул.Гагарина, 101

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

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

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