Устройство для исследования графов
Изобретение относится к области вычислительной техники и может быть использовано для решения на графах задач нахождения центра (бицентра) дерева. Это необходимо при выборе резервных пунктов управления в иерархических системах управления, адаптированных к изменяющимся условиям обстановки путем передачи управления тому или иному промежуточному пункту в случае выхода из строя (прогнозирования выхода из строя) центрального пункта. Устройство также может быть применено при исследовании структур, представленных графами тийа дерево, с целью выявления неизоморфных деревьев . Целью изобретения является расширение функциональных возможностей за счет определения вершины (двух вершин), образующей центр (бицентр) дерева. Устройство содержит распределитель импульсов, матрицу моделей ребер., каждая модель ребра содержит элемент И и триггер. Устройство также содержит группу элементов ИЛИ, группу счетчиков, группу дешифраторов, группу триггеров, группу элементов И, группу ключей, сумматор, регистр, блок вычитания, дешифратор, элемент ИЛИ, генератор импульсов. 1 з.п. ф-лы, 1 ил. i (Л ю 00 00 s|
СОЮЗ СОВЕТСКИХ
СОЦИАЛИСТИЧЕСКИХ
РЕСПУБЛИК
А1 (5ц 4 ° G 06 F 15/20
РХ.F.<-".т-:щ у
ОЛИСАНИЕ ИЗОБРЕТЕНИЯ
К ASTOPCHOMV СВИДЕТЕЛЬСТВУ
1З, „13
4т J + Qg p
ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССР
ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ (21) 3875071/24-24 (22) 25.03.85 (46) 07.02.87. Бюл. У 5 (72) В.И.Балакирев и А.Г.Луценко (53) 681.333(088.8) (56) Авторское свидетельство СССР
У 679998, кл. G 06 G 7/48, 1977.
Авторское свидетельство СССР
Ф 1251049, кл. С 06 F 15/20, 1984. (54) УСТРОЙСТВО ДЛЯ ИССЛЕДОВАНИЯ
ГРАФОВ (57) Изобретение относится к области вычислительной техники и может быть использовано для решения на графах задач нахождения центра (бицентра) дерева. Это необходимо при выборе резервных пунктов управления в иерархических системах управления, адаптированных к изменяющимся условиям обстановки путем передачи управления тому.или иному промежуточному пункту
„SU, 2 710 в случае выхода из строя (прогнозирования выхода из строя) центрального пункта. Устройство также может быть применено при исследовании структур, представленных графами типа дерево, с целью выявления неизоморфных деревьев. Целью изобретения является расширение функциональных возможностей за счет определения вершины (двух вершин), образующей центр (бицентр) дерева. Устройство содержит распределитель импульсов, матрицу моделей ребер., каждая модель ребра содержит элемент И и триггер. Устройство также содержит группу элементов ИЛИ, группу счетчиков, группу дешифраторов, группу триггеров, группу элементов И, группу ключей, сумматор, регистр, блок вычитания, дешифратор, элемент ИЛИ, генератор .импульсов. 1 з.п. ф-лы, 1 ил.
128871
Изобретение относится к вычислительной технике и может быть использовано для решения на графах задач нахождения центра (бицентра) дерева.
Цель . изобретения — расширение функциональных возможностей за счет определения вершины (двух вершин), образующей центр (бицентр) дерева.
На чертеже представлена структур-. ная схема устройства.
Устройство содержит распределитель 1 импульсов, матрицу 2 моделей ребер 3, каждая модель ребра 3 содержит элемент И 4 и триггер 5. Устройство также содержит группу элементов
ИЛИ 6, группу счетчиков 7, группу дешифраторов 8 единицы, группу триг геров 9, группу элементов И 10, груп1 пу ключей 11, сумматор 12, регистр 13,20 блок 14 вычитания, дешифратор 15, элемент ИЛИ 16, генератор 17 импульсов.
Первоначально триггеры 5, соответствующие позициям матрицы смежности графа, в которых записаны единицы, 25 устанавливают в единичное состояние, как и триггеры 9, в регистр 13 записывают код числа вершин графа, счетчики 7 и сумматор t2 обнуляют.
Устройство работает следующим об- 30 разом.
При поступлении пускового сигнала импульсы генератора 17 проходят на вход распределителя 1, который поочередно выдает. импульсы на свои выходы.
Каждый импульс распределителя 1 проходит через те элементы И 4 соответствующего столбца матрицы 2, на первый вход, которых поступает единичный сигнал с выхода триггеров 5. После прохождения импульсов распределителя 1 через каждый элемент ИЛИ 6 на вход счетчика 7 поступает столько импульсов, сколько триггеров 5 находятся в единичном состоянии в соответствую- 15 щей строке матрицы 2.
Код числа поступивших импульсов с выхода калгдого счетчика 7 поступает на вход соответствующего дешифратора 8, который выдает на выход единич- >О ный сигнал лишь .в случае, когда показания счетчика 7 равны единицы. Единичный сигнал с выхода дешифратора 8 проходит через ключ 11 на вход сумматора 12, поскольку на управляющий .> вход ключа 11 поступает единичный потенциал с выхода триггера 9, и открывает элемент И 1О» При поступлении (n+i)-го импульса распределителя 1 сумматор 12 суммирует общее число единиц, поступающих на его входы с выходов ключей 11, код результата остается в сумматоре 12 и, кроме того, поступает на первый вход блока 14, на второй вход которого поступает код числа с выхода регистра t3. Разность и-Ь поступает на вход дешифратора 15, который выдает сигнал на свой первый или второй выходы, если .только разность равна единице или двум соответственно.
Одновременно сигналы с выходов тех или иных ключей 11 поступают на вхо-. ды установки в ноль триггеров 5 соответствующих столбцов матрицы 2 и переводят эти триггеры в нулевое состояние, вследствие чего закрываются соответствующие элементы И 4 для прохождения импульсов распределителя 1 в последующих циклах его работы.
Кроме того, импульс с (N+t)-го выхода распределителя 1 проходит через те элементы И 10, которые открыты единичным сигналам с выхода соответствующих дешифраторов 8, и перебрасывает соответствующие триггеры 9 в нулевое состояние (уже до конца работы устройства), вследствие чего закрываются соответствующие ключи 11.
Задним фронтом п+1 импульс распределителя 1 обнуляет счетчики 7. Таким образом, после первого цикла работы распределителя 1 в сумматоре 12 хранится некоторое число 5, численно равное числу вершин графа, каждой из которых инцидентно всего одно ребро.
При этом триггеры 5 столбцов матрицы 2, соответствующие этим вершинам, сброшены в ноль, а соответствующие ключи 11 закрыты до конца работы устройства. Все счетчики 7 обнулены.
С каждым новым циклом работы распределителя 1 накапливаемая в сумматоре 12 сумма Б возрастает и, наконец, после какого-то цикла разность п-S становится равной двум и единице, Код этой разности с выхода блока 14 вычитания поступает на вход дешифратора 15, который в этом случае выцает на один из своих выходов сигнал, который через элемент ИЛИ 16 поступает на вход останова генератора 17, прекращая работу устройства.
Номер столбца, в котором триггеры 5 остались в единичном состоянии, указывает вершину — центр дерева, а если таких столбцов два, то соответст128871Î вующие две вершины образуют бицентр дерева, нахождение которого необходимо для выбора резервных пунктов управления в иерархических системах управления, адаптированных к изменяю- 5 щимся условиям обстановки путем передачи управления тому или иному промежуточному пункту в случае выхо да из строя (прогнозирования выхода из строя) центрального пункта.
Устройство также может быть применено при исследовании структур, представленных графами типа дерево, с целью выявления неизоморфных деревьев.
Формула изобретения
Устройство для исследования графов, содержащее матрицу из NxNмоделей ребер, группу элементов ИЛИ, группу счетчиков, группу элементов И, руппу триггеров, группу ключей, генератор импульсов, распределитель импульсов и регистр, вход запуска генератора импульсов является входом запуска устройства, а выход генератора импульсов подключен к входу распределителя импульсов, каждый
i-й выход которого (i=1 2,...,N) под-З-О ключен к первому информационному вхо,ду каждой модели ребра i-го столб ца матрицы моделей ребер, вторые информационные входы моделей ребер
i-го столбца матрицы объединены и 35 подключены к выходу j-го ключа группы, выход каждой j-й модели ребра (j=1,2,...,N) и i-й строки матрицы подключен к j-му входу i-го элемента
ИЛИ группы, выход которого подключен к счетному входу i-го счетчика группы, (N+1)-й выход распределителя импульсов подключен к первым входам элементов И группы, выход каждого элемента И группы подключен к входу одноименного триггера группы, выход которого подключен к управляющему входу одноименного ключа группы, о т л и ч а ю щ е е с я тем, что, с целью расширения функциональных возможностей за счет определения центра графа, в него введены сумматор, дешифратор, блок вычитания, элемент ИЛИ и группа дешифраторов единиц причем выход каждого счетчика
Р группы подключен к входу одноименного дешифратора единицы группы, выход каждого дешифратора единицы группы подключен к информационному входу соответствующего ключа группы и к второму входу одноименного элемента И группы, (N+1)-й выход распределителя импульсов подключен к входам сброса счетчиков группы и входу разрешения счета сумматора, выход i-го ключа группы подключен к -му информационному входу сумматора, выход которого подключен к первому входу блока вычитания, второй вход которого подключен к выходу регистра, выход блока вычитания подключен к входу дешифратора, выходы которого подключены к соответствующим входам элемента ИЛИ, выход . элемента ИЛИ подключен к входу останова генератора импульсов.
2. Устройство по и. 1, о т л ич а ю щ е е с я тем, что, модель ребра содержит триггер и элемент И, выход которого является выходом модели ребра, первый вход элемента И является первым информационным входом модели ребра, а второй вход элемента И подключен к выходу триггера, вход которого является вторым информационным входом модели ребра.
12887 I 0
Составитель Т.Сапунова
Редактор Н.Бобкова Техред Л.Олейник Корректор Т.Колб
Заказ 7810/48 Тираж 673 Подписное
ВНИИПИ Государственного комитета СССР по делам изобретений и открытий
113035, Москва, Ж-35, Раушская наб., д. 4/5
Производственно-полиграфическое предприятие, r.Ужгород, ул. Проектная, 4
