Устройство для разложения графа на деревья Советский патент 1987 года по МПК G06G7/122 

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

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

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

В состав устройства входит второй элемент И 1, наборное поле 2, ключи 3 ,,,,,3 ребер (где М - количество ребер в графе), счетчики (где N - количество вершин в графе), первая группа элементов 5„ ,,,,,5, триггеры 6 ,. ,, ,6. д, (ребер), элементы 7,.,,7. / запрета, распределит ели 8,,,,,8ц|.1 , второе . наборное поле 9, вторая группа элементов И 10 ,., ,, 10|Ц(.,, третье наборное поле 1 1 , элементы 12л , , . , 2|у задержки, вход 13 сброса устройства, Первый вход 14 тактовых импульсов устройства, вход 15 опроса устройства, выход 16 признака останова устройства, вход 17 импульсов стирания информации устройства, блок 18 шифраторов, дополнительный регистр 19, распределитель 20, сдвигающие регистры 2 1 ,, , , ,2 1| , первый элемент И 22 входы 23 задания весов ребер устройства, блок 24 сравнения весов, второй вход 25 тактовых импульсов -устройства, выходы 26 признаков выбранных ребер устройства, вход 27 зада- пня эталонного веса устройства, сумматор 28, схема 29 сравнения, регист 30 эталонного значения веса и группы регистров ЗЦ ,, , , ,3.,

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

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

и ввод эталонного значения веса дерева,

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

5

0

5

0

5

0

5

0.

5 31 ,31

группы поступает на

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

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

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

t

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

выход которого подключен к

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

ды которых подключены к соответству- ду схемы сравнения, выход которой ющим входам слагаемых сумматора, вы- подключен к (Н+1)-му входу второго ход которого подключен к второму вхо- элемента И.

.Гт.21бгм J/A -4 -; тГ-л м

I I 1/ i

4,

« «

Л

/J

.

Редактор М. Дьшьш

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

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

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

ВНИИПИ Государственного комитета СССР

по делам изобретений и открытий 113035, Москва, Ж-35, Раушская наб., д. 4/5

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

29

Нзле-

менту 1

28

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