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

СОКОВ СОВЕ 1 СКИХСОЦИАЛИС 1 ИЧГСКИРЕСГ 1 УВЛИК 6 Г 15/11 ГОсудлРстВенньЙ кОмитГГПО ИЗОБРЕТЕНИЯМ И ОТКРЫТПРИ ГКНТ СССР ПИСАНИЕ ИЗОБРЕТЕН КО А ВИДЕТЕЛ У во СССРО, 1984. во СССР О, 1986ГАШЕНИЯвавЪ(с ОО межости, входы 5 заершины подм 1 ожества1 росд устройства и еыинадлеж 1 оси вар 111 ВЗННЕ УСТО 1 ЛВ Х т а ес лд у к 1111 1 1"ф О Г р а относится к вычислительжет быть использовано для тренне устойчивых подгистрации матрицы с дания центральной в устройства, вход 6 о ходы 7 приз,аков пр подмножеству г 1 урУс 1 ройство раба ется повышева при решевнутре 1 не 1 бходимо определит е годл ожество вег, заданнуо, например ршину,чалом рабсты ра 1,1 я ают в единиу в бл рицы см"жн сТИ за 11 УТРЕ 1 рафа, К-о цсэ . усть не тойчиво чающих ную), ве еред на не ус вклю траль ункционал к 1 элеменершин внутства блок 3 , блок 4 ре,1 блокак11:. Г И ч ли уст ра И 1 Л(46) 15.10.91. Бюл, М 3871) Таганрогский радиотехнический институт им. В.Д. Кал м ы ко ва72) В,М.Глушань,.В.М.Курейчик и А.В.Пришибской(54) УСТРОЙСТВО ДЛЯ Р - ЗАДАЧ НА ГРАФАХ(57) Изобретение относится к вычислительной технике и может быть использовано для определения внутренне устойчивых подмножеств. Целью изобретения является повышение быстродействия устройства при решении задач определения внутрене устойчивых подмножеств графа, Устройство Изобретение ной технике и мо определения вну множеств,Целью изобретения явля ние быстродействия устройст нии задачи определения устойчивых подмножеств граф На чертеже представлена ная схема устройства,Устройство содержит бл тов ИЛИ, блок 2 регистрации ренне устойчивого подмноже определения смежных вершисодержит блок 1 элементов ИЛИ, блок 2 регистрации вершин внутренне устойчивого подмножества, блок 3 определения смежных вершин, блок 4 регистрации матрицы смежности, входь 5 задания центральной вершиы подмножества, вход 6 опроса устройства и выходы 7 признаков принадлежности вершин подмножеству внутренне устойчивых, Для определения внутренне устойчивого подмножества вершин графа. включающих зэданую, например К-ю центральную) вершину, перед началол 1 работы разряды блока 2 устанавливают в единицу, в блок 4 регистрации матрицы смежности заносят инфорлацию о топологии графа На К-й вход 5 задания центральной вершиы подм 1 ожестга и вход 6 опроса подают сигнал уровня лсгической единицы. При этом на выходах 7 устройс 1 ва будет сформирован состав вутре;1 е устачивых вершин, включающих К-ю вершину, 1 ил1684796 Формула изобретенияУстройство для решения задач на графах, содержащее блок элементов ИЛИ, блок регистрации вершин внутренне устойчивого подмножества, блок определения смежСоставитель А,Мишин Редактор Н.Каменская Техред М,Моргентал Корректор А.ОсауленкоЗаказ 3508 Тираж Подписное ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР 113035, Москва, Ж, Раушская наб 4/5 Производственно-иэдательский комбинат "Патент", г. Ужгород, ул.Гагарина, 101 формацию о топологии графа. На К-й вход 5 задания центральной вершины подмножества подают сигнал уровня логической единицы. При этом блок 3 определения смежных вершин выдает сигналы уровня логической единицы на те свои выходы признаков, которые соответствуют вершинам, принадлежащим множеству смежных с центральной. Через время, достаточное для выполнения указанной операции, на вход 6 опроса устройства подают сигнал уровня логической единицы, При этом блок 2 регистрации устанавливает в ноль те из своих разрядов, которым соответствуют единичные сигналы на его установочных входах (т.е. из подмножества внутренне устойчивых исключаются вершины, смежные с центральной), При этом на выходах 7 устройства будет сформирован состав внутренне устойчивых вершин, включающих К-ю вершину,ных вершин и блок регистрации матрицы смежности, выход значения (К, М)-го элемента которого (К = 1, В; М = 1, В, где В - количество вершин в графе) подключен 5 к входу признака наличия (К, М)-й дуги блокаопределения смежных вершин, о т л и ч а ющ е е с я тем, что, с целью повышения быстродействия устройства при решении задачи определения внутренне устойчивых под множеств графа, К-й вход задания центральной вершины подмножества устройства подключен к К-у разряду первого информационного входа блока элементов ИЛИ, К-й разряд информационного входа которого 15 подключен к входу опроса К-й вершины блока определения смежных вершин, выход признака принадлежности М-й вершины множеству смежных которого подключен к входу установки в ноль М-го разряда блока 20 регистрации вершин внутренне устойчивого подмножества, К-й разряд информационного выхода которого является выходом признака принадлежности К-й вершины внутренне устойчивому подмножеству гра фа устройства и подключен к К-у разрядувторого информационного входа блока элементов ИЛИ,