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

/12 ЕЛЬОТВ Н АВТОРСИОМ етельство С С 7/122) 19 ельство СССР С 7/122, 19 РАЗЛОЖЕНИЯ ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССРПОДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИИ(56) Авторское свид ССР У 748428, кл. С 06 78.Авторское свидетУ 922781,кл. С 06 78. (54) УСТРОЙСТВО ДЛЯ ГРАФА НА ДЕРЕВЬЯ(57) Изобретение является усовершенствованием устройства по авт, св, В 922781, относится к области вычислительной техники, может быть использовано для анализа систем, отображаемых вероятностными графами, и позволяет выделять деревья в графе, вес которых не меньше эталонного значения веса дерева, Целью изобретения является расширение функциональных воэ" можностей устройства за счет выделения деревьев, вес которых превышает эталонное значение веса. С этой целью в устройство введен блок сравнения весов, содержащий регистр эталонного значения веса, группу регистров весов ребер выбранного дерева,сумматор и схему сравнения. В процессе работы информация о ребрах выбранного дерева анализируется оператором,который по результатам анализа вводитв соответствующиерегистры группывесаребер выбранного дерева, после суммирования которых вес выбранного дерева сравнивается с эталонным значением веса на схеме сравнения. Если весвыбранного дерева не меньше эталонного значения веса, признак неотрицательного результата с выхода схемысравнения блокирует запись кодов ребер в регистры устройства. Работаустройства продолжается до переборавсех деревьев графа, При этом в регистры устройства записываются кодыребер только тех деревьев, вес которых не меньше эталонного значения2 ил.1 13240Изобретение относится к вычислительной технике и может быть испопьзовано для исследования характеристик разложения графа на деревья всистемах, отображаемых вероятностными графами.Цель изобретения - расширениефункциональных возможностей устройства за счет выделения деревьев,вес которых превышает эталонное значение веса,На Фиг. 1 приведена функциональная схема устройства; на Фиг. 2 -функциональная схема блока сравнениявесов,15В состав устройства входит второйэлемент И 1, наборное поле 2, ключи3 3 ребер (где М - количестворебер в графе), счетчики 4,,4(где И - количество вершин в графе), 20первая группа элементов 5 ь5триггеры 66ц (ребер),элементы 7 7запрета,9Враспределители 8811 второенаборное поле 9, вторая группа элементов И 1010 третье наборное поле 11, элементы 12112 д,задержки, вход 13 сброса устройства,первый вход 14 тактовых импульсовустройства, вход 15 опроса устройства, выход 16 признака останова устройства, вход 17 импульсов стиранияинформации устройства, блох 18 шифраторов, дополнительный регистр 19,распределитель 20, сдвигающие регист ры 2121, , первый элемент И 22,входы 23 задания весов ребер устрой: -ства, блок 24 сравнения весов, второй вход 25 тактовых импульсов устройства, выходы 26 признаков выбран" 10ных ребер устройства, вход 27 задания эталонного веса устройства, сумматор 28, схема 29 сравнения, регистр30 эталонного значения веса и группы регистров 31, ,31,.45Устройство работает следующимобразом.В первом и во втором тактах устройство работает аналогично устройству-прототипу, за исключением того,что в первом такте дополнительно производится начальная установка (сброс)регистра 30 и группы регистров 31,31 , а во втором такте по результатам анализа признаков выбранных ребер оператор производит вводвесов выбранных ребер в соответствую..щие регистры 3131 ., группы и ввод эталонного значения веса дерева,В третьем такте по сигналу на входе 25 информация с регистров 31 ,31, группы поступает на входы сумматора вес полученного дерева с его выхода сравнивается с эталонным значением веса дерева и по результатам сравнения, если вес полученного дерева не меньше эталонного значения веса, формируется признак неотрицательного результата, который в качестве дополнительного условия поступает на (И+1)-й вход элемента И 1. В остальном работа устройства совпадает с работой устройства-прототипа.Изобретение обеспечивает возможность оценки весовых характеристик деревьев, следовательно, можно выбрать отдельные деревья, весовые качества которых удовлетворяют определенным условиям,Формула изобретенияУстройство для разложения графа на деревья по авт. св. В 922781, о т л и ч а ю щ е е с я тем, что, с целью расширения функциональных воэможностей устройства за счет выделения деревьев, вес которых превышает эталонное значение веса, в него введен блок сравнения весов, содержащий группу регистров, сумматор, схему сравнения и регистр эталонного значения веса, причем информационные выходы распределителей импульсов являются выходами признаков выбранных ребер устройства, инФормационные входы регистров группы являются входами задания весов ребер устройства, информационный вход регистра эталонного значения веса является входом задания эталонного значения веса устройства, второй тактовый вход устройства подключен к входам признаков чтения всех регистров группы и к входу признака чтения регистра эталонного значения веса, выход которого подключен к первому входу схемы сравнения, вход сброса устройства подключен к входу начальной установки регистра эталонного значения веса и к входам начальной установки всех регистров группы, информационные выходы которых подключены к соответствующим входам слагаемых сумматора, выход которого подключен к второму вхо 1324039 , 4ду схемы сравнения, выход которойподключен к (И+1)-му входу второгоэлемента И,1324039 Составитель А, МишинТехред И,Попович Редактор М. Дыпын Корректор Г. Решетник За Тираж 672 ПодписноеССР ногоний ауш д в оиэводственно-полиграфическое предприятие, г, Ужгород,роектн 2967/53 ВНИИПИ по 113035, Государств лам изобре осква, Жомитета открыти кая наб