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

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

графа

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

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

Устройство содержит матрицу из ВхВ триггеров 1, где В - количество вершин в графе, первую матрицу из ВхВ элементов И 2, вторую матрицу из ВхВ элементов ИЗ, группу из ВхВ элементов 4 задержки, первую группу из В элементов ИЖ 5, вторую группу из В элементов ИЛИ 6, третью группу из В элементов ИЛИ 7, группу из В триггеров 8, элемент И 9, первый 10 и. второй 11 счетчики, первый 12 и второй 13 элементы ИЛИ и блок 14 синхронизации

Кроме того, обозначены () вход 15 задания количества вершин в графе устройства, вход 16 начальной установки устройства, вход 17 пуска устройства, входы 18 признаков наличия ребер из М-й в К-ю вершину графа (,,В; К 1,,,в), выход 19 признака связности всех вершин графа устройства, выходы 20 признаков принадлежности подграфу К-й вершины графа устройства, выходы 21 количества ветвей, исходящих из М-й вершины графа, выход 22 количества ребер в подграфе устройства, выход 23 признака выдачи информации устройства, выход 2,4 признака окончания работы устройства, выходы 25 группы блока 15 синхронизации, первый выход 26 блока 15

СП

о :о со

1C

со

31509

синхронизации, второй выход 27 блока 15 синхронизациио

Пусть требуется определить характеристики связности каждой вершины графа (фигоЗ) Перед началом работы на вход 15 устройства подают код числа шесть (количество вершин в графе). На вход 16 начальной установки подают импульсный сигнал единичного уров- ня, при этом устанавливаются в О все триггеры 1, в исходное состояние - блок 14 синхронизации, в счетчик.11 заносится код числа шесть Подаются импульсные сигналы единичного уров-. ня на входы 18 второго триггера первой строки, пятого триггера четвертой строки, четвертого триггера пятой строки матрицы, таким образом задают ненаправленные дуги, пятый триггер 1 шестой строки матрицы и шестой триггер 1 пятой строки матри- цыо При этом указанные триггеры 1 устанавливаются в единичное состояние

На вход 17 пуска устройства пода- ют импульсный сигнал единичного/уровня, при этом блок Д синхронизации начинает вьфабатывать сигналы в соответствии с временной диаграммой его работЫо Сигнал единичного уровня по- является на первом выходе 26 блока 14 синхронизации, при этом устанавливаются в О все триггеры 8 и на счетчик 10 в счетчик 11 заносится Сигнал единичного уровня появля- ется на первом выходе 25 группы бло- .ка синхронизации, при этом устанавли- вается в 1 второй триггер 8 группы (первая вершина связана с второй вершиной первого подграфа)оЧерез время Т1, необходимое для Определения состава вершин достижимых из М-й вершины графа, (в данном случае из первой), на выходе 27 блока 14 синхронизации появляется импульсный сигнал единичного уровня. При этом на выходе элемента ИПИ 12 появляются импульсы единичного уровня, количество которых равно количеству ребер исходящих М-й вершины графа (в данном случае первой)

Величина задержки в каждом элементе 4 выбрана из того условия, чтобы импульсы на выходе элемента.ИЛИ 12 фшссировались раздельно. Через время Т2, достаточное для прохождения импульса через все элементы 4 задержки он появляется в качестве признака выдачи информации на выходе 23 устрой-

5 : 0 с 0 j

0

ства. По окончании действия импульса блок 14 синхронизации формирует импульсный сигнал единичного уровня на выходе 26„ При этом устанавливаются в О все триггеры 8 группы и счетчик lOj счетчик П фиксирует число четыре (количество неисследованных вершин). Далее устройство рабо- тает аналогично и на последующих шагах фиксируются числа 000000 (состав достижимых вершин в позиционном коде) и О - для второй вершины, -000000 и О - для третьей (изолированной вершины) и 000111 и 4 - для четвертой,пятой и шестой вершин (графд)„ После опроса шестой вершины по импульсу на выходе 26 блока 14 счетчик 11 переходит через О, при этом останавливается блок 14 синхронизации и на выход 24 устройства вьщается сигнал единичного уровня в качестве призна- ка окончания работы.

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

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

2SS

20 П

26

Фиг.1

Т/ тг п тг

TJ п

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

Физ.2

2 J

Фиг,3