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

( 9) (И) 6 06 Р 15/419 ГОСУДАРСТВЕННЫЙ КОМИТЕТПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМПРИ ГКНТ СССР ОПИСАНИЕ ИЗОБРЕТЕНИЯ 7 АВТОРСКОМУ СВИДЕТЕЛЬС(71) Филиал "Восход" Московского авиационного института им, Серго Орджоникидзе (72) В.В.Соловьев, О,В.Тихонова и Н.Н.Черезова(56) Авторское свидетельство СССР ЬЬ 1336025, кл, 6 06 Р 15/20, 1986.Авторское свидетельство СССР И. 1711187, кл, 8 06 Е 15/20, 04,01,89.(54) УСТРОЙСТВО ДЛЯ РЕШЕНИЯ ЗАДАЧ НА ГРАФАХ(57) Изобретение относится к вычислительной технике и может быть использовано для анализа связности вершин графа. Целью изобретения является расширение функциональных возможностей устройства эа счет перечисления внутренне устойчивых подмножеств вершин графа. Устройство содержит блок 1 синхронизации, блок 2 перечисления вершин, блок 3 определения внутренне устойчивых подмножеств вершин графа, блок 4 регистрации, блок 5 задания матрицы смежности, вход 6 начальной установки, вход 7 пуска и с первого по третий выходы 8 - 10 блока 1 синхронизации. Перед началом работы обнуляют блок 4 регистрации, устанавливают в исходное состояние блок 2 перечисления вершин, в блок 5 задания матрицы смежности заносят информацию о топологии графа. На вход 7 пуска устройства подают импульс уровня логической единицы. При этом блок 1 синхронизации формирует на своих выходах 8-10 последовательность сигналов, под управлением которой в блок 4 регистрации заносится информация о всех возможных внутренне устойчивых подмножествах вершин графа.4 ил,5 10 15 20 25 30 35 40 45 50 55 Изобретение относится к вычислительной технике и может быть использовано для анализа связности вершин графа.Цель изобретения - расширение функциональных воэможностей устройства за счет перечисления внутренне устойчивых подмножеств вершин графа.На фиг. 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 перечисления вершин, выходы М-го разряда позиции кода вершины которого (М=1, В, где В - количество вершин в графе) подключен к М-му разряду второго информационного входа узла 15 коммутации и к М-му разряду второго информационного входа узла 13 логического сложения, М-ый разряд информационного выхода которого подключен к входу опроса М-ой вершины узла 14 определения смежных вершин, выход признака принадлежности К-ой вершины множеству смежных вершин которого (К=1, , В) подключен к К-му разряду первого информационного входа узла 17 поразрядного сравнения и к К-му разряду первого информационного входа узла 15 коммутации, К-ый разряд информационного выхода которого подключен к входу установки в нуль К-го разряда узла 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 синхронизации ос 177435345 50 55 цы. При этом узел 15 коммутации подключает к своему информационному выходу второй информационный вход, При этом узел 16 регистрации устанавливает в нуль те свои разряды (если они не были установлены раньше), которым соответствуют единичные потенциалы на его входе (тем самым, если вершина с номером, сформированным узлом 12, смежна хотя бы с одной из вершин, не смежных с центральной. она исключается из состава внутренне устойчивого подмножества). Через время, достаточное 5 10 15 20 25 30 35 40 для выполнения указанных операций, узел 11 синхронизации вновь формирует илпульс на своем выходе 21, и работа устройства повторяется, После того как узел 12 перечислит все вершины графа, он формирует сигнал уровня логической единицы на своем выходе признака окончания списка, который одновременно является признаком выдачи информации блока 3. При этом узел 11 синхронизации прекращает формирование синхросигналов и переходит в режим ожидания следующего импульса пуска. Формула изобретения Устройство для решения задач на графах, содержащее блок синхронизации, блок перечисления вершин и блох задания матрицы смежности, причем вход пуска устройства подключен к входу пуска блока синхронизации, первый выход которого подключен к тактовому входу блока перечисления вершин, отл ич а ю щеес я тем, что, с целью расширения функциональных возможностей устройства за счет перечисления внутренне устойчивых подмножеств вершин графа, в него введены блок определения внутренне устойчивых подмножеств вершин графа и блок регистрации, вход установки в "0" которого является входом начальной установки устройства, причем Ы-й разряд позиционного кода номера вершины блока перечисления вершин (М= . В, где В - количество вершин в графе) подключен к М-му входу задания Центральной вершины блока определения внутренне устойчивых подмножеств вершин графа, выход признака принадлежности К-й вершины подмножеству которого (К==1, ., В) подключен к К-му разряду информационного входа блока регистрации, выход значения (К, М)-го элемента блока задания матрицы смежности подключен к входу признака наличия (К, М)- й дуги блока определения внутренне устойчивых подмножеств вершин графа, выход признака окончания списка блока перечисления вершин подключен к входу останова блока синхронизации, второй выход блока синхронизации подключен к входу пуска блока определения внутренне устойчивых подмножеств вершин графа, выход признака выдачи информации которого подключен к входу признака записи блока регистрации и к входу повторного пуска блока синхронизации, третий выход которого подключен к входу признака смены адреса блока регистрации.1774353 Составитель А. Миш Техред М.Моргентал Корректор еда ктор карь роизводственно-издательский комбинат ".Патент", г. Ужгород, ул.Гагарина, 10 Э.Заказ 3928 Тираж ПодписноеВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР113035, Москва, Ж; Раушская наб 4/5