ВСЕСОЮЗНАЯ Советский патент 1973 года по МПК G06F15/173 

1

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

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

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

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

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

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

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

Устройство содержит блок индикации /. кнопку пуска 2, кнопки , переключатели , генератор тактовых импульсов 5, линию задержки 6, счетчики 7i-7, блоки коэффициентов пересчета Sj-8, схемы «И схемы «ИЛИ с усилителями на выходе, триггеры //I-П, схему «И /2; счетчик /5 числа деревьев, переключатель 14, схемы

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

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

После соединения в соответствии с топологией исследуемого графа гнезд входящих 16i-16к и выходящих 17i-17 из узла дуг с помощью проводников (на чертеже не показаны) переключатели , соответствующие этим узлам, устанавливаются в нижнее ноложение. На блоках коэффициентов нересчета 8i-8 устанавливаются значения, равные степени данного .узла (числу входящих дуг). После этого нажатием кнопки пуска 2 запускают генератор тактовых импульсов 5, с выхода которого импульсы поступают на входы счетчиков /1-7у, и в каждый цикл сбрасывают в нуль триггеры lli-11. Кроме того, тактовые импульсы через линию задержки 6 поступают на гнезда корневого узла 18. Время задержки линии задержки 6 должно быть втрое меньше периода следования тактовых импульсов. После поступления на вход некоторого, счетчика 7s p(s) импульсов (где p(s) число дуг, ВХОДЯЩИХ в данный узел) этот счетчик сбрасывается в нуль, а содержимое следующего счетчика увеличивается на единипу.

Так как выходы счетчиков соединены с одними из входов схем «И Род - 9п,к, то при Поступлении сигнала на вторые входы этих схем появление импульса на выходе этих схем возможно только в случае совпадения сигналов на входах. В каждой строке такое совпадение возможно только на одной из этих схем «И. С выхода этой строки через схему «ИЛИ (lOi-10 } импульс опрокидывает триггер (11-i-lig) данного узла и через гнезда выходящих из узла дуг графа и проводники поступают на вторые входы соответствующих схем «И (Род - РЛ.К) и т. д. Таким образом, импульс с гнезд корневого узла 18 .может по проводникам наборного поля и схемам «И РОД - Р„,к поступить на входы всех триггеров lli-//„, если к ним имеются соединительные пути, что означает наличие дерева у исследуемого графа. Если дерево имеется, на выходе схемы «И 12 появляется сигнал.

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

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

фиксации данного дерева генератор тактовых импульсов 5 запускается либо с выхода блока индикации 1, либо опять кнопкой пуска 2. Окончание работы устройства происходит после переполнения последнего из счетчиков

7i-7,.

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

Устройство для нахождения деревьев графа, содержащее блок индикации, счетчики, диоды,

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

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

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

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