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

СОЮЗ СОВЕТСНИХСОЦИД ЛИСТИЧЕСНИХРЕСПУБЛИН 5)4 С 06 Г ОПИСАНИЕ ИЗОБРЕТЕНИ А ВТОРСНОМУ СВИДЕТЕЛЬСТВУ СЛЕДОВА В 36В.М.Балакире льство СССР15/20, 1982.ство СССР5/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Изобретение относится к вычислительной технике и может быть использовано для решения задач на вероятностных графах,Цель изобретения -расширение функ- бциональных возможностей устройстваза счет определения веса подграфовв каждом розыгрыше вершин и ребер.На фиг. 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 реле,30Устройство работает следующим образом. 2В первом такте импульс начальной установки поступает по входу 4 на первые Б.-входы триггеров 12 и 13 и устанавливает их в нулевое состояние. Во втором такте на входы 14 и 15 поступают данные розыгрыша вершин и ребер, в результате чего открываются соответствующие ключи 9 и 10 (при этом все выходы ключа 9 соединяются с информационным входом, и между всеми выходами ключа образуется электрический контакт). Единичные сигналы с прямых выходов триггеров 11 открывают соответствующие ключи 8. В результате этого образуется электрический контакт между всеми вершинами и ребрами, присутствующими в розыгрыше. Если в данном розыгрыше не выпало ни одной вершины, то единичные потенциалы с инверсных выходов триггеров 11 поступают на все входы элемента И 5, который выдает импульс на выход. При отсутствии сигнала на выходе 3 в третьем такте на вход 11 устройства поступает сигнал, запускающий генератор 2, первый импульс которого своим передним фронтом обнуляет сумматор 22, а также проходит .через первый открытый ключ 8 и соответствующий ключ 9 на контакты 23 и 24 первого и второго массивов контактов наборного поля, соответствующие связанным меж10 15 20 25 30 35 40 45 50 55 з 13ду собой ребрам и вершинам в первомподграфе. При этом импульс проходитчерез соответствующие сработавшиеключи 9 и 10. При появлении импульсана контактах одной из групп контактов 23 он попадает на второй Б.-входсоответствующего триггера 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. Число подграфов, на ко-. 416464торые распадается граф в каждом испытании, равно числу выходов 16, по которым вьдается информация, а веса подграфов вьдаются по выходам 16.5 Формула изобретения Устройство для исследования вероятностных графов, содержащее элемент И, четыре группы ключей, две группы триггеров, генератор импульсов,.распределитель импульсови наборное поле, контакты которого соединены согласно, топологии графа, причем вХод пуска генератора импульсов является входом пуска устройства, выход генератора импульсов подключен к информационным входам первых ключей первой и второй групп: вход установки в "1" К -го триггера первой группы ( К = 1, Н, где Н - количество вершин в графе) является К-м входом розыгрыша вершин устройства, прямой выход К -го триггера первой группы подключен к управляющим входам К -х ключей второй и третьей групп, инверсный выход К-го триггера первой группы (К+Н) подключен к управляющему входу К -го ключа первой группы, выход М-го ключа первой группы ( М =, 1 Н - 2) подключен к информационному входу. (В+1) ключей первой и второй групп, выход (Н)-го ключа первой группы подключен к информационному входу Н -го ключа второй груп. пы, выход К-го ключа третьей группы подключен к контактам К -й группы первого массива контактов наборного поля, вход установки в "1" р-го триггера второй группы ( р = 1 е, гдеЕ - количество ребер в графе) является р -м входом розыгрыша ребер устройства, прямой выход р-го триггеравторой группы подключен к управляющему входу р-го ключа четвертойгруппы, входы управляющей цепи которого подключены к первой паре контактов р -й группы второго массива контактов наборного поля, выход элемента И подключен к входу останова генератора импульсов и является выходом признака окончания работы устройства, о т л и ч а ю щ е е с я тем,что, с целью расширения функциональных возможностей за счет определениявеса подграфов в каждом розыгрышевершин и ребер, в устройство введенысумматор с фиксацией результата, двегруппы. ве Составитель Л,МипинРедактор М.Лылын Техред М.Дидык Коррек тай 438/53 Тираж 672ВНИИПИ Государственногпо делам изобретени 11303.5, Москва, Ж, Ра Подписно омитета СССРоткрытийкая наб., д,венно-полиграфическое предприятие, г, Ужгород, ул, Проектная, 4 роизвод 5 13 группы блоков памяти, пятая группа ключей и группа элементов И, причем инверсный выход к-го триггера первой группы подключен к 1 -му входу элемента И и к входу признака чтения К-го блока памяти первой группы, выход которого подключен к входу К-го слагаемого сумматора с фиксацией результата, инверсный выход р -го триггера второй группы подключен к айоду чтения р -го блока памяти второй группы, выход которого подключен к входу (Н+ р) - го слагаемого сумматора с фиксацией результата, выход которого подключен к информационным входам всех ключей пятой группы, вход опроса устройства подключен к тактовому входу распределителя импульсов,4164 б 61-й выход которого подключен к управляющему входу -го ключа пятой группы,выход которого является К -м информационным выходом устройства, выходгенератора импульсов подключен к входу сумматора с фиксацией результата, выход К -го ключа второй группыподключен к информационному входу 10К-го ключа третьей группы, выход которого подключен к входу установкив0 М -го триггера первой группы,контакты второй пары Р-й группы второго массива контактов наборного поляподключены к первому и второму входу Р-го элемента И соответственно,выход которого подключен к входу установки в 0 Р -го триггера второй