Устройство для решения задач на графах Советский патент 1991 года по МПК G06F15/173 

сл

с

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

о

00 00

Фиг Л

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

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

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

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

Устройство работает следующим образом.

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

Перед началом работы в блок 4 задания матрицы смежности заносят информацию о топологии графа. На вход 5 пуска устройства подают импульс уровня логической единицы. При этом блок 1 синхронизации формирует последовательность импульсов, предусмотренную временной диаграммой его работы (фиг.2). Блок 1 синхронизации формирует потенциал уровня логической единицы на первом выходе б группы и через время, достаточное для его установления, - на своем выходе 7. При этом блок 2 формирует на своих выходах потенциалы уровня логической единицы в соответствии с составом КСС графа (с текущей топологией), включающей первую вершину. Через время, достаточное для определения КСС, блок 1 формирует потенциал уровня логической единицы на своем выходе 8. При этом блок 3 стягивания вершин фиксирует на своих выходах состав дуг, инцидентных первой вершине (текущей точке стягивания) при стягиваниии в нее всех вершин текущей КСС графа. Через время, достаточное для стягивания вершин, блок 1 снимает потенциалы с первого выхода 6 группы и выходов 7 и 8 и формирует импульс уровня логической единицы на своем выходе 9. При этом

блок 4 удаляет из текущей топологии графа все дуги, инцидентные вершинам из текущей КСС графа. Через время, достаточное для удаления дуг, блок 1 формирует импульс

уровня логической единицы на своем выходе 10. При этом блок 4 добавляет к текущей топологии графа дуги, инцидентные текущей точке стягивания, Через время, достаточное для выполнения операции

0 добавления дуг, блок 1 формирует потенциал уровня логической единицы на втором выходе 6, после чего работа устройства повторяется. По завершении В циклов работы (В - количество вершин в графе) в блоке 4

5 будет сформирована конденсация исходного графа,

Формула изобретения Устройство для решения задач на гра0 фах, содержащее блок синхронизации и блок задания матрицы смежности, причем вход пуска устройства подключен к входу пуска блока синхронизации, первый и второй выходы которого подключены к входу

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

0 определения конденсации графа, в него введены блок определения компонент сильной связности и блок стягивания вершин, причем К-й выход группы блока синхронизации (, где В - количество вершин в

5 графе) подключен к входу опроса К-й вершины - носителя компонент сильной связности блока определения компонент сильной связности и К-му входу задания точки стягивания блока стягивания вершин, выход при0 знака наличия (К,М)-й дуги которого (,...,В) подключен к входу разрешения добавления (К,М)-го элемента блока задания матрицы смежности, выход значения (К,М)-го элемента которого подключен к вхо5 ду признака наличия (К,М)й дуги блока стягивания вершин и входу признака наличия (К,М)-й дуги блока определения компонент сильной связности, выход признака принадлежности М-й вершины множеству вершин

0 компоненты сильной связности которого подключен к М-му входу задания множества стягиваемых вершин и входу разрешения удаления дуг, инцидентных М-й вершине блока задания матрицы смежности, третий

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

W 7

-TL. .

Л

t

Ј

-ПЈ

f