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

®/г/

VI

2

CJ (Л СО

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

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

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

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

БлокЗ определения внутренне устойчивых подмножеств вершин графа содержит узел 11 синхронизации, узел 12 перечисле- ния вершин, узел 13 логического сложения, узел 14 определения смежных вершин, узел 15 коммутации, узел 16 регистрации, узел 17 поразрядного сравнения, причем вход 18 пуска блока 3 подключен к входу пуска узла 11 синхронизации, первый выход 19 узла 11 синхронизации подключен к входу установки в единицу разрядов узла 16 регистрации, второй выход 20 узла 11 синхронизации подключен к входу подключения первого информационного направления узла 15 коммутации, третий выход 21 узла 11 синхронизации подключен к тактовому входу узла 12 перечисления вершин, выходы М-го разряда позиции кода вершины которого

( В, где В - количество вершин в

графе) подключен к М-му разряду второго информационного входа узла 15 коммутации и к М-му разряду второго информационного входа узла 13 логического сложения, М-ый разряд информационного выхода которого подключен к входу опроса М-ой вершины узла 14 определения смежных вершин, выход признака принадлежности К-ой вершины множеству смежных вершин которого () подключен к К-му разряду первого информационного входа узла 17 поразрядного сравнения и к К-му разряду первого информационного входа узла 15 коммутации, К-ый разряд информационного выхода которого подключен к входу установки в куль К-ro разряда узла 16 регистрации, К-ый разряд информационного выхода которого является выходом 22 признака принадлежности К-ой вершины подмножеству блока 3 и подключен к К-му входу разрешения опроса узла 14 и к К-му разряду второго информационного входа узла 17 поразрядного сравнения, выход признака равенства которого подключен к входу подключения второго информационного направления узла 15 коммутации, вход 23 при- знака наличия (К, М)-ой дуги блока 3 подключен к одноименному входу узла 14 определения смежных вершин, выход признака окончания списка узла 12 перечисления вершин является выходом 24 признака выдачи информации блока 3 и подключен к входу останова узла 11 синхронизации, М- ый вход 25 задания центральной вершины блока 3 подключен к М-му разряду первого информационного входа узла логического сложения 13.

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

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

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

Блок 3 определения внутренне устойчивых подмножеств вершин графа работает следующим образом.

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

На вход 18 пуска блока 3 подают им- пульс уровня логической единицы. При этом узел 11 синхронизации формирует на своих выходах 19-21 последовательность сигналов, предусмотренную временной диаграммой его работы. Импульс уровня логической единицы появляется на выходе 19 узла 11 синхронизации, при этом все разряды узла 16 регистрации устанавливаются в единицу. Через время, достаточное для выполнения указанной операции, узел 11 синхрониза- ции формирует импульс логической единицы на своем выходе 20. При этом к выходу узла 15 коммутации подключается его первый информационный вход, и узел 16 устанавливает в нуль те свои разряды, которым соответствуют сигналы уровня логической единицы на его входе (тем самым из состава внутренне устойчивого подмножества исключаются вершины, смежные с центральной). Через время, достаточное для выполнения указанной операции, узел 11 синхронизации формирует импульс на своем выходе 21. При этом узел 12 перечисления вершин выдает на свой выход номер очередной вершины (в первом такте - пер- вый). При этом узел 14 определения смежных вершин выдает на свои выходы признаки принадлежности составу вершин, смежных с текущей (если ее опрос разрешен). При этом узел 17 (если информация, поступившая на его информационные входы, совпала хотя бы в одном разряде) формирует на своем выходе признака равенства сигнал уровня логической единицы. При этом узел 15 коммутации подключа- ет к своему информационному выходу второй информационный вход. При этом узел 16 регистрации устанавливает в пуль те свои разряды (если они не были установлены раньше), которым соответствуют единич- мые потенциалы на его входе (тем самым, если вершина с номером, сформированным узлом 12, смежна хотя бы с одной из вершин, не смежных с центральной, она исключается из состава внутренне устойчивого подмножества). Через время, достаточное

для выполнения указанных операций, узел 11 синхронизации вновь формирует импульс на своем выходе 21, и работа устройства повторяется. После того как узпл 12 перечислит все вершины графа, он формирует сигнал уровня логической единицы на своем выходе признака окончания списка, который одновременно является признаком выдачи информации блока 3. При этом узел 11 синхронизации прекращает формирование синхросигналов и переходит в режим ожидания следующего импульса пуска.

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

блока перечисления першин (. где

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

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

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