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

(54) УСТРОЙСТВО ДЛЯ ИССЛЕДОВАНИЯ СВЯЗНОСТИ ВЕЮЯТНОСТНОГО ГРАФА

1

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

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

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

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

Поставленная цель достигается тем, что в устройство введены счетчик, формирователь импульса, дополнительные элементы И к поtoследовательная цепочка из элементов задержки, выход каждого элемента задержки цепочки соединен с первым входом соответствующего дополнительного элемента И, второй вход которого подключен к выходу соответ15ствующего триггера матрицы, выходы всех дополнительных элементов И соединены со счетным входом счетчика, установочный вход которого подключен к установочной щине устройства, вход формирователя импуль30сов соединен с выходом устройства, а его выход - со входом первого элемента задержки цепочки, выход счетчика является дополнительным выходом устройства. На чертеже приведена блок-схема устройства. Устройство содержит триггеры 1, элементы И 2, элементы ИЛИ 3, элементы И 4, установоч11ую шнну 5, счетчик 6, дополнительные элементы И 7, элементы 8 задержки и формирователь 9 импульсов. Предлагаемое устройство работает следующим образом. В такте ti по шине 5 происходит установка в нулевое состояние всех триггеров 1 маТ рицы и счетчика 6. В такте t2 на установочные входы триггеров 1 матрицы передаются двоичные сигналы, определяемые значениями соответствующих элементов матрицы смежности исследуемого .графа. Одноврвменно в такте tj определяется наличие связности первой вершины со всеми остальными. Если первая вершина связана хотя бы с одной вершиной, то соответствующий триггер 1 первой строки находится единичном состоянии. В противном случае все триггерь 1 находятся в нулевом пол жении и граф состоит из нескольких несвязанных частей. Если все триггеры 1 первой строки находятся в единичном состоянии, то на выходах всех элементов ИЛИ 3 имеется сигнал, сра& тывает элемент И 4 и на первом выходе уст ройства появляется сигнал, свидетельствуюищй о том, что исследуемый граф является связным. Если не все тригегры 1 первой строки, а только i-ый триггер 1 находится в единичном состоянии, тогда Сигнал с его выхода поступает на соответствующий элемент ШШ 3, сигнал с которого поступаем на элемент И 4 и на входы элементов И 2 i-ой строки. Если j-ый триггер 1 i-ой строки находится в единичном состоянии, то сигнал с него поciynaet через соответствующий элемент И 2 на вход j -го элемента ИЛИ 3, через который сигнал поступает на элемент И 4 и на входы элементов И 2 j-ой строки. Если граф является связным, то в резуль тате таких переключений на всех входах элемента И 4 и на первом выходе устройства имеется сигнал. В противном случае на всех входах хотя бы одного элемента ИЛИ 3 отсутствуют сигналы и элемент И 4 не срабаты вает: граф не является связным. В случае, если граф связан, сигнал с выхо да элемента И 4 в виде ступеньки поступает на вход формирователя 9 импульса, с выхода кЬторого сигнал в виде одиночного импульса через первый элемент 8 задержки, поступает на вход первого элемента И 7, дру4гой вход которого соединен с выходом перого триггера 1 первой строки. Если данный триггер 1 находится в единичном состоянии, то сигнал с выхода элемента И 7 в виде одиночного импульса поступает на счетный вход счетчика 6. С выхода первого элемента 8 задержки сигнал поступает также на вход следующего элемента 8 задержки и далее аналогичным образом опрашивается содержимое всех следующих триггеров 1 матрицы. В результате полного цикла опроса содержимое счетчика 6 соответствует количеству единиц в матрице смежности (количеству ребер связного графа). Таким образом, сигнал на выходе счетчика 6 представляет некоторый код, характеризующий связность графа. Введенные в устройство счетчик, повторители, элементы И, схема дифференцирования и их функциональные связи позволяют получать количественную оценку связности исследуемого графа. Это, в свою очередь, дает возможность сравнивать графы различных вариантов структур по показателю связности с целью выбора графов с наименьшей связностью, применение которых при осуществлении параллельных вычислений является предпочтительным. Формула изобретения Устройство для исследования связности вероятностного графа по авт. св. № 637822, отличающееся тем, что, с целью расишрения функциональных возможностей за счет возможности получения количественной оценки связности графа, в него введены счетчик, формирователь импульса, дополнительные элементы И и цепочка из последовательно соединенных элементов задержки, выход каждого элемента задержки цепочки соединен с первым входом соответствующего дополнительного элемента И, второй вход которого подключен к выходу соответствующего триггера матрицы, выходы всех дополнителып 1х элементов И соединены со счетным входом счетчика, установочный вход которого подключен к установочной шине устройства, вход формирователя импульсов соединен с выходом устройства, а его выход - со входом первого элемента задержки цепочки, выход счетчика является дополнительным выходом устройства. Источникн информации, принятые во внимание при экспертизе 1. Авторское свидетельство СССР № 637822, кл. G 06 F 15/20, 1978 (прототип).