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

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

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

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

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

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

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

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

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

ON Ю СЛ О

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

Блок 2 определения достигающих вершин содержит матрицу из В х В элементов И 11, где В - количество вершин в графе, группу из В элементов И 12, группу из В элементов ИЛИ 13 и элемент И 14, причем вход 15 опроса К-й вершины блока 2 (,...В) подключен к первому входу К-го элемента И 12 группы, выход которого подключен к первым выходам всех элементов И 11 К-го столбца матрицы, вход 16 признака наличия (К,М)-й дуги блока 2 (,.,.В) подключен к второму входу К-го элемента И 11 М-й строки матрицы, выход которого подключен к К-у входу М-го элемента ИЛИ 13 группы, выход которого является выходом 17 признака принадлежности М-й вершины массиву достигающих вершин блока 2 и подключен к второму входу М-го элемента И 12 группы и к М-у входу элемента И 14, выход которого является выходом 9 признака достижимости вершины из всех вершин графа.

Блок 2 определения достигающих вершин работает следующим образом. На входы 16 признаков наличия дуг подается информация о топологии графа. На один из

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

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

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

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

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

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

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

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

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

ю,юг ю8

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

фиг.1

15i 16ff 16& 15г 16П 16дг

0 000

L JL J

16П 16дг

0 000

15B 16,8 168&

0 ЙЦЭ a

ФигЗ