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

t±t

Фиг I

О 00 СО

о

со

J

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

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

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

Устройство (фиг.1) содержит блок 1 задания матрицы смежности, регистры 2 и 3, блоки 4 и 5 сравнения групп, блок 6 определения полустепеней захода, блок 7 определения полустепеней исхода, первый 8 и второй 9 тактовые входы устройства, вход 10 задания допустимых полустепеней захода устройства, вход 11 задания допустимых полустепеней исхода устройства, выход 12 признака связности графа на нулевом уровне бинарных отношений.

На фиг.2 обозначена группа из В сумматоров 13, где В - количество вершин в графе, вхоДы 14 признаков наличия дуг и выходы 15 полустепеней исхода вершин, причем вход 14 признака наличия (К, М)-й дуги подключен к входу К-ro слагаемого М-го сумматорэ группы (К 1В; М 1В), выход

которого является выходом 15 полустепени исхода М-й вершины блока 7 определения полустепеней исхода.

На фиг.З обозначена группа из В сумматоров 16, причем вход 17 признаков наличия (К, М)-й дуги блока 6 подключен к входу М-го слагаемого К-го сумматора 16 группы, выход которого является выходом 18 полустепени захода К-й вершины блока 6.

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

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

вершины, номера которых зафиксированы в регистрах 2 и 3. Если в результате удаления получается нуль-граф (т.е. граф, состоящий из одних изолированных вершин), на выходе 11 устройства появляется сигнал уровня

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

Формула изобретения Устройство для анализа параметров

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

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

признака наличия (К, М}-й дуги блока задания матрицы смежности ( ,..., Е)

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

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

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

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

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

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

чен к входам признаков записи, а второй знаков чтения первого и второго регист- тактовый вход устройства - к входам при- ров.

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

#75, tS2

Пл Пт Пи пгв И М

7

Ю, $189

«

Фиг. 2

17я ав

М

1Вг

fa

J

%

Фиг.З