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

 

Союз Советских

Социалистических

Республик

О П (11) 468244

ИЗОБРЕТЕНИЯ (61) Дополнительное к авт. свид-ву М(51) N. Кл. (22) Заявлено 17.11.72-(21) 1847047/18-24 с присоединением заявки е-Q 06 f 15/20

Гасударственный квинтет

Саветв Министров СССР аа делам изааретений и аткрытий (231Приоритет(53) УДК 681.325, (088. 8) Опубликовано 25.04.75. Бюллетень № 15

Дата опубликования описания 11 О5 75 (72) Лвтор изобретения

В. В. Епихин (71) Заявитель (54) УСТРОЙСТВО ДЛЯ ИССЛЕДОВАНИЯ СВЯЗНОСТИ ВЕРОЯТНОСТНОГО

ГРАФА

Изобретение относится к области вычислительной техники.

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

Предлагаемое устройство отличается от известных тем, что в нем потенциальные единичные выходы триггеров первой строки 20 матрицы триггеров через соответствующие последовательно включенные ключи и элементы задержки соединены с нулевыми входами.

2 триггеров одноименной строки матрицы триггеров, а единичные входы триггеров первой 25

2 строки каждого столбца матрицы триггеров

;через соответствующие элементы ИЛИ подкl лючены к импульсным единичным выходам остальных триггеров одноименных столбцов матрицы триггеров.

На чертеже приведена блок-схема предлагаемого устройства.

Устройство содержит элемент И 1, триг геры 2 -2ыы, элементы ИЛИ 3 -3 1, элементы задержки 4 -4р1, ключи 5 -5Р1

2 Р1 : сбросовый вход 6, вход 7 проверочных импульсов, установочные входы 8 — 8 и

12 выход 9.

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

Работа устройства происходит по тактам, Т, Т . В такте Т происходит сброс

1 2 3 1 всех триггеров 2. ° в нулевое положение

1) 1. импульсом по сбросовому входу 6. В такте на все установочные входы 8 сех триггеров 2 поступают результаты розыгрьпла состояний ребер графа. Наличие ребра в данном розыгрыше соответствует импульсу на установочном входе 8 — 8 или

12 1N

3 ь 4

2 . Орукур 4уд ну ед »

822 NN Р Р "-12 NN,дах триггеров 8 - 8 появляются в.

22 йй графа представляется в виде матрицы смеж

:, момент перебрасывании этих триггеров из

) единичного. положения в нулевое, Поэтому

) записывают- 5 .по пеРвомУ : ИМпульсу. постУпившемУ по

11:, входу проверочных импульсов 7, произойдет

- 2 по установочным ; ся в тр -ры 12 1И " У,, . - - -:перезапись состояни@соответствуюших строк входам 8 - 8, причем элемент а -,,через элемейты HJIH 3 - 3 в триггеры

12 1N 1Ф 2 Ц

; записывается по установочному входу 8 ° 2 - 2,, первой строки. Фактически про-, 1ь 16 12 1И !

Элементы остальных строк (за искшочением исходит операпия логического сложения эле элементов первого столбца а. ) aaIIMobraa- ментов первой строки с элементами тех

Ll

8 обра м, стРок, котоРые соответствУют единичным ются в триггеры 8 - таким о Разом, 22 NN, элементам первой строки. В результате что элементы j ()й строки (j = 2, 3,..".И )у этого число триггеров 2 — 2 >rrepe6po12 18 записываются в триггеры 2 ° - 2 приgN .шенных в единичное положение, . либо возчем элемент этой строки а. записывается растет (если имеются вершины, расстояние ,)к

В р зультате до которых оТ пеРвой PaaHo:двум), либо ос по установочному .входу 8; - РезУльтате тается прежним (если нервам вершина свяэтого в такте Т в тригrepax 2 2 ea, ® зана только с теми веуцднами, расстояние .

2 12 КМ до которых равно единине). По второму писывается матрица смежностей вершин pa= импульсу, оетупирйему по входу провероч-, зыгранного состояния, вероятностного графа,, ных жал&,"ею"Ф, опять произойдет логиче-: за исключением элементов первого столбца ское сложение элементов первой строки матматрицы. Если первая строка этой матри-; 5. рицы с элементами тех строк, которые соцы содержит только единицы (граф связен), 2 2 первой сТроКН ответствуют единичным элементам обновлен-, то все триггеры 2 ной первой строки. Соответственно число матрицы триггеров находятся в единичном триггеров 2 - 2, переброшенных в

12 1N положении, на всех входах элемента И 1,, единичное положение, либо возрастет (если имеются сигналы, и на выходе 9 появляет- ЗО имеются вершины расстояние до которых

Ф сЯ сигнал, котоРый говоРит о свЯзности,, от первой ра но трем) либо тан я преж гРафа. В эчом слУчае дальнейшаЯ Работа ;ням (если таких вершин не имеется). Если, пРиостанавливается (такт Т пропускается), граф связен, то после очередного импульса,: и УстРойство переходит к, РозыгРышУ но« . поступившего по входу проверочных импуль-, вого состояния (работа по тактам Т . Т . сов 7, произойдет переброс последних триг- 2 в единичное положение, и Т ). Если хотя бы один элемент первой, Роа 212

t, сработает элемент И 1 и на выходе 9 по-,: строки матриш,1 сме тн вершин рюен .. р нулю, то не на всех входах элемента: имев одах элемента И:1 име-. "явится. сигнал. Иальнейшее поступление им ются сигналы и на выходе 9 сигнал отсутст- .40; пульсов по входу проверочных импульсов 7 вует. В этом случае в такте Т по входу про-.,! прекрашается и устройство переходит .к.но3 вому циклу работы. Если после (g-2)-го,верочных импульсов 7 поступает серия из, импульса (максимально во (возможное расстоя(f4 — 2) импульсов. Первый импульс из ние между вершинам вершинами ровно И - 1), посэтой cepIIH rrooTyIIae T epee ключи и 45 тупившего по вх по входу 7 проверочных имэлементы задержки 4 на считывание триг, пульсов, на выходе а в ходе 9 отсутствует сигнал, геров 8 — 8, соответствующих тем

22 NN то граф разбит на несколько ч ф 6 н сколько частей строкам матрицы смежности, с которыми первая вершина по результатам розыгрыша;

1 !

Предмет изобретения связана непосредственно ребром (т, е. Рас-. 5О стояние до которых От первой вершины рав.но единице), т, к. потенциальные единич» l Устройство для исследования связности ные выходы трипгеров 2 - 2 ° нах - вероятностного графа, содержашее матрицу

12 1Ц дящихся в единичном положении, открыва« триггеров, нулевые входы которых подклюют соответствуюшие им ключи 5 - (° чены ко входу сброса триггеров устройст-, :55 ф692ф4

6 ва, а единичные входы к его установоч) ным входам, элемент И, включенный между

; потенциальными единичными выходами триь-

;геров первой строки матрицы триггеров ( выходом устройства, элементы задержки, l

1 элементы ИЛИ и ключи первые входы кот

, рых подключены ко входу проверочных им

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

1задержки соединены с нулевыми входами, и 1.триггеров ойаовменной строки матрицы . триггеров, а единичйые ЫхОды триггеров„. ервой строки каждого столбца матрицы триггеров через состветствукидие элемент

; яЛИ полклюййнйк имврКьеным елнврЖйм ц 1ч выходам остальных триггеров одноименных

"зйтолйлов матрилы триггеров.

Соста итеаь 1 .Сорокин

Редан ор О Стеннна 1ехред H.XBHeeBB Корректор

Л,Орлова

Изд, № 6/О

Заказ 1 1

Тираж 6т У

Подписное

Предприятие «Патент», Москва, Г-59, Бережковская иаб., 24

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

Москва, 113035, Раушская иаб., 4