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

 

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

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

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

ГОСУДАРСТВЕ HHblA КОМИТЕТ

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

ПРИ ГКНТ СССР

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

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

М 1444809, кл. G 06 F 15/20, 1987.

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

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

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

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

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

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

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

Перед началом работы обнуляют накапливающий блок 4 логического сложения, в блок 3 задания матрицы смежности заносят информацию о топологии графа.

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

25

40 если иэ первой вершины достижимы все остальные вершины графа, на выходе 9 блока 2 появляется сигнал уровня логической единицы. Через время, достаточное для окончания проверки принадлежности вершины массиву истоков, блок 1 синхронизации формирует сигнал уровня логической единицы на выходе 7. Г)ри э ом накапливающий блок 4 логического сложения (при наличии сигнала уровня логической единицы на выходе 9) добавляет(no ИЛИ) nspsye вершину к текущему массиву истоков.. Через время, достаточное для окончания операции логического сложения в блоке 4, блок

1 синхронизации снимает сигналы уровня логической единицы с первого выхода 8 и выхода 7 и формирует сигнал уровня логической единицы на втором выходе 8. Далее работа устройства повторяется до тех пор, пока не будут проверены все вершины графа, при этом на выходах 10 устройства будет сформирован массив истоков графа.

Блок 2 определения достижимых вершин содержит матрицу из В х В элементов

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

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

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

16 признака достижимости К-й вершины блока 2 и подключен.к второму входу М-ro элемента И группы и к М-у входу элемента

И-14, выход которого является выходом 9 признака достижимости всех вершин графа блока 2.

Блок 2 определения достижимых вершин работает следующим образом.

На входы 15 блока подается информация о топологии графа. На один из входов

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

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

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

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

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

Редактор H.Êàìåíñêàÿ Техред М.Моргентал Корректор С.Шевкун

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

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

1 l3035, Москва, Ж-35, Раушская наб.. 4/5

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