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

(Л

4

00

о

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

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

1

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

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

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

Устройство содержит блок 1 синхронизации, блок 2 определения связ-

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

причем М-й вход 10 задания истока подграфа подключен к второму входу элемента ИЛИ 13, выход которого подключен к входу 15 опроса М-й вершины графа блока 12 задания топологии, выход 16 признака достижимости К-й .ветви графа которого (,,,,,В) подключен к К-му входу элемента И 14 и к первому входу К-го элемента ИЛИ 13, вход 6 опроса блока 2 определения связности подключен к входу 17 разрешения работы блока 12 задания топологии графа.

Блок .12 задания топологии содержит матрицу из В f В триггеров 18, группу из В элементов ИЛИ 19, группу из В элементов И 20 и матрицу из В « В элементов И 21, причем вход 22 признака наличия ветви из М-й в К-ю вершину графа подключен к входу установки в единицу К-го триггера Н-й строки матрицу.

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

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

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

2 появляется импульсный сигнал уров- 15 в нулевое состояние. На вход 22 установки в единицу М-го триггера 18 К-й строки матрицы подают импульсный сигнал единичного уровня (.при наличии ветви из М-й в К-ю вершину граня 1, при этом производится останов блока 1 синхронизации, а потенциал уровня 1 на первом выходе 9 блока 1 синхронизации является признаком соответствия первой вершины исто-20 Фа) . Тем самым задают топологию гра- ку графа (т.е. из первой верпины мо- Фа в соответствии с его матрицей смеж- жет быть достигнута любая вериина графа). В том случае, если из первой вершины все остальные вершины достигнуты быть не могут, сигнал на выходе 7 блока 2 не появляется и через время Т2, достаточное для опроса блока 2, блок 1 синхронизации снимает сигности. При наличии сигналов уровня 1 на входе 17 разрешения работы и М-м входе 15 опроса блок 12 выдает 25 сигналы уровня 1 на те выходы 16, соответствуюшяе которым триггеры 18 М-й строки матрицы установлены в единичное состояние.

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

Устройство для анализа параметров графа, содержавшее матрицу из В л В

выходе 9. При этом происходит останов оц триггеров, где В - количество верпшн

л -. Т „ П .

блока синхронизации, а потенциал уровня 1 на В+1-м выходе блока I служит признаком отсутствия истока в графе.

Блок 2, определения связности работает следуюшлм образом.

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

ный сигнал уровня

при этом происходит установка в исходное состояние блока 12 задания топологии графа. В блок 12 заносится информация о топологии графа. При поступлении на М-й вход 10 задания истока подграфа сигнала уровня 1 производит- ся опрос М-й вершины графа, при этом блок 12 при наличии сигнала уровня 1 на входе 17 разрешения работы

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

50

выдает на свои выходы 16 сигналы ypoB-gj. в него введены вторая группа из В ня 1, позиции которых соответству- элементов ИЛИ, группа из В элементов ют составу веришн, связных с М-й. Указанные сигналы поступают на соответствующие входы 15 и через время.

И, элемент ИЛИ и блок синхронизации, вход пуска которого является входом пуска устройства, вход начальной усдостаточное для окончания переходных процессов, на выходах 16 формируется состав всех веригин, связных с М-й. Если связными являются все вершины графа, на выходе элемента появляется сигнал уровня логической единигП), который в качестве признака связности всех вершин графа поступает на выход 7 блока 2.

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

Сигнал уровня 1 на входе 4 устанавливает все триггеры 18 матрицы

Фа) . Тем самым задают топологию гра- Фа в соответствии с его матрицей сме

ности. При наличии сигналов уровня 1 на входе 17 разрешения работы и М-м входе 15 опроса блок 12 выдает сигналы уровня 1 на те выходы 16, соответствуюшяе которым триггеры 18 М-й строки матрицы установлены в единичное состояние.

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

Устройство для анализа параметров графа, содержавшее матрицу из В л В

триггеров, где В - количество верпшн

л -. Т „ П .

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

в него введены вторая группа из В элементов ИЛИ, группа из В элементов

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

рого подключен к второму входу М-го элемента И группы, выход которого подключен к вторым входам всех элементов И М-й строки матрицы( )-й выход группы блока синхронизации является выходом признака отсутствия истока в графе устройства и подключен к первому входу элемента ИЛИ, выход элемента И подключен к второму входу элемента ИШi, выход которого подключен к входу останова блока синхронизации.