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

 

Изобретение относится к вычислительной технике, и может быть использовано для решения задач на вероятностных графах и позволяет определять веса подграфов, на которые распадается вероятностный граф в каждом розыгрыше вершин и ребер. Уст°16 JS IS (Л со О) 4: С5 о

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

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

РЕСПУБЛИК

А1 (19) (И) (51)4 G 06 Г 15 20

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

Н ABTOPCHOMV СВИДЕТЕЛЬСТВУ

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ (21) 4011322/24-24 (22) 13.01.86 (46) 30.09.87. Бюл. И - 36 (72) А.Г.Луценко и В. M.Áàëàêèðåâ (53) 681.333(088.8) (56) Авторское свидетельство СССР

Ф 1119023, кл. G 06 F 15/20, 1982.

Авторское свидетельство СССР

N - 656073, кл. G 06 F 15/36, 1976. (54) УСТРОЙСТВО ДЛЯ ИССЛЕДОВАНИЯ ВЕРОЯТНОСТНЫХ ГРАФОВ (57) Изобретение относится к вычислительной технике, и может быть использовано для решения задач на вероятностных графах и позволяет определять веса подграфов, на которые распадается вероятностный граф в каждом розыгрыше вершин и ребер. Уст134 ройство содержит вход 1 пуска, генератор 2 импульсов, выход 3 окончания испытания, вход 4 начальной установки, элемент И 5, группу элементов И 6„ пять групп ключей 7 — 11, две группы триггеров 12 и 13, входы

14 розыгрыша вершин, входы 15 розыгрыша ребер, информационные выходы

16.устройства, распределитель 17 -импульсов, вход 18 опроса устройства, две группы блоков 19 и 20 памяти, наборное поле 21, сумматор 22, два массива групп контактов 23 и 24 наборного поля. В исходном состоянии на триггерах 12 и 13 записаны результаты розыгрыша ребер и вершин соответственна. После пуска при помощи ключей 7 — 10 производится анализ вер1646 шин графа на связность. Веса связанных вершин и веса соответствующих ребер поступают с выхода блоков 19 и 20 памяти на вход сумматора 22, где формируется вес первого подграфа.

Одновременно производится сброс триггера 12 и 13, соответствующих ребрам и вершинам первого подграфа. По следующему импульсу генератора 2 производится обнуление сумматора 22 и при помощи ключей 7 производится выбор первой вершины второго подграфа.

Процесс повторяется до тех пор, пока не будут обнулены все триггеры 13.

В этом случае сигнал с выхода элемента И 5 формирует сигнал окончания испытания и останавливает генератор

2. 2 ил.

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

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

На фиг. 1 представлена функциональная схема предлагаемого устройст10 ва; на фиг. 2 — функциональные схемы ключей, подключаемых к наборному полк

Устройство содержит вход 1 пуска устройства, генератор 2 импульсов, 15 выход 3 признака окончания испытаний, вход 4 начальной установки,„ элемент

И 5, группу элементов И 6, пять групп ключей 7 — 11, две группы триггеров

12 и 13, Н входов 14 розыгрыша вершин, где Н вЂ” количество вершин в графе, Е входов 15 розыгрыша ребер, где Е— количество ребер в графе, Н информационных выходов 16 устройства, распределитель 17 импульсов, вход 18 оп25 роса устройства, две группы блоков

19 и 20 памяти, наборное поле 21 и сумматор 22 с фиксацией результата.

Наборное поле 21 содержит два массива контактов 23 и 24. Ключи 9 и 10 содержат обмотки 25 реле.

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

В первом такте импульс начальной установки поступает по входу 4 на первые R-входы триггеров 12 и 13 и устанавливает их в нулевое состояние.

Во втором такте на входы 14 и 15 поступают данные розыгрыша вершин и ребер, в результате чего открываются соответствующие ключи 9 и 10 (при этом все выходы ключа 9 соединяются с информационным входом, и между всеми выходами ключа образуется электрический контакт). Единичные сигналы с прямых выходов триггеров 11 открывают соответствующие ключи 8. В результате этого образуется электрический контакт между всеми вершинами и ребрами, присутствующими в розыгрыше.

Если в данном розыгрыше не выпало ни одной вершины, то единичные потенциалы с инверсных выходов триггеров 11 поступают на все входы элемента И 5, который выдает импульс на выход. При отсутствии сигнала на выходе 3 в третьем такте на вход 11 устройства поступает сигнал, запускающий генератор 2, первый импульс которого своим передним фронтом обнуляет сумматор 22, а также проходит .через первый открытый ключ 8 и соответствующий ключ 9 на контакты 23 и 24 первого и второго массивов контактов наборного поля, соответствующие связанным меж10

55 з 13 ду собой ребрам и вершинам в первом подграфе. При этом импульс проходит через соответствующие сработавшие ключи 9 и 10. При появлении импульса на контактах одной из групп контактов 23 он попадает на второй R-вход соответствующего триггера 11 и сбра.сывает его в ноль, триггер 12, соответствующий одному из ребер, присутствующих в данном розыгрыше, сбрасывается единичным сигналом с выхода соответствующего элемента И 6 лишь в том. случае, если в розыгрыше присутствуют обе вершины, связанные данным ребром, только в этом случае единичные сигналы поступают на оба входа элемента И 6 с соответствующей пары контактов 23.

При переходе триггеров 11 и 12 в нулевое состояние единичные сигналы с их инверсных выходов поступают на входы считывания соответствующих блоков 19 и 20, которые выдают веса связанных в первом подграфе вершин и ребер на входы сумматора 22. Последний суммирует вес вершин и ребер подграфа и выдает вес подграфа на информационные входы ключей 11.

В четвертом такте по входу 18 опроса на тактовый вход распределителя

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

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

Далее устройство работает аналогично, только вес второго подграфа выдается на второй выход 16 устройства и т.д.

После прохождения некоторого количества импульсов с выхода генератора 2 уже не останется вершин, для которых соответствующие триггеры 11 находятся в состоянии "1", единичные сигналы с инверсных выходов триггеров 11 проходят через элементы И 6 на. все входы элемента И 5, который выдает на выход 3 сигнал окончания данного испытания. Этот же сигнал обнуляет распределитель 17, который переходит в исходное состояние и останавливает генератор 2. Число подграфов, на ко-.

41646

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

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

Устройство для исследования вероятностных графов, содержащее элемент

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

"1" k --ro триггера первой группы (k = 1,... Н, где Н вЂ” количество вершин в графе) является К-м входом розыгрыша вершин устройства, прямой выход k -го триггера первой группы подключен к управляющим входам К -х ключей второй и третьей групп, инверсный выход К-го триггера первой группы (К+Н) подключен к управляющему входу k -го ключа первой группы, выход М-ro ключа первой группы (М =, 1,..., Н вЂ” 2) подключен к информационному входу. (М+1) ключей первой и второй групп, выход (Н-1)-го ключа первой группы подключен к информационному входу Н -ro ключа второй группы, выход k -го ключа третьей группы подключен к контактам К -й группы первого массива контактов наборного поля, вход установки в "1" р-го триггера второй группы (р = 1,..., E, где

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

Составитель А.Мип ин

Редактор М.Дылын Техред М,яндык Корректор Л. Патай

Заказ 4438/53 Тираж 672 Подписное

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

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

Производственно-полиграфическое предприятие, r. Ужгород, ул. Проектная, 4

5 13 группы блоков памяти, пятая группа ключей и группа элементов И, причем инверсный выход К-го триггера первой группы подключен к k -му входу элемента И и к входу признака чтения

k ãî блока памяти первой группы, выход которого подключен к входу К-ro слагаемого сумматора с фиксацией результата, инверсный выход Р -го триггера второй группы подключен к dxopy чтения р -го блока памяти второй группы, выход которого подключен к входу (н+ р) — ro слагаемого сумматора с фиксацией результата, выход которого подключен к информационным входам всех ключей пятой группы, вход опроса устройства подключен к тактовому входу распределителя импульсов, 4164б 6

1-й выход которого подключен к управляющему входу k-ro ключа пятой группы, выход которого является k -м информационным выходом устройства, выход генератора импульсов подключен к входу сумматора с фиксацией результата, выход К -го ключа второй группы подключен к информационному входу

k -го ключа третьей группы, выход которого подключен к входу установки в "0" К -го триггера первой группы, контакты второй пары Р-й группы второго массива контактов наборного поля подключены к первому и второму входу Р-го элемента И соответственно, выход которого подключен к входу установки в 0 p -ro триггера второй