Всесоюзная

 

ОПИСАН И Е

ИЗОБРЕТЕН ИЯ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ

Союз Ссеетсних

Социалистических

Респтблин

Зависимое от авт. свидетельства №

Заявлено,31.Х.1967 (№ 119,3850/18-24) с присоединением заявки №

Приоритет

М. Кл. G 06f 15/34

Комитет по делатх изобретений и открытий при Совете Министров

СССР

УДК 681.323.16(088.8) Опубликовано 28.Xll.1972. Бюллетень ¹ 5 за 1973

Дата опубликования описания 13.11.1973

Автор изобретения! --:-" -:.-О:ОБ1-1ГАВ ,}.,. ) *" н,-: I g 1 )1 Щ и

Е1 1ЬЛЙОТЕКА

P. В. Дмитришин

Заявитель

УСТРОЙСТВО ДЛЯ НАХОЖДЕНИЯ ДЕРЕВЬЕВ ГРАФА

Изобретение относится к области вычислительной техники.

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

Однако такие устройства не позволяют решать задачу нахождения деревьев ненаправленногоо гр а фа.

В предложенном устройстве этот недостаток исключен.

Устройство отличается от известных тем, что оно содержит блоки коэффициентов пересчета и счетчик числа деревьев. Причем выходы каждого счетчика соединены со входами блока индикации, входами соответствующего блока коэффициентов пересчета и одними из входов соответствующих схем «И», вторые входы которых соединены с гнездами входящих в узел дуг графа, а их выходы через схему «ИЛИ» с усилителями на выходе присоединены к гнездам выходящих из узла дуг графа и к счетным входам триггеров, подключенных выходами ко входам схемы «И». Выход последней непосредственно соединен со входом счетчика числа деревьев и одним входом блока индикации, а через переключатель и диод со входом останова генератора тактовых импульсов и другим входом блока индикации.

Выходы блоков коэффициентов пересчета сое5 динены со входом сброса соответствующего счетчика и одним пз входов схемы «ИЛИ», подключенной вторым входом к выходу переполнения предыдущего счетчика, выходом к суммирующему входу последующего счетчи10 ка и через переключатель,ко второму входу последующей схемы «ИЛИ». Выход генератора тактовых импульсов подключен к суммирующему входу первого счетчика, через линию задержки соединен с гнездами корневого узла

15 и через переключатель — со вторым входом первой схемы «I IЛИ». Выходы последнего блока коэффициентов пересчета, выход переполнения последнего счетчика и выход последнего переключателя через диоды подключены

20 ко входу блока индикации.

Блок-схема устройства приведена па чертеже.

Устройство содержит блок индикации 1, KkIOIII< III ска 2, I HOIIICII 31 — 8„, перек IkO I3T0JIII

25 41 — 4„генератор тактовых импульсов 5, линшо задержки б, счетчики 7,— 7, блоки коэффициентов пересчета 8,— 8», схемы «И» 9и — 9„», схемы «ИЛИ» 10,— lU с усилитслямп на выкодс, триггеры 11 — 11», схему «I I» 12; счетчик

30 18 числа деревьев, переключатель 14, схемы,364939

10

«ИЛИ» 15> — 15», наборное поле (на чертеже не показано) с гнездами входящих в узел дуг графа 16,— 16», гнездами выходящих из узла дуг графа 17 — 17„и гнездами корневого узла 18.

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

После соединения в соответствии с топологией исследуемого графа гнезд входящих

16> — 16» и выходящих 17> — 17» из узла дуг с помощью проводников (на чертеже не показаны) переключатели 4 — 4, соответствующие этим узлам, устанавливаются в нижнее положенис. На блоках коэффициентов пересчета 8,— 8» устанавливаются значения, равные степени данного .узла (числу входящих дуг). После этого нажатием кнопки пуска 2 запускают генератор тактовых импульсов 5, с выхода которого импульсы поступают на в <оды счетчиков 7> — 7„, и в каждый цикл сбрасывают в нуль триггеры 11,— Il Кроме того, тактовые импульсы через линию задержки б поступают на гнезда корневого узла 18. Время задержки линии задержки б должно быть втрое меньше периода следования тактовых импульсов. После поступления на вход некоторого счетчика 7, p(s) импульсов (где о(з) число дуг, входящих в данный узел) этот счетчик сбрасывается в нуль, а содержимое следующего счетчика 7, увеличивается на единицу.

Так как выходы счетчиков 7 — 7» соединены с одними из входов схем «И» 9Π— 9„,„то при поступлении сигнала на вторые входы этих схем появление импульса на выходе этих схем возможно только в случае совпадения сигналов на входах. В каждой строке такое совпадение возможно только на одной из этих схем «И». С выхода этой строки через схему

«ИЛИ» (10 — 10„) импульс опрокидывает триггер (11,— 11») данного узла и через гнезда выходящих из узла дуг графа 17 — 17» и проводники поступают на вторые входы соответствующих схем «И» (9О< — 9„,,) и т. д, Таким образом, импульс с гнезд корневого узла

18 может по проводникам наборного поля и схемам «И» 9О < — 9„,, поступить на входы всех триггеров 11,— П», если к ним имеются соединительные пути, что означает наличие дерева у исследуемого графа. Если дерево имеется, па выходе схемы «И» 12 появляется сигнал.

В непрерывном режиме (переключатель 14 разомкнут) генератор тактовых импульсов 5 работает до останова устройства. В этом случае счетчик 13 числа деревьев укажет число

55 деревьев в графе. Если переключатель 14 замкнут, то импульс с выхода схемы «И» 12 поступает также на останов генератора тактовых импульсов 5 и в блок индикации 1. После фиксации данного дерева генератор тактовых импульсов 5 запускается либо с выхода блока индикации 1, либо опять кнопкой пуска 2.

Окончание работы устройства происходит после переполнения последнего из счетчиков

7»Предмет изобретения

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

364939

Редактор Л. Утехина

Заказ 248/7 Изд. Ж о3 Тирам< 647 Подписное

ЦНИИПИ Комитета по делам изобретений и открытий прн Совете Министров СССР

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

Типография, пр. Сапунова, 2

Составитель Г. Сорокин

Техред Л. Грачева

Корректоры: E. Михеева и Л. Кириллова