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

1288711Изобретение относится к вычислительной технике и может быть использовано для решения на графах задачнахождения центра (бицентра) дерева.Цель . изобретения - расширениефункциональных возможностей за счетопределения вершины (двух вершин),образующей центр (бицентр) дерева.На чертеже представлена структурная схема устройства,Устройство содержит распределитель 1 импульсов, матрицу 2 моделейребер 3, каждая модель ребра 3 содержит элемент И 4 и триггер 5. Устройство также содержит группу элементовИЛИ 6, группу счетчиков 7, группудешифраторов 8 единицы, группу триггеров 9, группу элементов И 10, груп 1пу ключей 11, сумматор 12, регистр 3,20блок 14 вычитания, дешифратор 15, элемент ИЛИ 16, генератор 17 импульсов.Первоначально триггеры 5, соответствующие позициям матрицы смежностиграфа, в которых записаны единицы, 25устанавливают в единичное состояние,как и триггеры 9, в регистр 13 записывают код числа вершин графа, счетчики 7 и сумматор 12 обнуляют,Устройство работает следующим образом.При поступлении пускового сигналаимпульсы генератора 17 проходят навход распределителя 1, который поочередно выдает импульсы на свои выходы.Каждый импульс распределителя 1 проходит через те элементы И 4 соответствующего столбца матрицы 2, на первый вход, которых поступает единичныйсигнал с выхода триггеров 5. Послепрохождения импульсов распределителя 1через каждый элемент ИЛИ 6 на входсчетчика 7 поступает столько импульсов, сколько триггеров 5 находятсяв единичном состоянии в соответствующей строке матрицы 2.Код числа поступивших импульсовс выхода каждого счетчика 7 поступаетна вход соответствующего дешифратора 8, который выдает на выход единичный сигнал лишь .в случае, когда показания счетчика 7 равны единицы. Единичный сигнал с выхода дешифратора 8проходит через ключ 11 на вход сумматора 12, поскольку на управляющийвход ключа 11 поступает единичный потенциал с выхода триггера 9, и открывает элемент И 1 О При поступлении(и+1)-го импульса распределителя 1 сумматор 12 суммирует общее число единиц, поступающих на его входы с выходов ключей 11, код результата остается в сумматоре 12 и, кроме того, поступает на первый вход блока 14, на второй вход которого поступает код числа с выхода регистра 13. Разность и-Б поступает на вход дешифратора 15, который выдаетсигнал на свой первый или второй выходы, если, только разность равна единице или двум соответственно.Одновременно сигналы с выходов тех или иных ключей 11 поступают на входы установки в ноль триггеров 5 соответствующих столбцов матрицы 2 и переводят эти триггеры в нулевое состояние, вследствие чего закрываются соответствующие элементы И 4 для прохождения импульсов распределителя 1 в последующих циклах его работы.Кроме того, импульс с (И+1)-го выхода распределителя 1 проходит через те элементы И 10, которые открыты единичным сигналам с выхода соответствующих дешифраторов 8, и перебрасывает соответствующие триггеры 9 в нулевое состояние (уже до конца работы устройства), вследствие чего закрываются соответствующие ключи 11, Задним фронтом п+1 импульс распределителя 1 обнуляет счетчики 7. Таким образом, после первого цикла работы распределителя 1 в сумматоре 12 хранится некоторое число Б, численно равное числу вершин графа, каждой из которых инцидентно всего одно ребро. При этом триггеры 5 столбцов матрицы 2, соответствующие этим вершинам, сброшены в ноль, а соответствующие ключи 11 закрыты до конца работы устройства. Все счетчики 7 обнулены,С каждым новым циклом работы распределителя 1 накапливаемая в сумматоре 12 сумма Б возрастает и, наконец, после какого-то цикла разность и-Б становится равной двум и единице, Код этой разности с выхода блока 14 вычитания поступает на вход дешифратора 15, который в этом случае выцает на один из своих выходов сигнал, который через элемент ИЛИ 16 поступает на вход останова генератора 17, прекращая работу устройства. Номер столбца, в котором триггеры 5 остались в единичном состоянии, указывает вершину - центр дерева, а если таких столбцов два, то соответст 1288710вующие две вершины образуют бицентр дерева, нахождение которого необходимо для выбора резервных пунктов управления в иерархических системах управления, адаптированных к изменяю щимся условиям обстановки путем передачи управления тому или иному промежуточному пункту в случае выхода из строя (прогнозирования выхода из строя) центрального пункта. Устройство также может быть применено приисследовании структур, представленных графами типа дерево, с целью выявления неизоморфных деревьев.формула изобретенияУстройство для исследования графов, содержащее матрицу из ИхИ 2 О моделей ребер, группу элементов ИЛИ, группу счетчиков, группу элементов И, группу триггеров, группу ключей, генератор импульсов, распределитель импульсов и регистр, вход запуска генератора импульсов является входом запуска устройства, а выход генератора импульсов подключен к входу распределителя импульсов, каждый -й выход которого (=1,2И) под-ЗО ключен к первому информационному вхо,ду каждой модели ребра -го столбца матрицы моделей ребер, вторые информационные входы моделей ребер -го столбца матрицы объединены и 35 подключены к выходу 1-го ключа группы, выход каждой 1-й модели ребра (3=1,2И) и 1-й строки матрицы подключен к 3-му входу х-го элемента ИЛИ группы, выход которого подключен О к счетному входу -го счетчика группы, (0+1)-й выход распределителя импульсов подключен к первым входам элементов И группы, выход каждогоэлемента И группы подключен к входуодноименного триггера группы, выходкоторого подключен к управляющемувходу одноименного ключа группы,о т л и ч а ю щ е е с я тем, что,с целью расширения функциональныхвозможностей за счет определенияцентра графа, в него введены сумматор, дешифратор, блок вычитания, элемент ИЛИ и группа дешифраторов единиц причем выход каждого счетчикагруппы подключен к входу одноименного дешифратора единицы группы, выход каждого дешифратора единицы группы подключен к информационному входусоответствующего ключа группы и квторому входу одноименного элемента Игруппы, (И+1)-й выход распределителяимпульсов подключен к входам сбросасчетчиков группы и входу разрешениясчета сумматора, выход 1-го ключагруппы подключен к 1-му информационному входу сумматора, выход которогоподключен к первому входу блока вычитания, второй вход которого подключенк выходу регистра, выход блока вычитания подключен к входу дешифратора,выходы которого подключены к соответствующим входам элемента ИЛИ, выходэлемента ИЛИ подключен к входу останова генератора импульсов. 2, Устройство по и. 1, о т л ич а ю щ е е с я тем, что, модель ребра содержит триггер и элемент И, выход которого является выходом модели ребра, первый вход элемента И является первым информационным входом модели ребра, а второй вход элемента И подключен к выходу триггера, вход которого является вторым информационным входом модели ребра.1288710 Составитель Т.СапуноРедактор Н.Бобкова Техред Л.Олейник рректор Т.Кол Заказ 7810/ вен рете Жоизводственно-полиграфическое предприятие, г.ужгород, ул. Проектная Тираж 67 ВНИИПИ Государст по делам изоб 113035, Москва, Подписноео комитета СССРй и открытийРаушская наб., д. 4