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

 

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

СОЮЗ СОВЕТСКИХ

СОЦИАЛИСТИЧЕСКИХ

РЕСПУБЛИК

„„4 G 06 F 15/20

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

К А BTOPCHOMV СВИДЕТЕЛЬСТВУ с ,i

ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССР

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ (2 1) 384 1 662/24-24 (22) 09.01.85 (46) 07.09.86. Бюл. № 33 (72) А. И. Багрич и В. Н. Кустов (53) 681.333 (088.8) (56) Авторское свидетельство СССР № 637822, кл. G 06 F 15/20, 1978.

Авторское свидетельство СССР № 896630, кл. G 06 F 15/20, 1982. (54) УСТРОЙСТВО ДЛЯ ИССЛЕДОВАНИЯ СВЯЗНОСТИ ВЕРОЯТНОСТНОГО

ГРАФА (57) Изобретение относится к цифровой вычислительной технике и может быть исполь„„Я0„„1256039 д1 зовано для количественной оценки связности графов информационно-логических структур

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

ИЛИ, два регистра, счетчик, формирователь импульсов и элемент И. 1 ил.

1256039 вид

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

ЭВМ.

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

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

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

И 2 и 7 и элемента 8 задержки. Кроме того, на чертеже обозначены входы 15 задания номера начальной вершины устройства, выходы 6 идентификации вершин устройства, выход 17 индикации связности графа устройства, выход 18 фиксации числа дуг устройства.

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

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

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

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

0 а г а1г . aI аг

0 77зг 0 ... изу

1О и„икз... а !

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

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

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

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

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

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

И4, íà j-й разряд регистра 12 и на входы элементов И2 j-й строки.

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

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

Появление единичного сигнала на выходе

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

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

B виде единичного импульса поступает на

1256039

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

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

В случае, если граф является связным, одиночные импульсы с элементов И 7 последовательно поступают на счетчик 6, который подсчитывает число триггеров 1 матрицы, находящихся в единичном состоянии (т. е. число дуг исследуемого графа). Код со счетчиков 6 поступает на вход 18 устройства, позволяя оценить связность графа не только качественно, но и количественно в абсолютном значении.

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

i ãî элемента ИЛИ первой группы (где

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

Зо

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

1256039

Составитель Т. Сапунова

Редактор С. Патрушева Техред И. Верес Корректор Л. Патай

Заказ 4825/49 Тираж 671 Подписное

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

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

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