SU1444809A1

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

Info

Publication number: SU1444809A1
Application number: SU874275962A
Authority: SU
Inventors: Евгений Иванович Бороденко; Леонид Геннадьевич Подзубанов; Виктор Алексеевич Синица; Игорь Витальевич Картавых; Владимир Викторович Верияскин
Priority date: 1987-07-03
Filing date: 1987-07-03
Publication date: 1988-12-15

Abstract

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

Description

(Л

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

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

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

На фиг. 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 М-й строки матрицы установлены в единичное состо ние.

Claims

нал уровн 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, выход которого подключен к входу останова блока синхронизации .