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

Устройство относится к области вычислительной техники и может быть использовано для определения характе ристик связности вероятностного графа. Известное устройство для определе ния связности l , содержащее триггеры, элементы ИЛИ и элемент И, обладает низким быстродействием. Наиболее близким по технической сущности к изобретению является устройство для исследования связности вероятностного графа 2, содержащее матрицу триггеров, элементы ИЛИ по числу столбцов матрицы триггеров, элемент И, входы которого соединены с выходами элементов ИЛИ, выход элемента И соединен с выходом устройства, элементы И по числу триггеров, кроме триггеров первой строки матрицы, выходы триггеров столбцов матрицы через соответствующие элементы И соединены с входами соответствуквди элементов ИЛИ, входы сброса всех триггеров матрицы объединены и соеди иены с установочной шиной устройства, установочные входы всех триггеров соединены с входами устройства. Однако это устройство также отличается недостаточным быстродействием Целью изобретения является повышение быстродействия устройства. Это достигается тем, что в предлагаемом устройстве выходы триггеров первой строки матрицы соединены с входами соответствующих элементов ИЛИ выходы которых соединены со вторыми входами элементов И соответствующих строк. Блок-схема описываемого устройства приведена на чертеже. Устройство содержит матрицу триггеров 1, элементы И 2 по числу триггеров, элементы ИЛИ 3, элемент И 4, установочную шину 5. Устройство работает следующим образом. В такте t по шине 5 происходит установка в нулевое состояние всех триггеров 1 матрицы. В такте tg на установочные входы триггеров 1 матрицы подаются результаты розыгрыша состояния исследуемого графа. Результаты розыгрыша выдаются в виде матрицы смежности вершин. При этом элементы . и элементы первого столбца не записываются, а остальные элементы матрицы смежности записьлваются в соответствующие триггеры 1, т.е. элемент (1 j), (j О

аписывается в триггер Нi -и строи j -го столбца.

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

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

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

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

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

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

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

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

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

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

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

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

1 Авторское свидетельство СССР 468244, кл. G06 F 15/20, 1972.

2. Авторское свидетельство СССР № 271906, кл. G06 Q 7/48, 1968.