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

 

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

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

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

РЕСПУБЛИК ((9) (11) (sx)s G 06 F 15/419

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

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

ПРИ ГКНТ СССР

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

/О

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (21) 4389706/24 (22) 09.03.88 (46) 07.10.91. Бюл. М 37 (72) E.È.Áîðîäåíêo, Л.Г.Подзубанов, B.A.ÑèHèöà, И,В.Картавых и А.Л.Гостев (53) 681.333(088.8) (56) Авторское свидетельство СССР

М 1320814,.кл; 6 06 F 15/20, 1986, Авторское свидетельство СССР

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

При этом на выходе 12 устройства формиру-, З ется признак связности графа на нулевом уровне бинарных отношений. 3 ил.

1683034

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

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

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

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

10 задания допустимых полустепеней эахо5

10 да устройства, вход 11 задания допустимых полустепеней исхода устройства. выход 12 признака связности графа на нулевом уровне бинарных отношений, На фиг.2 обозначена группа иэ В сумма- 25 торов 13, где  — количество вершин в графе, вхоДы 14 признаков наличия дуг и выходы

15 полустепеней исхода вершин, причем вход 14 признака наличия (К, M)-й дуги подключен к входу К-ro слагаемого M-го сумма- 30 тора группы (К = 1„,, В; M = 1, „„В), выход которого является выходом 15 полустепени исхода M-й вершины блока 7 определения полустепеней исхода.

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

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

Перед началом работы в блок 1 задания матрицы смежности заносят информацию о топологии графа. При этом блоки 6 и 7 с пре- 45 деляют локальные степени всех его вершин.

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

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

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

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

К-й вершины блока задания матрицы смежности, выход признака наличия топологии нуль-графа которого является выходом признака связности графа на нулевом уровне бинарных отношений устройства, вход задания допустимой полустепени захода которого подключен к вторым информационным входам всех блоков сравнения первой группы, выход полустепени исхода M-й вершины блока определения полустепеней исхода подключен к первому информационному входу M-ro блока сравнения второй группы, выход признака "НЕ меньше" которого подключен к М-му разряду информационного входа второго регистра, M-й разряд информационного выхода которого подключен к входу признака удаления дуг, заходящих в M-ную вершину блока задания матрицы смежности, вход задания допустимой полустепени исхода устройства подключен. к вторым информационным входам всех блоков сравнения второй группы, первый тактовый вход устройства подклю1683034 знаков чтения первого и второго регистров. чен к входам признаков записи. а второй тактовый вход устройства — к входам приdue. 2 Ъ ИВ 1767 17вд

Ф ° ° ° ° °

° ° ° 7 52 ° ° е Я;у

7 2 Ь

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

Техред М.Моргентал Корректор М.Кучерявая

Редактор М.Бланар

Заказ 3415 Тираж,/ Подписное

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

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

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

, fkyg ф»

° ° ° ° ° °

/JAN g ° ° °

15 у l5 ð

+If At+

° Ф ° Ъ