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

 

ОП ИСАНИЕ

ИЗОБРЕТЕН ИЯ

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

Сеюв Соаетсииа

Сюцмапистичесиих

Республик и 896630 (61) Дополнительное к авт. свид-ву N 637822 (22) Заявлено 24.04.80 (21) 2916984/18-24 (51)M. Кд.

G 06 F 15/20 с присоединением заявки М

Рюударатаекай кеиктат

CCCP

ai ааааа каааратений и атхрытка (23 ) П р нор и тетвЂ

Опубликовано 07.01 82 Бюллетень М 1

Дата опубликования описания 07.01.82 (53) УДК 681.333 (088.8) ; .с .",«

«., :f тт" -«-..«7 IФ;, f « «

" .-: ь, в "«г

« t (72) Автор изобретения

В. Н. Кустов (71) Заявитель (54) УСТРОЙСТВО ДЛЯ ИССЛЕДОВАНИЯ СВЯЗНОСТИ

ВЕРОЯТНОСТНОГО ГРАФА

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

По основному авт. св. Н 637822 известно

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

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

20 матрицы объединены и соединены с установочной шиной устройства, установочные входы всех триггеров соединены со входами устрой ствя ()).

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

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

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

896630 4 гой вход которого соединен с выходом первого триггера 1 первой строки. Если данный триггер 1 находится в единичном состоянии, то сигнал с выхода элемента И 7 в виде одиночного импульса поступает на счетный вход счетчика 6. С выхода первого элемента 8 задержки сигнал поступает также на вход следующего элемента 8 задержки и далее аналогичным образом опрашивается содержимое всех следующих триггеров 1 матрицы.

В результате полного цикла опроса содержимое счетчика 6 соответствует количеству единиц в матрице смежности (количеству ребер связного графа).

Таким образом, сигнал на выходе счетчика

6 представляет некоторый код, характеризующий связность графа.

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

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

Устройство содержит триггеры 1, элементы

И 2, элементы ИЛИ 3, элементы И 4, установочную шину 5, счетчик 6, дополнительные элементы И 7, элементы 8 задержки и формирователь 9 импульсов.

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

В такте tq по шине 5 происходит установ«а в нулевое состояние всех триггеров 1 мат рицы и счетчика 6.

В такте t2 на установочные входы триггеров 1 матрицы передаются двоичные сигналы, определяемые значениями соответствующих элементов матрицы смежности исследуемого .графа.. Одноврвменно в такте t> определяется наличие связности первой вершины со всеми остальными. Если первая вершина связана хотя бы с одной вершиной, то соответствующий триггер 1 первой строки находится в единичном состоянии. В противном случае все триггеры 1 находятся в нулевом положении и граф состоит из нескольких несвязанных частей.

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

3, сигнал с которого поступает на элемент

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

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

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

В случае, если граф связан, сигнал с выхода элемента И 4 в виде ступеньки поступает на вход формирователя 9 импульса, с выхода кЬторого сигнал в виде одиночного импульса через первый элемент 8 задержки, поступает на вход первого элемента И 7, друФормула изобретения

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

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

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

1. Авторское свидетельство СССР N 637822, кл. 6 06 F 15/20, 1978 (прототип).

896630

Составитель А Яинков

Техред А.Савка

Корректор Г Решетняк

Редактор Л. Пчелинская:

Подписное

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

Заказ 11707/38 Тираж 731

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

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