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

ю

1

ел

00

СП

со

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

Цель изобретения - расширение функциональных возможностей устрой- ств а за счет разбиения множества вер ш{1н графа на подмножества вершин одного поколения.

На фиг.1 представлена функциональная схема устройства; на фиг.2 - временная диаграмма работы блока синхронизации.

Устройство содержит накапливающий бло: 1 логического сложения, блок 2 задания матрицы смежности, блок 3 определения полустепеней захода,блок

4регистрации матрицы расслоения,бло

5синхронизации,вход 6 пуска устройс ва, первый и второй выходы 7 и 8 блока 5 синхронизации, выходь 9 группы блока 5 синхронизации и выход 10 признака окончания работы устройства.

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

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

Перед началом работы устанавлива- ют Б ноль разряды блока 3, в блок 2 заносят информацию о топологии графа. При этом блок 3 выдает на свои выходы состав вершин, полустепени за- хода которых равны нулю (т.е. состав вершин не имеющих предков). На вход

6пуска устройства подают импульс уровня логической единицы. При этом блок 5 синхронизации формирует последовательность сигналов, преду- смотренную временной диаграммой его работы. Потенциал уровня логической единицы появляется на первом выходе

9 группы блока 5 синхронизации. При этом блок 4 регистрации подготавлива- ется к записи первой строки матрицы расслоения (первого слоя вершин). Через время, достаточное для окончания операции определения полусте- пеней захода, блок 5 синхронизации формирует импульс уровня логической единицы на выходе 7. При этом блок 4 фиксирует данные, поступившие на его информационный вход, накапливающий блок 1 логического сложения до- бавляет (по ИЛИ) к ранее накопленному значению данные, поступившие на его информационный вход. Через время, достаточное для выполнения указанных операций, блок 5 снимает по- тенциал уровня логической единицы с первого выхода 9 и формирует импульс уровня логической единицы на выходе 8. При этом блок 10 фиксирует на своем ВЫходе накопленное значение. При этом блок 2 задания матрицы смежности устанавливает в ноль (удаляет) столбцы матрицы смежности, а блок 3 определения полустепеней захода блокирует опрос тех вер-. шин, соответствующие которым разряды информационного выхода 10 блока установлены в единицу (тем самым удаляются дуги, исходящие из вершин вошедших во все уже выделенные слои, и запрещается определение полустепени захода для этих вершин). При этом блок 3 выдает на свои выходы состав вершин, полустепени захода которых равным единице. Далее блок 5 синхронизации вьщает потенциал уровня логической единицы на второй выход 9, и работа устройства повторяется.После того, как все слои вершин будут найдены, на выходе 10 признака окончания работы устройства появится потенциал уровня логической единицы. При этом в блоке 4 регистрации будут зафиксированы все слои вершин одного поколения.

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

Устройство для .решения задач на графах, содержащее блок задания матрицы смежности, блок синхронизации и блок регистрации матрицы расслоени причем вход пуска устройства подключен к входу пуска.блока синхронизации, выход которого подключен к входу признака записи блока регистрации матрицы расслоения, Р-й выход группы блока синхронизации (Р 1,.. С, где С - количество слоев в графе) подключен к Р-му адресному входу блока регистрации матрицы расслоения, отличающееся тем, что, с целью расширения функциональных возможностей устройства за счет разбиения множества вершин графа на подмножества вершин одного поколения, в него введены блок определения полустепеней захода и накапливающий блок логического сложения, причем первый выход блока синхронизации подключен к тактовому входу накапливающего блока логического сложения, К-й разряд информационного выхода которого (к 1,...,В, где В - количество вершин в графе) подключен к входу блокировки опроса К-й вершины блока определения полустепеней захода и к входу признака удаления (К-го столбца блока задания матрицы смежности, выход признака наличия (К,М)- го элемента которого (М 1,...,В)

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

Изобретение относится к вычислительной технике и может быть использовано для исследования связности графов. Целью изобретения является расширение функциональных возможностей устройства за счет разбиения множества вершин графа на подможества вершин одного поколения. Устройство содержит накапливающий блок логического сложения, блок 2 задания матрицы смежности, блок 3 определения полустепеней захода, блок 4 регистрации матрицы расслоения, блок 5 синхронизации, вход 6 пуска устройства, первый и второй выходы 7 и 8 блока 5 синхронизации, выходы 9 группы блока 5 синхронизации и выход 10 признака окончания работы устройства. Установив в "0" разряды блока 3, в блок 2 заносят информацию о топологии графа. На вход 6 пуска устройства подают импульс уровня логической единицы. При этом блок 5 синх0ронизации формирует последовательность сигналов, предусмотренную временной диаграммой его работы, под управлением которой в блоке 4 фиксируются все слои вершин одного поколения. 2 ил.

8

-TL

Составитель А.Мишин Редактор С.Патрушева Техред А.Кравчук. Корректор М.Кучерявая

Заказ 2422

Тираж 568

ЗНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР 113035, Москва, Ж-35, Раушская наб., д. 4/5

Фиг.2

Подписное