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

 

637822 записывается в триггер 1 -й стро ки ) -го столбца.

Одновременно в такте t определяется наличие связности первой вершины со всеми остальными. Если первая вершина связана хотя бы с одной вершиной, то какой-либо из триггеров

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

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

Если не все. триггеры 1 первой строки находятся в единичном состоянии, то пусть -й триггер 1 первой строки находится s единичном состоянии, тогда сигнал с его выхода поступает на соответствующий элемент ИЛИ

3, сигнал с которого поступает на элемент И 4 и на входы элементов И

2 i -й стройки. Если -й триггер 1

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

И 4 и на входы элементов И 2 -й строки.

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

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

Таким образом, связность графа

6 определяется за два такта работы, что значительно быстрее, чем в прототипе.

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

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

Источники информации, принятые во внимание при экспертизе:

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

М 468244, кл. 606 F 15/20, 1972..

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

Р 271906, кл. GO6 g 7/48, 1968.

6 37822

Составитель T.Арешев

Техред Н.Бабурка Корректор Е. Папп

Редактор С. Хейфиц

Филиал ППП Патент, г. Ужгород, ул. Проектная, 4

Заказ 7108/40 Тираж .784 Подписное

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

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