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

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

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

I Изобретение относится к вычисли- 1 тельной технике и может.быть исполь- ; зовано для количественной оценки ; связности графов информационно-логи- ческих структур АСУ. I Целью изобретения является рас- ; ширение функциональных возможностей :устройства за счет определения нали- чия связи каждой вершины с остальными в ориентированном графе.

На чертеже представлена функциональная схема устройства. : Устройство для исследования связности графа содержит вход 1 установки устройства в исходное состояние, установочные входы 2 -2 V матрицу 3 ячеек формирования топологии, исследуемого графа, каждая ячейка которой содержит триггер 4 -, и элементы И 5,-j и 6 ,-j (где l ,2,...,п), счетчик 7, дешифратор 8, первую и вторую группы элементов ИЛИ 9 -9 и , группу элементов НЕ 11,,-11 генератор 12 тактовых Импульсов, регистрационную матрицу 13 ячеек, каждая ячейка которой содержит регистри рзтощий триггер 14,-: и элемент И 15Кроме того, обозначены группа триггеров 16, вход 17 запуска устройства.

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

Первоначально импульс с входа 1 переводит триггеры А , -4 матрицы 3 и регистрирующие триггеры 14 „ - матрицы 13 в нулевое состояние, подготавливая устройство к работе. Затем в .устройство через установочные входы 2 , -2 „ заносится информация о технологии графа. При этом триггер 4 jj ( ,n) устанавливается в единичное состояние, если есть информационная связь из i-й вершины в j-ю вершину графа. После этого на

15

20

5

0

5

0

5

0

5

вход 17 подается пусковой импульс и далее устройство работает по тактам.

В каждом такте определяются номера вершин, связанные с вершиной, соответствующей порядковому номеру такта. В каждом такте импульс с генератора 12 устанавливает триггеры нулевое состояние, а так-; же по ступает через счетчик 7 на де- -.. шифратор 8. На выходе дешифратора 8 возбуждается шина с номером, соответствующим порядковому номеру такта.

На первом такте высокий потенциал с первого выхода дешифратора В подается на первые входы элементов И 15,-15,1, первые строки матрицы 13 и через элемент ЕЛИ 10, поступает на первые входы элементов И 5„ -5 первой строки матрицы 3. Высокие потенциалы появляются на выходах только тех элементов И 5, S,, на вторые входы которых поданы высокие потенциалы с триггеров 4.,., -4 первой строки матрицы 3. Если все триггеры 11 1п 2Рвой строки матрицы находятся в единичном состоянии, то сигналы с выходов элементов И 5„ -5,„через элементы И 6, и элементы ИЛИ 9,1П

в

Л. Г1

Эр переводят триггеры 16,-16 единичное, состояние..Высокие потенциалы с выходов триггеров . через элементы И 1 5„-15; первой строки третьей группы поступают на регистрирующие триггеры 14„-14д, первой строки матрицы, и они перебрасываются в единичное состояние.

Если не все триггеры 4 -4/ первой строки матрицы 3, а только i-й триггер 4 ,. находится в -единичном состояний, то сигнал с соответствующего элемента И 5,. через элементы И 6. и ИЛИ 9j переводит триггер 16 в единичное состояние. Сигнал с выхода триггера 16 , через элемент И 15м

переводит регистрирующий триггер 14 в единичное состояние, через элемент НЕ 1 Ij запрещает прохождение сигналов через элементы И 6,,- -6 ,,,--го столца и через элементы ИЛИ 10. поступа ет на первые входы элементов И 5,-,- 5, строки. Если j-й триггер строки (ijtj) матрицы 3 находится в единичном состоянии, то сигнал с него через элементы И 5,-; у И 6 ,-jV и ИЛИ 9t переводит j-й триггер 16 в единичное состояние. Сигнал с выхода триггера 16 через элемент И переводит регистрирующий триггер 14 V. в единичное состояние, через элемент НЕ 11, запрещает прохождение сигналов через элементы И столбца матрицы 3 и через элемент ИЛИ 10 поступает на первые входы элементов И 5. -5. j-й строки.П J

В результате таких переключений в единичное состояние переводится часть шш все регистрирующие триггеры 14,, -14 первой строки матрицы.

На k-M такте импульс с выхода генератора 12 сбрасывает триггеры 16 16

в нулевое состояние, а также

1594558

поступает в счетчик 7. Информация о количестве поступивших импульсов из счетчика 7 поступает в дешифратор 8. В результате дешифрования на k-M выходе дешифратора 8 появляется высокий потенциал, который поступает через элемент ИЛИ 10. на элементы И 5j,-5y j-й cTpoK i. Дальше

O схема работает аналогично рассмотренному случаю на первом такте. В результате работы схемы на k-м такте все шш часть регистрирукяцих триггеров k-й строки матрицы

5 переходят в единичное состояние.

Едиш1чное состояние регистрирующего триггера 14-, расположенного в i-1 строке H,j-M столбце матрицы, свидетельствуют о том, что i-я верши0 на графа связана с j-й вершиной, т.е. существует хотя бы один путь о графе из j-й вершины в j-ю.

На п-м такте работы устройства определяются связи п-й вершины со

5 всеми остальными вершинами графа, а также сигнал с п-го выхода дешифратора 8 поступает на вход останова генератора 12 тактовых импульсов, и устройство прекращает работу.

Редактор И.Шмакова

Составитель С.Титова

Техред М.Дидык Корректор О.Ципле