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

f

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

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

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

Устройство содержит триггеры 1, элементы И 2, элементы ИЛИ 3, элементы И 4, вход 5 сброса устройства, счетчик 6, элементы И 7, элементы 8 задержки, формирователь 9 импульсов, элементы И ЛИ 10, регистры 1 и 12. Каждая ячейка 13 матричной модели 14 исследуемого графа образована совокупностью триггера 1, элементов И 2 и 7 и элемента 8 задержки. Кроме того, на чертеже обозначены входы 15 задания номера начальной вершины устройства, выходы 16 идентификации вершин устройства, выход 17 индикации связности графа устройства, выход 18 фиксации числа дуг устройкгтва.

Устройство для исследования связности вероятного графа работает следуюш,им образом.

Перед началом работы на вход сброса устройства подается сигнал, устанавливающий в нулевое состояние все триггеры 1 элементов 13 матричной модели исследуемого графа 14, счетчик 6 и регистры 11 и 12.

Затем на устаповочные входы устройства поступают двоичные сигналы в соответствии с матрицей смежности исследуемого графа.

Матрица смежности имеет следующий

вид

«It,

«2ji

азп

. . а

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

256039

2

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

5В случае, когда начальная верщина подграфа связана хотя бы с одной вершиной, то тогда соответствующий триггер 1 в строке матрицы матричной модели 14, определяемой номером начальной вершины, находится в

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

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

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

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

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

35 Если производится исследование связности всего графа в целом, начиная с первой вершины, и граф является связным, то во всех разрядах регистра 2 установлены единицы, на всех входах элемента И4 и на выходе 17 индикации связности графа и.меется сигнал.

Появление единичного сигнала на выходе 17 устройства (выход элемента И 4) указывает на то, что в каждом из столбцов матрицы имеется хотя бы один триггер, находящийся в единичном состоянии. Это сви40

S,

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

50 Данный сигнал с выхода элемента И 4 в виде ступеньки поступает на вход формирователя 9 импульсов, с выхода которого через первый элемент 8 задержки сигнал в виде единичного импульса поступает на вход первого элемента И 7, другой вход которого 55 соединен с выходом первого триггера 1. Если данный триггер находится в единичном состоянии, то сигнал с выхода элемента И 7 в виде единичного импульса поступает на

счетный вход счетчика 6, с выхода первого элемента 8 задержки сигнал поступает на вход элемента 8 задержки следующего элемента 13 матрицы матричной модели 14 топологии исследуемого графа. Далее аналогичным образом опрашивается содержимое всех последующих элементов 13 магричной модели 14.

В случае, если граф является связным,

ки матрицы подключен к выходу формирователя импульсов, выход триггера каждой ячейки матрицы подключен к первому входу первого элемента И своей ячейки матрицы, выход i-ro элемента И каждого j-ro столбца матрицы подключен к i-му входу j-ro элемента ИЛИ первой группы (i, j I, 2, ..., N), выход триггера каждой ячейки каждой строки матрицы, кроме первой, подключен к первому входу второго элемента И той же ячейодиночные импульсы с элементов И 7 по- д матрицы, второй вход которого подклюследовательно поступают на счетчик 6, который подсчитывает число триггеров 1 матрицы, находящихся в единичном состоянии (т. е. число дуг исследуемого графа). Код со счетчиков 6 поступает на вход 18 устчен к второму выходу элемента задержки той же ячейки матричной модели исследуемого графа, выходы вторых элементов И каждой ячейки каждой строки матрицы, кроме первой, объединены и подключены к счетв абсолютном значении.

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

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

20

ройства, позволяя оценить связность графа 15 ному входу счетчика, вход сброса счетчика не только качественно, но и количественно и входы сбросов всех триггеров матрицы

объединены и являются входом сброса устройства, установочные входы всех триггеров являются установочными входами устройства, выход счетчика является выходом фиксации числа дуг, отличающееся тем, что, с целью расширения функциональных возможностей путем обеспечения проведения исследования связности графа, начиная с любой вершины, и определения номеров вер- матричную модель исследуемого графа, каж- 25 шин, связанных с данной вершиной, в него дая ячейка которой, кроме ячеек первой стро- введены первый и второй регистры, вторая ки, содержит первый и второй элементы И, группа элементов ИЛИ, в каждую ячейку триггер и элемент задержки, каждая ячейка первой строки матричной модели исследуе- первой строки матричной модели исследуе- мого графа введен второй элемент И, пер- мого графа содержит триггер, первый эле-вый вход которого подключен к выходу тригмент И и элемент задержки, причем i-й вход зо гера той же ячейки матрицы, а второй выходного элемента И подключен к выходу вход второго элемента И подключен к второ- i-ro элемента ИЛИ первой группы (где му входу элемента задержки той же ячейки i 1, 2 ..., N), выход выходного элемента И матрицы, выходы вторых элементов И всех подключен к входу формирователя импуль-ячеек первой строки матрицы объединены и

сов и является выходо.м индикации связное-подключены к установочному входу счетчика,

ти графа устройства в i-й строке матрицы 35 вторые входы первых элементов И и всех (где i 1, 3, 5, ...), вход каждого элемента ячеек первой строки матрицы объединены и задержки ячейки матрицы подключен к первому выходу элемента задержки ячейки матрицы предыдущего столбца этой строки, в j-й строке матрицы (где j 2, 4, 6, ...) вход каждого элемента задержки ячейки матрицы подключен к первому выходу элемента задержки ячейки матрицы последующего столбца этой строки матрицы, первый выход элемента задержки ячейки матрицы

каждой i-й строки последнего столбца мат- ., ной вершины исследуемого подграфа, второй рицы подключен к входу элемента задерж.-вход i-ro элемента ИЛИ второй группы объки ячейки (i-f 1)-и строки последнего столб- единен с входом i-ro разряда второго регистра и подключен к выходу i-ro элемента ИЛИ первой группы, выходы разрядов второго регистра являются выходами иден- элемента задержки ячейки матрицы (j -f 1)-й 50 тификации вершин устройства, входы сброса строки первого столбца матрицы, вход пер-первого и второго регистров объединены с

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

40

подключены к выходу первого разряда первого регистра, выход каждого т-го разряда которого (ш 2, 3, ..., N) подключен к первому входу гп-го элемента ИЛИ второй группы, выход которого подключен к вторым входам первых элементов И всех ячеек одноименной строки матричной модели исследуемого графа, входы первого регистра являются входами задания номера начальца матрицы, первый выход элемента задержки ячейки матрицы каждой j-й строки первого столбца матрицы подключен к входу

ки матрицы подключен к выходу формирователя импульсов, выход триггера каждой ячейки матрицы подключен к первому входу первого элемента И своей ячейки матрицы, выход i-ro элемента И каждого j-ro столбца матрицы подключен к i-му входу j-ro элемента ИЛИ первой группы (i, j I, 2, ..., N), выход триггера каждой ячейки каждой строки матрицы, кроме первой, подключен к первому входу второго элемента И той же ячейчен к второму выходу элемента задержки той же ячейки матричной модели исследуемого графа, выходы вторых элементов И каждой ячейки каждой строки матрицы, кроме первой, объединены и подключены к счетвторые входы первых элементов И и всех ячеек первой строки матрицы объединены и

ной вершины исследуемого подграфа, второй вход i-ro элемента ИЛИ второй группы объ

подключены к выходу первого разряда первого регистра, выход каждого т-го разряда которого (ш 2, 3, ..., N) подключен к первому входу гп-го элемента ИЛИ второй группы, выход которого подключен к вторым входам первых элементов И всех ячеек одноименной строки матричной модели исследуемого графа, входы первого регистра являются входами задания номера началь-Ю

Изобретение относится к цифровой вычислительной технике и может быть использовано для количественной оценки связности графов информационно-логических структур ЭВМ. Целью изобретения является расширение функциональных возможностей устройства за счет обеспечения проведения исследования графа, начиная с любой его вершины, и определения номеров вершин, связанных с данной вершиной. Устройство содержит матричную модель топологии исследуемого графа, каждый элемент матрицы которой состоит из триггера, двух элементов И и элемента задержки. Кроме того, устройство содержит две группы элементов ИЛИ, два регистра, счетчик, формирователь импульсов и элемент И. 1 ил. N5 СД о: о оо ;&