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

 

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

СОЮЗ СОВЕТСКИХ социАлистических

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

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

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

ПРИ ГКНТ СССР

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

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ

4 М фь.

Cd (Я

Шаг./ (21) 4679275/24 (22) 13.02.89 (46) 07.11.92. Бюл. М 41 (71) Филиал "Восход" Московского авиационного института им, Серго Орджоникидзе (72) В.В.Соловьев, О.В.Тихонова и Н.Н.Черезова (56) Авторское свидетельство СССР

ЬЬ 1336025, кл. 6 06 F 15/20, 1986.

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

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

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

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

4 ил.

1774353

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

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

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

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

Блок 3 определения внутренне устойчивых подмножеств вершин графа содержит узел 11 синхронизации, узел 12 перечисления вершин, узел 13 логического сложения. узел 14 определения смежных вершин, узел

15 коммутации, узел 16 регистрации, узел 17 поразрядного сравнения, причем вход 18 пуска блока 3 подключен к входу пуска узла

11 синхронизации, первый выход 19 узла 11 синхронизации подключен к входу установки в единицу разрядов узла 16 регистрации, второй выход 20 узла 11 синхронизации подключен к входу подключения первого информационного направления узла 15 коммутации, третий выход 21 узла 11 синхронизации подключен к тактовому входу узла 12 перечисления вершин, выходы М-го разряда позиции кода вершины которого (M=1...„В, где  — количество вершин в графе) подключен к M-му разряду второго информационного входа узла 15 коммутации и к М-му разряду второго информационного входа узла 13 логического сложения, M-ый разряд информационного выхода которого подключен к входу опроса M-ой вершины узла 14 определения смежных вершин, выход признака принадлежности

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

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

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

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

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

10 и 8 блока 1 синхронизации. При этом блок

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

При этом блок 4 регистрации формирует поступившую на его вход информацию, а блок

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

55 ганавливэется «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, смежна хотя бы с одной из вершин, не смежных с центральной. она исключается из состава внутренне устойчивого подмножества). Через время, достаточное

40 для выполнения указан««ь«х 0l1cpBI«H«««. узел

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

11 синхронизации прекращает форл«ирование синхросигналов и переходит s режим ожидания следую«цего импульса пуска.

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

Устройство для решения задач на графах, содержащее блок синхронизации, блок перечисления вершин и блох задания матрицы смежности, причем вход пуска устройства подключен к входу пуска блока синхронизации, первый выход которого подключен к тактовому входу блока перечисления вершин, о т л и ч а ю ще е с я тем, что, с целью расширения функциональных возможностей устройства за счет перечисления внутренне устойчивых подмножеств вершин графа, B него введены блок определения внутренне устойчивых подмножеств вершин графа и блок регистрации, вход установки в "0" которого является входом начальной установки устройства, причем Ы-й разряд позиционного кода номера вершины блока перечисления вершин (М= ....„В, где

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

1774353

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

Техред М.Моргентал Корректор С. Пекарь

Редактор

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

>.

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

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

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