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

 

Изобретение является усовершенствованием устройства по авт. св. ,№ 922781, относится к области вычислительной техники, может быть использовано Для анализа систем, отображаемых вероятностными графами, и позволяет выделять деревья в графе, вес которых не меньше эталонного значения веса дерева. Целью изобретения является расширение функциональных возможностей устройства за счет вьщеления деревьев, вес которых превьшает эталонное значение веса. С этой целью в устройство введен блок сравнения весов, содержащий регистр эталонного значения веса, группу регистров весов ребер выбранного дерева, сумматор и схему сравнения. В процессе работы информация о ребрах выбранного дерева анализируется оператором, который по результатам анализа вводит в соответствующие регистры группы веса ребер выбранного дерева, после суммирования которых вес выбранного дерева сравнивается с эталонным значением веса на схеме сравнения. Если вес выбранного дерева не меньше эталонного значения веса, признак неотрицательного результата с выхода схемы сравнения блокирует запись кодов ребер в регистры устройства. Работа устройства продолжается до перебора всех деревьев графа. При этом в регистры устройства записываются коды ребер только тех деревьев, вес которых не меньше эталонного значения, - 2 ил. i (Л со ГчЭ 4 О СО СО

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

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

РЕСПУБЛИК (50 4 G 06 G 7/122

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ (61) 922781 (2 1) 4039253/24-24 (22) 20.03.86 (46) 15.07.87. Бюл. У 26 (72) В. Н, Червяцов, А. Я. Ярмыш и А. И. Шаромов (53) 681. 333 (088. 8) (56) Авторское свидетельство СССР

N - 748428, кл. G 06 G 7/122, 1978.

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

У 922?81, кл. G 06 G 7/122, 1978. (54) УСТРОЙСТВО ДЛЯ РАЗЛОЖЕНИЯ ГРАФА

НА ДЕРЕВЬЯ (57) Изобретение является усовершенствованием устройства по авт. св, Ф 922781, относится к области вычислительной техники, может быть использовано для анализа систем, отображаемых вероятностными графами, и позволяет выделять деревья в графе, вес которых не меньше эталонного значения веса дерева. Целью изобретения является расширение функциональных воэможностей устройства за счет выделения деревьев, вес которых превышает,.SU„„1324039 А 2 эталонное значение веса. С этой целью в устройство введен блок сравнения весов, содержащий регистр эталонного значения веса, группу регистров весов ребер выбранного дерева, сумматор и схему сравнения. В процессе работы информация о ребрах выбранного дерева анализируется оператором, который по результатам анализа вводит в соответствующие регистры группы веса ре6 ер выб р ан ног о дер ев а, по сле суммирования которых вес выбранного дерева сравнивается с эталонным значением веса на схеме сравнения. Если вес выбранного дерева не меньше эталонного значения веса признак неотрицаt е тельного результата с выхода схемы сравнения блокирует запись кодов ребер в регистры устройства. Работа устройства продолжается до перебора всех деревьев графа, При этом в регистры устройства записываются коды ребер только тех деревьев, вес кото рых не меньше эталонного значения.2 ил.

1 13240

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

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

В состав устройства входит второй элемент И 1, наборное поле 2, ключи

3,...,3 ребер (где М вЂ” количество ребер в графе), счетчики 4, ° ..,4 (где И вЂ” количество вершин в графе), первая группа элементов 5 ...,,5 триггеры 6„„,...,6 „„„(ребер), элементы 7,..., 7 „, „„з апрета >

2,1 распределители 8„,...,8 1,, второе наборное поле 9, вторая группа элементов И 10„,...,10„,,, третье наборное поле 11, элементы 122 12„ задержки, вход 13 сброса устройства, первый вход 14 тактовых импульсов устройства, вход 15 опроса устройства, выход 16 признака останова устройства, вход 17 импульсов стирания информации устройства, блок 18 шифраторов, дополнительный регистр 19, распределитель 20, сдвигающие регист-35 ры 21„,...,21,„, первый элемент И 22, входы 23 задания весов ребер устрой:— ства, блок 24 сравнения весов, второй вход 25 тактовых импульсов устройства, выходы 26 признаков выбран" 10 ных ребер устройства, вход 27 задания эталонного веса устройства, сумматор 28> схема 29 сравнения, регистр

30 эталонного значения веса и группы регистров 31„,,31„,„.

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

В первом и во втором тактах устройство работает аналогично устройству-прототипу, за исключением того, что в первом такте дополнительно производится начальная установка (сброс) регистра 30 и группы регистров 31

1 ...,31 „, а во втором такте по результатам анализа признаков выбранных ребер оператор производит ввод весов выбранных ребер в соответствующие регистры 31 >...,31 », группы и ввод эталонного значения веса дерева.

В третьем такте по сигналу на входе 25 информация с регистров

31 >...,31 группы поступает на входы сумматора> вес полученного дерева с его выхода сравнивается с эталонным значением веса дерева и по результатам сравнения, если вес полученного дерева не меньше эталонного значения веса, формируется признак неотрицательного результата, который в качестве дополнительного условия поступает на (0+1)-й вход элемента

И 1. В остальном работа устройства совпадает с работой устройства-прототипа.

Изобретение обеспечивает возможность оценки весовых характеристик деревьев, следовательно, можно выбрать отдельные деревья, весовые качества которых удовлетворяют определенным условиям, Формула и з о б р е т е н и я

Устройство для разложения графа на деревья по авт. св. N> 922781, о т л и ч а ю щ е е с я тем, что, с целью расширения функциональных воэможностей устройства за счет выделения деревьев, вес которых превышает эталонное значение веса, в него введен блок сравнения весов, содержащий группу регистров, сумматор, схему сравнения и регистр эталонного значения веса, причем информационные выходы распределителей импульсов являются выходами признаков выбранных ребер устройства, информационные входы регистров группы являются входами задания весов ребер .устройства, информационный вход регистра эталонного значения веса является входом задания эталонного значения веса устройства, второй тактовый вход устройства подключен к входам признаков чтения всех регистров группы и к входу признака чтения регистра эталонного значения веса, выход которого подключен к первому входу схемы сравнения, вход сброса устройства подключен к входу начальной установки регистра эталонного значения веса и к входам начальной установки всех регистров группы, информационные выходы которых подключены к соответствующим входам слагаемых сумматора, выход которого подключен к второму вхо1324039, 4 ду схемы сравнения, выход которой подключен к (И+1)-му входу второго элемента И, 1324039

Составитель А, Мишин

Редактор М. Дылын Техред И.Попович Корректор Г. Решетник

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

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

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

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