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

 

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

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

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

РЕСПУБЛИН (19) (11) 23 (51)4 G 06 F 15 20

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

К АSTOPCHOMV СВИДЕТЕЛЬСТВУ

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

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

ПРИ ГННТ СССР! (21) 4243997/24-24 (22) 13.05.87 (46) 23.09.89. Бюл. У 35 (72) А.И.Багрич и С.В.Тальянский (53) 681.333 (088.8) (56) Авторское свидетельство СССР

М- .896630, кл. G 06 F 15/20, 1982.

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

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

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

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

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

Устройство содержит матрицу из

ВхВ триггеров 1, где B — количество вершин в графе, первую матрицу из

ВхВ элементов И 2, вторую матрицу из

ВхВ элементов И 3, группу из ВхВ элементов 4 задержки, первую группу из

В элементов ИЛИ 5, вторую группу иэ

В элементов ИЛИ 6, третью группу из

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

После опроса всех вершин графа устройство формирует признак окончания работы. 3 ил. геров 8, элемент И 9, первый 10 и. второй 11 счетчики, первый 12 и второй 13 элементы ИЛИ и блок 14 синхронизации.

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

24 признака окончания работы устройства, выходы 25 группы блока 15 синхронизации, первый выход 26 блока 15

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

15 синхронизации.

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

На вход 16 начальной установки подают импульсный сигнал единичного уров- 10 ня, при этом устанавливаются s "0"

see триггеры 1, в исходное состояниеблок 14 синхронизации, в счетчик 11 заносится код числа шесть, Подаются импульсные сигналы единичного уров-. ня на входы 18 второго триггера первой строки, пятого триггера четвертой строки, четвертого триггера пятой строки матрицы, таким образом задают ненаправленные дуги, пятый 20 триггер 1 шестой строки матрицы и шестой триггер 1 пятой строки матрицы. При этом указанные триггеры 1 устанавливаются в единичное состояние.

На вход 17 пуска устройства пода- 25 ют импульсный сигнал единичного. уровня, при этом блок 14 синхронизации начинает вырабатывать сигналы в соответствии с временной диаграммой его работы, Сигнал единичного уровня по- 30 является на первом выходе 26 блока

l4 синхронизации, при этом устанавливаются в "0" все триггеры Я и на счетчик 10 в счетчик ll заносится

"1".. Сигнал единичного уровня появля- 35 ется на первом выходе 25 группы б тока синхронизации, при этом устанавливается в "1" второй триггер 8 группы (первая вершина связана с второй вершиной первого подграфа).Через время 40

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

Величина задержки в каждом элементе 4 выбрана из того условия, чтобы импульсы на выходе элемента ИЛИ 12 фиксировались раздельно. ЧеРез врем,55

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

0 — для третьей (изолированной вершины) и 000111 и 4 — для четвертой,пятой и шестой вершин (графа). После опроса шестой вершины по импульсу на выходе 26 блока 14 счетчик 11 переходит через "0", при этом останавливается блок 14 синхронизации и на выход 24 устройства выдается сигнал единичного уровня в качестве призна ка окончания работы.

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

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

К-го триггера M-й строки матрицы,выход которого подключен к первому входу К-го элемента И M-й строки первой матрицы, выход которого подключен к

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

5 150992 второй матриц и к входу (КхМ+1)-ro элемента задержки той же группы (Кх".1 ВхВ), выход К-ro элемента

ИЖ первой группы подключен к K-му

5 входу элемента И, выход которого является выходом признака связности всех вершин графа устройства, о т— л и ч а ю щ е е с я тем, что, с целью расширения функциональных воз- 1{) можностей устройства за счет определения характеристик связности каждой вершины графа, в него введены группа из В триггеров, второй элемент ИЛИ, второй счетчик и блок синхронизации, 15 причем вход начальной установки устройства подключен к входу начальной установки блока синхронизации и к входу признака записи второго счетчика, первый выход блока синхронизации 20 подключен к входу установки в "0" первого счетчика, к вычитающему входу второго счетчика и к входам установки в "0" всех триггеров группы, выход К-го элемента ИЛИ первой груп- 25 пы подключен к первому входу К-го элемента ИЛИ третьей группы и к вхо3 6 ду установки в "1 К-го триггера группы, выход которого является вы ходом признака принадлежности подграфу К-й вершины графа устройства,выход ВхВ-ro элемента задержки группы является выходом признака выдачи информации устройства и подключен, к первому входу второго элемента ИЛИ, вход пуска устройства подключен к второму входу второго элемента ИЛИ, выход которого подключен к входу пуска блока синхронизации, М-й выход группы которого подключен к второму входу М-ro элемента ИЛИ третьей группы, выход которого подключен к вторым входам всех элементов И М-й строки первой матрицы, вход задания количества вершин в графе устройства под-:. ключен к информационному входу второго счетчика, выход признака перехода через ноль которого является выходом признака окончания работы устройства и подключен к входу останова блока синхронизации, второй выход которого подключен к входу первого элемента задержки группы, 1509923

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

Редактор М.Бланар Техред Л.Олийнык Корректор О.Цыпле

Заказ 5815/48 Тираж 668 Подписное

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

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

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