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

)5 606 Е 15 ГОСУДАРСТВЕННЫЙ КОМИТЕТПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМПРИ ГКНТ СССР ОПИСАНИЕ ИЗОБРЕТЕНИ У АВТОРСКОМУ СВИДЕТЕЛ 1(56) Автбрское свидетельство СССР ЬЬ 408312, кл. 6 06 Р 15/20, 1973.Авторское свидетельство СССР .- М 643880, кл. О 06 Р 15/20, 1975. (54) УСТРОЙСТВО ДЛЯ ИССЛЕДОВАНИЯ ГРАФОВ(57) Изобретение относится к вычислительной технике и может быть использовано для решения задачи выделения максимально полного подграфа графа. Целью изобретения является расширение класса решаемых задач за счет выделения максимально полного подграфа исследуемого графа, Поставленная цель достигается тем, что устройство содержит блок 1 задания матрицы смежности графа, блок 2 выбора минимального кода, группу сумматоров 3, триггеры 4 модулей вершин и элемент И 5, причем блок 1 задания смежности графа содержит модели дуг 6, триггер 7 модели дуги, элемент ИЛИ 8, установочные входы 9, 10, вход 11 начальной установки, тактовый вход 12, выход 13 устройства. 1 ил,5 10 15 20 25 ЗО 35 40 М 50 55 Изобретение. относится к вычислительной технике и может быть использовано длярешения задачи выделения максимальнополного подграфа графа.Целью изобретения является расширение класса решаеалых задач за счет выделения максимйМьно полного подграфаисследуемоГО графа.На чертежа представлена функциональная схема устрбйСтва.Устройство,Содержит блок 1 заданияматрицы смежйости графа, блок 2 выбораминимального коАа, группу сумматоров 31,триггеры 4 моДелей вершин и элемент И 5( = 1,п, где и " число вершин исследуемогОГраФа).Блдк 1 задания матрицы смежности графа предназначен для задания топологии исследуемого графй и содержит модели дуг 61,,) = 1,п,(дугй С индексом И, где- 1,п, вмодели отСутСтвуют), Модели дуг идентичныи содержат триггер 7 модели дуги и элементИЛИ 8, Крбмв того, иа чертеже обозначень 1установочные входы 9 и 10 модели дуги,вход 11 начальной установки устройства,тактовМА вхбд 12 устройства и выход 13устройства,Устройство работает следующим образом.".Перед началом решения подачей импульсов уровня логической единицы на установочные входы 9 моделей дуг 6,соответствующих имеющимся в исследуемом графе дугам; задается топология графа,а подачей импульса на вход 11 начальнойустановки устройства обеспечивается возврат в исходное нулевое состояние триггеров 4 моделей вершин. При этом сигналыуровня логической единицы с единичныхвыходов триггеров 7 моделей дуг 6, соответствующих единйчным элементам матрицы смежности исследуемого графа,поступают на первые входы элементов ИЛИ8 этих моделей дуг, С выходов элементовИЛИ 8 моделей дуг сигналы поступают насоответствующие входы элемента И 5 и входы соответствующих сумматоров Зь= 1,п.С выходов сумматоров сигкалы, пропорциональные числу единиц в соответствующихстроках матрицы смежности исследуемогографа, подаются на информационные входыблока 2 выбора минимального кода.Решение начинается подачей импульсана тактовый вход 12 устройства, При этом вблоке 2 осуществляется выбор минимального из входных сигналов и на соответствующем выходе блока появляется импульсуровня логической единицы, который поступает на единичный входтриггера соответст.вующей модели вершины, например на триггер 4 модели вершины. Триггер 4 модели вершины переходит в единичное состояние и сигнал с его единичного выхода поступает на объединенные входы всех моделей дуг -го столбца и -й строки блока 1, моделируя исключение -й вершины из множества вершин искомого подграфа. С выходов моделей дуг сигналы через их элементы ИЛИ 8 поступают на соответствующие входы элемента И 5 и входы сумматоров Зь= 1,п. Если при этом сигнал уровня логической единицы на выходе 13 устройства не появляется, то вновь подается импульс на тактовый вход 12 и начинается следующий шаг решения, который, как и возможные последукщие, аналогичен рассмотренному.Решение завершается, когда после очередного шага решения на всех входах элемента И 6 будут присутствовать сигналы единичного уровня и появится сигнал на выходе устройства 13.Вершины, входящие в множество вершин максимально полного подграфа исследуемого графа, при этом будут однозначно. определены находящимися в нулевом состоянии триггерами 4 моделей вершин,Ф ор мул а и зоб ретв н и я Устройство для исследования графов, содержащее группу из и модулей вершин, где и - число вершин исследуемого графа, от л и ч а ю щ е е с я тем, что, с целью расширения класса решаемых задач за счет выделения максимально полного подграфа исследуемого графа, в него дополнительно введены группа сумматоров,.блок выбора минимального кода, элемент И; блок задания матрицы. смежности графа, который содержит матрицу и х и моделей дуг, причем модели дуг с индексом , где= 1,п, в матрице отсутствуют, модель дуги содержит элемент ИЛИ модели дуги и триггер модели дуги, прямой выход которого соединен с первым входом элемента ИЛИ модели дуги, второй и третий входы и выход которого являются соответственно первым и вторым входами и выходом модели дуги, установочные входы триггера модели дуги являются установОчными входами модели дуги, каждая модель вершины представляет собой триггер, выход модели вершины соединен с первыми входами моделей дуг одноименного столбца и вторыми входами моделей дуг одноименной строки блока задания матрицы смежности графы, входы. слагаемых каждого. из сумматоров группы соединены с выходами одноименной модели дуг одноименного сумматора строки блока задания1725226 10 15 20 30 35 40 45 50 Составитель А.БорисовТехред М,Моргентал Корректор ЭЛончакова Редактор С.Пекарь Заказ 1177 Тираж Подписное ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР 113035, Москва, Ж, Раушская наб., 4/5 Производственно-издательский комбинат "Патент", г. Ужгород, ул.Гагарина, 101 матрицы смежности графа, выход сумматора группы соединен с одноименным входом блока выбора минимального кода, выходы которого соединены с установочными входами одноименных моделей вершин, входы сброса которых соединены с входом начальной установки устройства, выход каждо модели дуги,соедйнен с одноименным вхофм элемейта.И,.,"въаод которого является выходом устройства, вход синхронизации 5 блока выбора мийимального кода являетсятактовым входом устройства.