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

 

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

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

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

РЕСПУБЛИК (19) (1I) А1

L (5!) 4 (06 F !5/20

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ

ОПИСАНИЕ ИЗОБРЕТЕНИЙ,„ - " ::;."., К А ВТОРСКОМУ СВИДЕТЕЛЬСТВУ (- -, " - - "-.М

° °

° 4 (21 ) 4275962/24-24 (22) 03.07.87 (46) 15.12.88. Бил. ¹ 46 (72) Е.И.Бороденко, Л.Г.Подзубанов, В,А.Синица, И.В.1(артавых и В.В.Верияскин (53) 681,333(088.8) (56) Авторское свидетельство СССР

¹- 637822, кл. 0 06 F 15/20, !978.

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

2 определения связности вершин графа, элемент ИЛИ 3, вход 4 начальной установки устройства, тактовый выход

5 блока синхронизации, вход 6 опроса

l 444809 блока 2, выход 7 признака связности всех вершин графа, вход 8 останона блока l, выходы 9 группы блока 1, вход 10 задания истока подграфа, вход 11 пуска устройства, блок 12 задания топологии графа, элементы ИЛИ 13 группы, элемент И 14, входы 15 опроса вершин графа блока 12, выходы 16 признаков достижимости вершин графа блока 12, вход 17 разрешения работы блока 12, триггеры 18 матрицы, элементы ИЛИ 19 группы, элементы И 20 группы, элементы И 21 матриИзобретение относится к вычислительной технике и может быть использовано для анализа связности вершин графа.

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

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

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

Опроса блока 2 определения связности вершин графа, выход 7 признака связности всех вершин -графа которого подключен к второму входу элемента 3

ИЛИ, выход которОГО подключен к вхо- 25 ду 8 останова блока 1 синхронизации, М-й выход 9 группы которого подключен к М-му входу 10 задания истока подграфа (М=l,...,В, где  — количество вершин в графе), вход II пуска 30 ус гройства подключен к входу пуска блока 1 синхронизации. Блок 2 определения связности вершин графа содержит блок )2 вадания топологии, группу из

В элементов ИЛИ 13 и элемент И 14„ выход 7 которого является выходом признака связности всех вершин графа, цы и входы 22 признаков наличия ветвей между в ерши нами гр афа . По сле пуска блок 1 синхронизации производит последовательный опрос вершин графа, В там случае, если опрошенная вершина является истоком rpaAa, на выходе 7 появляется сигнал уровня логической единицы, который останавливает блок синхронизации. Выход

9, на котором присутствует потенциал высокого уровня, соответствует номеру вершины, являющейся истоком графа. 2 ил. причем M-й вход 10 задания истока подграфа подключен к второму входу

М-гс. элемента ИЛИ 13, выход которого подключен к входу 15 опроса M-й вершины графа блока l 2 задания топологии, выход !6 признака достижимости

К-й ветви графа которого (K=) В) подключен к К-му нходу элемента И 14 и к первому нходу К-го элемента ИЛИ

13, вход 6 опроса блока 2 определения связности подключен к входу 17 разрешения работы блока 12 задания топологии графа.

Блок 12 задания топологии содержит матрицу из В > В триггеров 18, группу из В элементов ИЛИ 19, группу из В элементов И 20 и матрицу из

В В элементон И 21, причем вход 22 признака наличия ветви из M-Й в К-ю вершину графа подключен к входу установки в единицу К-го триггера M-й строки матрицы.

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

Перед началом работы на вход 4 начальной установки подают импульсный сигнал уровня. "I, при этом происходит установка в исходное состояние блока 2 определения связности вершин графа и блока 1 синхронизации. В блок " заносится информация о топологии графа. На нход 11 пуска устройства подают импульсный сигнал единичного уровня, при этом блок 1 синхронизации формирует импульсные

1444809 сигналы уровня "1" в соответствии с временной диаграммой работы (фиг.2).

Импульсный сигнал уровня "1 появляется на первом выходе 9 блока 1 син5 хронизации, при этом блок 2 подготавливаетсяся к определению вершин, связных с первой вершиной, Через время Тl, достаточное для подготовки блока 2, блок 1 синхронизации формирует 10 импульсный сигнал уровня "1" на выходе 5, при этом производится опрос блока 2, В том случае, если все вершины графа связаны, на выходе 7 блока

2 появляется импульсный сигнал уров- >5 ня "1", при этом производится останов блока 1 синхронизации, а потенциал уровня "1" на первом выходе 9 блока 1 синхронизации является признаком соответствия первой вершины исто- 20 ку rpaAa (т.е. из первой вершины может быть достигнута любая вершина графа). В том случае, если из первой вершины все остальные вершины достигнуты быть не могут, сигнал на выходе .7 блока 2 не появляется и через время Т2, достаточное для опроса блока

2, блок 1 синхронизации снимает сигнал уровня "1" со своего первого выхода 9 и формирует его на втором вы- 30 ходе 9, После этого работа устройства повторяется. Если rpaA не имеет истока, то через В циклов опроса сигнал уровня "1" появляется на В+1-м выходе 9. При этом происходит останов З5 блока синхронизации, а потенциал уровня "1" на В+1-м выходе блока 1 служит признаком отсутствия истока в графе.

Блок 2, определения связности ра- 40 ботает следующим образом. достаточное для окончания переходных процессов, на выходах 16 формируется состав всех вершин, связных с M-й.

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

7 блока 2.

Блок 12 задания топологии работает следующим образом.

Сигнал уровня "1" на входе 4 устанавливает все триггеры 18 матрицы в нулевое состояние. На вход 22 установки в единицу М-ro триггера 18

К-й строки матрицы подают импульсный сигнал единичного уровня (при наличии ветви из М-й в К-ю вершину графа), Тем самым задают топологию графа в соответствии с его матрицей смежности. При наличии сигналов уровня

"1" на входе 17 разрешения работы и

М-и входе 15 опроса блок 12 выдает сигналы уровня " 1" на те выходы 16, соответствующие которым триггеры 18

М-й строки матрицы установлены в единичное состояние, Перед началом работы на вход 4 начальной установки подают импульсныи сигнал уровня > При этом IIpo 45 исходит установка в исходное состояние блока 12 задания топологии графа, В блок 12 заносится информация о топологии графа, При поступлении на М-й вход 10 задания истока подграфа сигнала уровня "1" производится опрос М-й вершины графа, при этом блок 12 при наличии сигнала уровня

"1" на входе 17 разрешения работы выдает на свои выходы 16 сигналы уровня "1", позиции которых соответствуют составу вершин, связных с M-й.

Указанные сигналы поступают на соответствующие входы 15 и через время, Формула изобретения

Устройство для анализа параметров графа, содержащее матрицу из В Х В триггеров, гце B — количество вершин в графе, матрицу из В л В элементов

И, первую группу из B элементов ИЛИ и элемент И, причем вход начальной установки устройства подключен к входам установки в "О" всех триггеров матрицы, вход признака наличия пути из М-й в К-ю вершину графа (К=l...,В

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

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

И, элемент ИЛИ и блок синхронизации, вход пуска которого является входом пуска устройства, вход начальной ус1444809

Со стави гель А. Мишин, Редактор M.Öèòêèíà Техред А.Кравчук

Корректор В;Бутяга

Заказ á508/50 Тираж 704 Подписное

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

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

II изводственно-полиграфическое предприятие, г. ж р д, у . р

У ro о л. П оектная 4 роизв

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

5 ментов И М-й строки матрицы (В+1)-й

1 выход группы блока синхронизации является выходом признака отсутствия истока в графе устройства и подключен к первому входу элемента ИЛИ, выход элемента И подключен к второму входу элемента HJIH выход которого подключен к входу останова блока синхронизации.