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

t-fif

3150

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

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

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

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

Блок 3 включает матрицу из « элементов И 12, где В - количество вершин в графе, и группу из В эле- ментов ИЛИ 13.

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

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

Перед началом работы в блок 1 задания матрицы смежности Заносят информацию о топологии графа, обнуля- ют накапливаюш.ий блок 5 логического сложения, в первый разряд регистра 2 сдвига заносят единицу.

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

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

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

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

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

2, Устройство по п. 1, отличающееся тем, что блок определения достигающих вершин содержит

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

Изобретение относится к вычислительной технике и может быть использовано для исследования достижимости ориентированных графов. Целью изобретения является расширение функциональных возможностей устройства за счет определения базы графа. Устройство содержит блок 1 задания матрицы смежности, регистр 2 сдвига, блок 3 определения достигающих вершин, блок 4 сравнения и накапливающий блок 5 логического сложения. Перед началом работы в блок 1 заносят информацию о топологии графа, обнуляют блок 5, в первый разряд регистра 2 заносят единицу (остальные разряды регистра 2 обнуляют). Опрашивают блок 4. При этом, если первая вершина не достижима ни из какой другой вершины или, другими словами, отсутствуют вершины, достигающие первую, сигналы уровня логической единицы на выходах 11 блока 3 отсутствуют и на выходе блока 4 появляется сигнал уровня логической единицы, который заносит информацию с выхода регистра 2 (по ИЛИ) в блок 5. В противном случае, если на выходах 11 присутствуют сигналы уровня логической единицы, импульс на выходе блока 4 не формируется и занесения информации в блок 5 не происходит. Сдвигая единицу в регистре 2, последовательно проверяют принадлежность соответствующих вершин составу базовых. 1 з.п. ф-лы, 2 ил.

матрицу из В В элементов- И и группу g достигающих вершин.

Редактор А.Огар

Составитель А.Мишин Техред М.Ходанич

Заказ 4870/46

Тираж 668

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

/ 3,s

фиг.2

Корректор И.Муска

Подписное