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

(54) УСТРОЙСТВО ДЛЯ ИССЛЕДОВАНИЯ ГРАФА СВЯЗНОСТИ ВЕРОЯТНОСТНОГО Saa N NM графа представляетсяв виде матрицы смвж« ности вершин ( N - число вершин графа). Элементы первой строки этой матрицы (за исключением элемента а--) записываютэлемента а., ) .- 21-., по установочным ся в триггеры 2:12jLi4,,. . .г входам 8.2- SIN причем элемент а i записывается по установочному входу i Элементы остальных строк (за искяючением I элементов первого столбца а. ) записьша .. ются в триггеры 8„„- 8 таким образом, ii PIN ЧТО элементы J-ОИ строки ( j 2, 3,..,W записьшаются в триггеры 2- - 2 причем элемент этой строки а. записывается J по установочному .входу 8 . - В результате этого в такте Т триггерах писывается матрица смежностей вершин разыгранного состоянияу вероятностного графа за исключением элементов первого столбца матрицы. Если первая строка этой матри цы содержит только единицы (граф связей) то все триггеры 2 2 первой строки 1 IN матрицы триггеров находятся в единичном положении, на всех входах элемента И 1 имеются сигналы, и на выходе 9 появляется сигнал, который говорит о связности графа. В этом случае дальнейшая работа приостанавливается (такт Т пропускается) и устройство переходит к, розыгрышу нового состояния (работа по тактам Т Т и т ). Если хотя бы один элемент первой о строки матрицы смежности вершин равен нулю, то не на всех входах элемента Й;1 име- ются сигналы и на выходе 9 сигнал отсутствует. В этом случае в такте Т по входу проварочных импульсов 7 поступает серия из ( N - 2) импульсов. Первый импульс из этой серии поступает через ключи 5 и элементы задержки 4 на считывание триггеров 822 соответствующих тем

строкам матрицы смежности, с которыми первая вершина по результатам розыгрыша : связана непосредственно ребром (т. е. рас-: стояние до которых от первой вершины равгно единице), т. к. потенциальные единичт, ные выходы трипгеров 2 „- , находящихся в единичном положении, открыва5,- 5. . :55

ют соответствующие им ключи

NПредмет изобретения

Устройство для исследования связности вероятностного графа, содержащее матрицу триггеров, нулевые входы которых подключены ко входу сброса триггеров устройст- , Импульсы на импульсных единичных БЫХО ;дах триггеров 8оо ®мы появляются в NN момент перебрасывания этих триггеров иа j единичного по/южения в нулевое. Поэтому i ino первому 1 импульсу, поступившему по i входу проверочных импульсов 7, произойдет :|перезапись состояний соответствующих строк :Чёрез элементы ИЛИ 3 - 3 в триггеры t..„.; . , 2 . п1 ,.,,.... 2 ,первой строки. Фактически про: исходит операция логического сложения элементов первой строки с элементами тех ; строк, которые соответствуют единичным элементам первой строки. В результате этого число триггеров 2 - 2 переброшенных в единичное положение, либо воз-; растет (если имеются вершины, расстояние : до которых от первой равно гдвум), либо ос« тается прежним (если перфаа вершина связана только с теми ве р1 рдаами, расстояние i до которых равно .е). По второму импульсу,;||оету Ш§Й1ёму по входу провероч--, ных Hivaij j jiQB, опять произойдет логиче- ское сложение элементов первой строки матрицы с элементами тех строк, которые соответствуют единичным элементам обновлен-, ной первой строки. Соответственно число / триггеров 2.,- 2 , переброшенных в ; i,i JLN / ; ; единичное положение, либо возрастет (если . имеются BepofflHbij расстояние до которых , от первой равно трем), либо останется преж; ним (если таких вершин не имеется). Если , граф связен, то после очередного импульса, поступившего по входу проверочных импуль-: ; СОВ 7, произойдет переброс последних триг; геров 2 -, м единичное положение, ; сработает элемент И 1 и на выходе 9 по явится сигнал. Дальнейшее поступление им- { пульсов по входу проверочных импульсов 7 I прекращается и устройство п вехсшит л. новому циклу работы. Если после (К-2)-го ,, импульса (максимально возможное расстояние между вершинами ровно N - 1), поступившего по входу 7 проверочных импульсов, на выходе 9 отсутствует сигнал, то граф разбит на несколько частей. ва, а единичные входы к его установоч«у ным входам, элемент И, включен{а 1й мензд потенциальными единичными выходами тршч геров первой стро триггеров и / выходом устройства, элементы задержки, 1 элементы ИЛИ и ключи первые входы кото-) рых подключены KOi, входу проверочных им-f пульсов устройства, отличающеес я тем, что с целью повышения быстродействия, в нем потенциальные единичные выjQходы триггере первой стро1Ш матрицы TpjfrrepOB через соответствующие поспедо-, вательно включенные ключи и элементы | задержки соединены с нулевыми входами ;.триггеров.однадменной строки матрицы-Триггеров, а единиЧЙью кййы Tpiirrepoa: первой строки каждого столбца матрицы i-IR5 l®P ,ТЯТ53 М ®, элемент |р|ЛИподЙ1 ёны кшйнуЖсным. еддачШм Kвыходам остальных триггеров одноименных) ;У толбшв матрихш триггеров.