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

 

СООЗ СОВЕТСНИХ

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

РЕСПУБЛИН

А1

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

Н А ВТОРСНОМУ СВИДЕТЕЛЬСТВУ

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

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

ПРИ ГКНТ СССР (21) 3904220/24-24 (22) 03.06.85 (46) 23.09.90. Бюл. Р 35 (72) В.Л.Львов (53) 681.333(088.8) (56) Авторское свидетельство СССР

N9 716043, кл. G 06 F 15/20, 1980.

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

9 896630, кл. G 06 F 15/20, 1981, (54)(57) УСТРОЙСТВО ДЛЯ ИССЛЕДОВАНИЯ

СВЯЗНОСТИ ГРАФА, содержащее матрицу ячеек формирования топологии исследуемого графа и первую группу элементов ИЛИ по чиалу столбцов матрицы формирования топологии исследуемого графа, каждая ячейка матрицы формирования топологии исследуемого графа содержит триггер и первый элемент

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

НЕ по числу столбцов матрицы формирования топологии исследуемого графа, группа триггеров по числу столбцов матрицы формирования топологии исследуемого графа, вторая группа элементов ИЛИ по числу строк матрицы

ÄÄSUÄÄ 1594558 (g1)g G 06 F 15/20 формирования топологии исследуемого графа, дешифратор, счетчик, генера--тор тактовых импульсов и регистрацион-. ная матрица ячеек, каждая ячейка которой содержит элемент И и регистрирующий триггер, в каждую ячейку матрицы формирования топологии исследуемого графа введен второй элемент ..

И, первый вход которого подключен к выходу первого элемента И своей ячейки матрицы формирования топологии исследуемого графа, вторые входы вторых элементов И ячеек каждого j ñòîëáöà (где j-=1,2,...,п) матрицы формирования топологии исследуемого графа объединены и подключены к выходу

j-го элемента НЕ группы, выход второ" го элемента И каждой i-й ячейки (i=1,2,...,n) j-го столбца матрицы формирования топологии исследуемого графа подключен к j-му входу j-го элемента ИЛИ первой группы, выход

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

j-го триггера группы, выход которого подключен к входу j-ro элемента НЕ группы, к первому входу j-ro элемента ИЛИ второй группы и к первым входам всех элементов И j-ro столбца регнстрационной матрицы, в каждой ячейке регистрационной матрицы выход элемента: И подключен к входу установки в единицу регистрирующего триггера, входы установки в ноль регистрирующих триггеров всех ячеек регистра ционной матрицы объединены между собой и объединены с входами установки в ноль триггеров матрицы формирова-, ния топологии исследуемого графа, вторые входы всех элементов И ячеек 1594558

25 каждой i-н строки регистрационной матрицы объединены между собой, объединены с вторым входом i-ro элемента

ИЛИ второй группы и подключены к

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

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

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

На чертеже представлена функциональная схема устройства.

Устройство для исследования связности графа содержит вход 1 установки устройства в исходное состояние, установочные входы 2,„ -2„„-, матрицу

3 ячеек формирования топологии, исследуемого графа, каждая ячейка которой содержит триггер 4 " и элемен11 ты И 5; и 6;> (где i=j=1,2,...,n), счетчик 7, дешифратор 8, первую и 35 вторую группы элементов ИЛИ 9 „-9„и

10, †.10» группу элементов НЕ 11 „ -11„,, генератор 12 тактовых импульсов, регистрационную матрицу 13 ячеек, каждая ячейка которой содержит регистри- 40 рующий триггер 14 и элемент И 15 " . т1 I1

Кроме того, обозначены группа триг-, геров 16,- 16 „ и вход 17 запуска уст- ройства.

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

Первоначально импульс с входа

1 переводит триггеры 4, -4 „„матрицы

3 и регистрирующие триггеры 14 „—

14 „ матрицы 13 в нулевое состояние, пп подготавливая устройство к работе.

Затем в устройство через установочные входы 2,„ -2 „„ заносится информация о технологии графа. При этом триггер 4 " (ij=1,n) устанавливается в единичное состояние, если есть информационная связь из i-й вершины в )-ю вершину графа. После этого на графа, п-й выход дешифратора подключен к входу останова генератора тактовых импульсов, вход запуска которого является выходом запуска устройства, выход генератора тактовых импульсов подключен к входу дешнфратора и к входам установки в ноль всех триггеров группы, вход 17 подается пусковой импульс и далее устройство работает по тактам.

В каждом такте определяются номера вершин, связанные с вершиной, соответствующей порядковому номеру такта. В каждом такте импульс с генератора 12 устанавливает триггеры

16,-16 „ в нулевое состояние, а так-.:же поступает через счетчик 7.на дешифратор 8. На выходе дешифратора

8 возбуждается шина с номером, соответствующим порядковому номеру такта.

На первом такте высокий потенциал с первого выхода дешифратора 8 подается на первые входы элементов .

И 15 „ -15,„, первые строки матрицы 13 и через элемент ИЛИ 10 поступает

1 на первые входы элементов И 5 -5

11 1П первой строки матрицы 3. Высокие потенциалы появляются на выходах только тех элементов И 5 -5 на вто1 1Ь рые входы которых поданы высокие потенциалы с триггеров 4,„-4,„первой строки матрицы 3. Если все триггеры

4,„ -4 „ первой строки матрицы находятся в единичном состоянии, то сигналы с выходов элементов И 5„ -5,„через элементы И 6 „, -б„„и элементы ИЛИ 9„9„ переводят триггеры 16„-16 „, в единичное. состояние..Высокие потенциалы с выходов триггеров 16 -16

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

Если не все триггеры 4 „, -4 „ первой строки матрицы 3, а только 1.-й триггер 4,, находится в единичном состоянии, то сигнал с соответствующего элемента И 5„. через элементы

И 6„, и ИЛИ 9; переводит триггер 16,. в едйничное состояние. Сигнал с выхода триггера 16, через элемент И 15 <

5 159 переводит регистрирующий триггер 14 .

6 в единичное состояние, через элемент

НЕ ll; запрещает прохождение сигналов через элементы И 6„ -6 „;-ro столб" ца и через элементы ИЛИ 10 поступает на первые входы элементов И 5

5;„ -й строки. Если j-й триггер 4 †. й: строки (iWj) матрицы 3 находится в единичном состоянии, то сигнал. с него через элементы И 5; q И 6;1. и ИЛИ 91 переводит j-й триггер 16 . в единичное состояние. Сигнал с выхода триггера 16 через элемент

И 15;; переводит регистрирующий триггер 14 . в единичное состояние, 11 через элемент НЕ ll запрещает прохождение сигналов через элементы

И 6 -6 -го столбца матрицы 3 и че11 П рез элемент ИЛИ 10 поступает на пер3 вые входы элементов И 5 . -5 . j-й

)1 строки.

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

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

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

4558 6 поступает в счетчик 7. Информация о количестве поступивших импульсов из счетчика 7 поступает в дешифратор 8. В результате дешифровання на

k-м выходе дешифратора 8 появляется высокий потенциал, который поступает через элемент ИЛИ 10 . на элементы И 5, -5 j-й строк6. Дальше схема работает аналогично рассмотренному случаю на первом такте. В результате работы схемы на k-м такте все или часть регистрирующих триггеров 14,-14> k-й строки матрицы переходят в едйничное состояние.

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

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

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

1594558

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

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

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

Заказ 2831 Тираж 566 Подписное

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

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

Производственно-издательский комбинат "Патент", r.Óæãîðîä, ул. Гагарина,101