Устройство для исследования графов Советский патент 1987 года по МПК G06F15/173 

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

Цель . изобретения - расширение функциональных возможностей за счет определения вершины (двух вершин.), образующей центр (бицентр) дерева.

На чертеже представлена структурная схема устройства.

Устройство содержит распределитель 1 импульсов, матрицу 2 моделей ребер 3, каждая модель ребра 3 содержит элемент И 4 и триггер 5. Устрой- ство также содержит труппу элементов ИЛИ 6, группу счетчиков 7, группу дешифраторов единицы, группу триг - геров 9, группу элементов И 10, группу ключей 11, сумматор 12, регистр 13 блок 14 вычитания, дешифратор 15, элемент ИЛИ 16, генератор 17 импульсов.

Первоначально триггеры 5, соответствующие позициям матрицы смежности графа, в которых записаны единицы, устанавливают в единичное состояние, как и триггеры 9, в регистр 13 записывают код числа вершин графа, счетчики 7 и сумматор 12 обнуляют.

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

При поступлении пускового сигнала импульсы генератора 17 проходят на вход распределителя 1, который поочередно выдает импульсы на свои выходы Каждый импульс распределителя 1 проходит через те элементы И 4 соответствующего столбца матрицы 2, на пер вый вход,которых поступает единичный сигнал с выхода триггеров 5. После прохождения импульсов распределителя через каждый элемент ИЛИ 6 на вход счетчика 7 поступает столько импульсов, сколько триггеров 5 находятся в единичном состоянии в соответствую щей строке матрицы 2.

Код числа .поступивших импульсов с выхода каждого счетчика 7 поступае на вход соответствующего дешифратора 8, который выдает на выход единич ньй сигнал лишь .в случае, когда показания счетчика 7 равны единицы. Единичный сигнал с выхода дешифратора 8 проходит через ключ 11 на вход сумматора 12, поскольку на управляющий вход ключа 11 поступает единичный потенциал с выхода триггера 9, и открывает элемент И 10 При поступлении (п+1)-го импульса распределителя 1

O

5

., 0 25

зо

,- Q

Q гг

сумматор 12 суммирует общее число единиц, поступающих на его входы с выходов ключей 11, код результата остается в сумматоре 12 и, кроме того, поступает на первьй вход блока 14, на второй вход которого поступает код числа с выхода регистра 13. Разность n-S поступ.ает на вход дешифратора 15, который вьщает сигнал на свой первый или второй выходы, если .только разность равна единице или двум соответственно.

Одновременно сигналы с вькодов тех или иных ключей 11 поступают на входы установки в ноль триггеров 5 соответствующих столбцов матрицы 2 и переводят эти триггеры в нулевое состояние, вследствие чего закрываются соответствующие элементы И 4 для прохождения импульсов распределителя 1 в последующих циклах его работы.

Кроме того, импульс с (N+1)-ro выхода распределителя 1 проходит через те элементы И 10, которые открыты единичным сигналам с выхода соответствующих дешифраторов 8, и перебрасывает соответстБую1Цие триггеры 9 в нулевое состояние (уже до конца работы устройства), вследствие чего закрываются соответствующие ключи 11. Задним фронтом п+1 импульс распределителя 1 обнуляет счетчики 7. Таким образом, после первого цикла работы распределителя 1 в сумматоре 12 хранится некоторое число S, численно равное числу вершин графа, каждой из которых инцидентно всего одно ребро. При этом триггеры 5 столбцов матрицы 2, соответствующие этим вершинам, сброшены в ноль, а соответствутащие ключи 11 закрыты до конца работы устройства. Все счетчики 7 обнулены. С каждым новьм циклом работы распределителя 1 накапливаемая в сумматоре 12 сумма S возрастает и, наконец, после какого-то цикла разность n-S становится равной двум и единице. Код этой разности с выхода блока 14 вычитания поступает на вход дешифратора 15, который в этом случае выдает на один из своих выходов сиг- нап, который через элемент ИЛИ 16 поступает на вход останова генератора 17, прекращая работу устройства. Номер столбца, в котором триггеры 5 остались в единичном состоянии, указывает вершину - центр дерева, а если таких столбцов два, то соответствующие две вершины образуют бйцентр дерева, нахождение которого необходимо для выбора резервных пунктов управления в иерархических системах управления, адаптированных к изменяю щимся условиям обстановки путем передачи управления тому или иному промежуточному пункту в случае выхо- ;да из строя (прогнозирования выхода из строя) центрального пункта. Устройство также может быть применено при исследовании структур, представленных графами типа дерево, с целью выявления неизоморфных деревьев.

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

1. Устройство дпя исследования графов, содержащее матрицу из NxN моделей ребер, группу элементов ИЛИ, группу счетчиков, группу элементов И, г руппу триггеров, группу ключей, генератор импульЪо в, распределитель импульсов и регистр, вход запуска генератора импульсов является входом запуска устройства, а выход генератора импульсов подключен к входу распределителя импульсов, каждый i-й выход которого (,2,...,N) под ключен к первому информационному вхо ,ду каждой модели ребра i-ro столбца матрицы моделей ребер, вторые информационные входы моделей ребер i-ro столбца матрицы объединены и подключены к выходу j-ro ключа группы, выход каждой j-й модели ребра (,2,...,N) и i-й строки матрицы подключен к j-му входу i-ro элемента ИЛИ группы, выход которого подключен к счетному входу i-ro счетчика группы, (Н+1)-й выход распределителя импульсов подключен к первым входам

5

5

0 5 0

элементов И группы, выход каждого элемента И группь подключен к входу одноименного триггера группы, выход которого подключен к управляющему входу одноименного ключа группы, отличающееся тем, что, с целью расширения функциональных возможностей за счет определения центра графа, в него введены сумматор, дещифратор, блок вычитания, элемент ИЛИ и группа дешифраторов еди- ниц, причем выход каждого счетчика группы подключен к входу одноименного дешифратора единицы группы, выход каждого дешифратора единицы группы подключен к информационному входу соответствующего ключа группы и к второму входу одноименного элемента И группы, (Н+1)-й выход распределителя импульсов подключен к входам сброса счетчиков группы и входу разрешения счета сумматора, выход i-ro ключа группы подключен к i-му информационному входу сумматора, выход которого подключен к первому -входу блока вычитания, второй вход которого подключен к выходу регистра, выход блока вычитания подключен к входу дешифратора, выходы которого подключены к соответствующим входам элемента ИЛИ, выход. элемента ШШ подключен, к входу останова генератора импульсов.

2. Устройство по п. 1, отличающееся тем, что, модель ребра содержит триггер и элемент И, выход которого является выходом модели ребра, первый вход элемента И является первым информационным входом модели ребра, а второй вход элемента И подключен к выходу триггера, вход которого является вторым информационным входом модели ребра.

Изобретение относится к области вычислительной техники и может быть использовано для решения на графах задач нахождения центра (бицентра) дерева. Это необходимо при выборе резервных пунктов управления в иерархических системах управления, адаптированных к изменяющимся условиям обстановки путем передачи управления тому или иному промежуточному пункту в случае выхода из строя (прогнозирования выхода из строя) центрального пункта. Устройство также может быть применено при исследовании структур, представленных графами тийа дерево, с целью выявления неизоморфных деревьев. Целью изобретения является расширение функциональных возможностей за счет определения вершины (двух вершин), образующей центр (би- центр) дерева. Устройство содержит распределитель импульсов, матрицу моделей ребер., каждая модель ребра содержит элемент И и триггер. Устройство также содержит группу элементов ИЛИ, группу счетчиков, группу дешифраторов, группу триггеров, группу элементов И, группу ключей, сумматор, регистр, блок вычитания, дешифратор, элемент ИЛИ, генератор импульсов. 1 з.п. ф-лы, 1 ил. i (Л ю 00 00 s|