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

 

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

СОЮЗ СОВЕТСКИХ

СОЦИАЛИСТИЧЕСКИХ

РЕСПУБЛИК (5!)5 G 06 F 15/20

ГОСУДАРСТВЕ ННЫЙ КОМИТЕТ

ПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМ

ПРИ ГКНТ СССР

ОПИСАНИЕ ИЗОБРЕТЕНИЯ,о, О

Ql о"

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (21) 4396694/24 (22) 24.03.88 (46) 15.05.91. Бюл, № 18 (72) Е,И.Бороденко, Л.Г.Подэубанов, В.А.Синица, В.В.Верияскин и И.В.Картавых (53) 681.333 (088.8) (56) Авторское свидетельство СССР № 1444809, кл. G 06 F 15/20, 1987.

Авторское свидетельство СССР

¹ 11555599335544,, кКл, G 06 F 15/20, 1988, (54) УСТРОЙСТВО ДЛЯ АНАЛИЗА. ПАРАМЕТРОВ ГРАФА (57) Изобретение относится к вычислительной технике и может быть использовано для исследования систем, описываемых графами. Целью изобретения является расширение функциональных воэможностей устройства за счет определения множества всех стоков графа. Устройство содержит

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

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

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

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

1649561

25

40

50 первом выходе 8 блока 1 синхронизации.

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

И .11, где  — количество вершин в графе, группу из В элементов И 12, группу из В элементов ИЛИ 13 и элемент И 14, причем вход 15 опроса К-й вершины блока 2 (К=1„..В) подключен к первому входу,К-го элемента И 12 группы, вьаод которого подключен к первым выходам всех элементов И

11 К-ro столбца матрицы, вход 16 признака наличия (К,M)-й дуги блока 2 (М=.1„„В) подключен к второму входу К-го элемента И 11

M-й строки матрицы, выход которого подключен к К-у входу М-го элемента ИЛИ 13 группы, выход которого является выходом

17 признака принадлежности M-й вершины массиву достигающих вершин блока 2 и подключен к второму входу М-го элемента

И 12 группы и к M-у входу элемента И 1.4; выход которого является выходом 9 признака достижимости вершины из всех вершин графа.

Блок 2 определения достигающих вершин работает следующим образом. На входы 16 признаков наличия дуг подается информация о топологии графа. На один из входов 15 подают потенциал уровня логической единицы. При этом на выходах 17, соответствующих вершинам, из которых может быть достигнута опрошенная вершина, появляются потенциалы уровня логической единицы. Если опрошенная вершина достижима из всех вершин графа, потенциал уровня логической единицы появляется на выходе блока 2.

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

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

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

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

° ° °

Щ 10 /ОЙ

gus. f

1649561

158 Ютв 1бВ

75r Ny 1@у 19z 16д ЯВ2

° °

° ° °

Составитель А.Мишин

Редактор Н.Каменская Техред М,Моргентал Корректор В,Гирняк

Производственно-издательский комбинат "Патент", r, Ужгород, ул.Гагарина, 101

Заказ 1870 Тираж 420 Подписное

ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР

113035, Москва, Ж-35, Раушская наб„4/5