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

 

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

СОЮЗ СОВЕТСКИХ, СОЦИАЛИСТИЧЕСКИХ

РЕСПУБЛИК (19) (И) А1 (б1) 4 С 06 Г 15/20

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

К д BTOPCHOMY СВИДЕТЕЛЬСТВУ

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

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

ПРИ ГКНТ СССР (21) 4417511/24-24 (22) 29.02.88 (46) 15.08.89. Бюл. М 30 (71) Киевский политехнический институт им. 50-летия Великой Октябрьской социалистической революции (72) О.Н.Костюк (53) 681.333(088.8) (56) Авторское свидетельство СССР

1(1133596, кл. G 06 F 15/20, 1983 °

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

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

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

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

В противном случае, если на выходах

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

Сдвигая единицу в регистре 2, последовательно проверяют принадлежность соответствующих вершин составу базовых. 1 з.п. ф-лы, 2 ил.

3 1501084

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

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

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

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

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

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

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

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

Через время, достаточное для сдвига информации в регистре 2, на вход

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

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

Устройство для анализа параметров графа, содержащее блок задания матрицы смежности, регистр сдвига, блок определения достигающих вершин и блок сравнения, причем выход признака наличия дуги из К-й в М-ю вершину графа блока задания матрицы смежности (К-1 ° е В М-1,, >Ву где  — количество вершин графа) подключен к одноименному входу блока определения достигающих вершин, выход признака принадлежности М-й вершины составу достигающих вершин графа которого подключен к М-му разряду информационного входа блока сравнения, К-й разряд информационного выхода регистра сдвига подключен к входу опроса К-1 вершины графа блока определения достигающих вершин, о т." л и ч а ю щ е е с я тем, что, с целью расширения функциональных возможностей устройства за счет определения базы графа, в него введен накапливающий блок логического сложения, причем первый тактовый вход устройства подключен к входу признака сдвига регистра сдвига, К-й разряд информационного выхода которого подключен к K-му разряду информационного вхо5 1501084 6 да накапливающего блока логического из В элементов ИЛИ, причем вход опсложения, второй тактовый вход уст- роса К-й вершины графа блока опредеройства подключен к входу опроса ления достигающих вершин подключен к блока сравнения выход признака раУ

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

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

Ф Ф

4 Ф в

Ф

° М! ее фио2

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

Редактор А.Orap Техред М.Ходанич Корректор И.Муска

Заказ 4870/46

Тираж 668

Подписное

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

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

11 . \3

Производственно-издательский Kot4vHi1d 1 Llc1 åiir, г. жгород, ул. Гагарина, 101