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

 

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

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

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

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

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

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

ПРИ ГКНТ СССР

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

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ а (21) 4657358/24 (22) 01.03.89 (46) 07.10.92. Бюл. М 37 (72) Е.И. Бороденко, Л,Г. Подзубанов, В.В.

Верияскин, А.В. Бындыч и B.Н, Валерьянов (56) Авторское свидетельство СССР

N 1683034, кл. G 06 F 15/20, 1988, Авторское свидетельство СССР

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

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

7 блока 1, а вторая — позицией нулевого разряда результата блока 3. 1 ил.

1767503

30

45

55

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

На чертеже представлена функциональная схема .стройства.

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

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

Пусть необходимо проверить наличие односторонней связности в графе. При этом граф считается односторонне связным, если существует пара вершин, для которой отсутствует взаимная достижимость, Перед началом работы в блок 5 задания матрицы смежности заносят информацию о топологии графа, На вход 6 пуска устройства подают импульс уровня логической "1", При этом блок 1 синхронизации формирует на своих выходах последовательность сигналов, предусмотренную временной диаграммой его работы, Сигнал уровня логической "1" появляется на первом выходе 7 группы блока 1 синхронизации. При этом блок 2 выдает на свои выходы подмножество вершин, из которых может быть до- стигнуто опрошенная вершина графа (в первом такте работы — первая вершина) Одновременно блок 4. выдает на свои выходы подмножество вершин, которые могут быть опрошены из опрошенной. При этом блок 3 выполняет поразрядно операцию логического умножения (конъюнкцию) операндов, поступающих на его входы. В том случае, если хотя бы в одном разряде результата формируется ноль, блок 3 формирует потенциал уровня логической "1" на выходе признака равенства нулю результата операции, что является признаком наличия односторонней связности, Если все разряды результата содержат единицы, сигнал уровня логической "1" формируется на выходе признака неравенства нулю результата операции, При этом блок 1 синхронизации снимает сигнал уровня логической "1" со своего выхода и первого выхода 7 группы и формирует сигнал уровня логической "1" на втором выходе 7 группы. Далее работа устройства повторяется либо до обнаружения наличия односторонней связности, либо до полного перебора всех вершин графа.

Формула изобретения

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