Всесоюзная

Союз Сонетсних Социалистических РеспубликЗависимое от авт, свидетельстваЗаявлено,31.Х,1967 ( 1193850/18-24)с присоединением заявкиМ. Кл, б 061 15 34 Комитет по аелатхобретениЯ и открытийри Совете МинистровСССР иорит К 681,323.16(088.8 Опубликовано 28,Х 11,1972. Бюллетень5 за 1973 Дата опубликования описания 13.11,1973. Дмитриши Заявител УСТРОЙСТВО Д ХОЖДЕНИЯ ДЕРЕВЬЕВ ГРАФА Изобретение относится к области вычислительной техники.Известны устройства для нахождения деревьев графа, содержащие блок индикации, счетчики, диоды, схемы И и ИЛИ, пере ключатели, линию задержки, генератор тактовых импульсов, схемы ИЛИ с усилителями на выходах, триггеры, наборное поле с гнездами входящих в узел и выходящих из узла дуг графа и гнездами, корневого узла.10Однако такие устройства не позволяют решать задачу нахождения деревьев ненаправленногоо гр а фа.В предложенном устройстве этот недостаток исключен. 15Устройство отличается от известных тем, что оно содержит блоки коэффициентов пересчета и счетчик числа деревьев. Причем выходы каждого счетчика соединены со входами блока индикации, входами соответствующего 20 блока коэффициентов пересчета и одними из входов соответствующих схем И, вторые входы которых соединены с гнездами входящих в узел дуг графа, а их выходы через схему ИЛИ с усилителями на выходе присое динены к гнездам выходящих из узла дуг графа и к счетным входам триггеров, подключенных выходами ко входам схемы И. Выход последней непосредственно соединен со входом счетчика числа деревьев и одним входом 30 блока индикации, а через переключатель и диод со входом останова генератора тактовых импульсов и другим входом блока индикации. Выходы блоков коэффициентов пересчета соединены со входом сброса соответствующего счетчика и одним из входов схемы ИЛИ, подключенной вторым входом к выходу переполнения предыду 1 цего счетчика, выходом к суммирующему входу последующего счетчика и через переключатель,ко второму входу последующей схемы ИЛИ. Выход генератора тактовых импульсов подключен к суммирующему входу первого счетчика, через линию задержки соединен с гнездами корневого узла и через переключатель - со вторым входом первой схемы 11 ЛИ. Выходы последнего блока коэффициентов пересчета, выход переполнения последнего счетчика и выход последнего переключателя через дподь 1 подключены ко входу блока индикации,Блок-схема устройства приведена ца чертеже.Устройство содержит блок индикации 1, кнопку пуска 2, кнопки 31 - 8, переключатсл 4, - 4, генератор тактовых импульсов 5, лпцшо задержки б, сеики 7, - 7, блоки коэффициентов пересчета 8, - 8, схемы И 9 сг - 9, схемы ИЛИ 10, - 1 О с усцлцтслямц ца выкодс, триггеры 11, - 11, схему И 12; счетчик 18 числа деревьев, переключатель 14, схемы5 Ю ИЛИ 15 - 15, наборное поле (на чертеже не показано) с гнездами входящих в узел дуг графа 16, - 16, гнездами выходящих из узла дуг графа 17 - 17 и гнездами корневого узла 18.Устройство работает следующим образом, После соединения в соответствии с топологией исследуемого графа гнезд входящих 16, - 16 и выходящих 17 - 17 из узла дуг с помощью проводников (на чертеже не показаны) переключатели 4, - 4, соответствующие этим узлам, устанавливаются в нижнее положенис. На блоках коэффициентов пересчета 8, - 8 устанавливаются значения, равные степени данного.узла (числу входящих дуг). После этого нажатием кнопки пуска 2 запускают генератор тактовых импульсов 5, с выхода которого импульсы поступают на в:оды счетчиков 7, - 7, и в каждый цикл сбрасывают в нуль триггеры 11, - 11, Кроме того, тактовые импульсы через линию задержки б поступают на гнезда корневого узла 18. Время задержки линии задержки б должно быть втрое меньше периода следования тактовых импульсов. После поступления на вход некоторого счетчика 7, р(з) импульсов (где р(з) число дуг, входящих в данный узел) этот счетчик сбрасывается в нуль, а содержимое следующего счетчика 7,. увеличивается на единицу.Так как выходы счетчиков 7, - 7 соединены с одними из входов схем И 9 О - 9,то при поступлении сигнала на вторые входы этих схем появление импульса на выходе этих схем возможно только в случае совпадения сигналов на входах. В каждой строке такое совпадение возможно только на одной из этих схем И. С выхода этой строки через схему ИЛИ (10, - 10) импульс опрокидывает триггер (11, - 11) данного узла и через гнезда выходящих из узла дуг графа 17, - 17 и проводники поступают на вторые входы соответствующих схем И (9 - 9) и т, д, Таким образом, импульс с гнезд корневого узла 18 может по проводникам наборного поля и схемам И 9 О- 9 поступить на входы всех триггеров 11, - П, если к ним имеются соединительные пути, что означает наличие дерева у исследуемого графа. Если дерево имеется, па выходе схемы И 12 появляется сигнал.В непрерывном режиме (переключатель 14 разомкнут) генератор тактовых импульсов 5 работает до останова устройства. В этом случае счетчик 13 числа деревьев укажет число 15 го г 5 30 35 40 45 50 55 деревьев в графе. Если переключатель 14 замкнут, то импульс с выхода схемы И 12 поступает также на останов генератора тактовых импульсов 5 и в блок индикации 1. После фиксации данного дерева генератор тактовых импульсов 5 запускается либо с выхода блока индикации 1, либо опять кнопкой пуска 2, Окончание работы устройства происходит после переполнения последнего из счетчиков7 Предмет изобретенияУстройство для нахождения деревьев графа, содержащее блок индикации, счетчики, диоды, схемы И и ИЛИ, переключатели, линию задержки, генератор тактовых импульсов, схсмы ИЛИ с усилителями на выходах, триггеры, наборное поле с гнездами входящих в узел и выходящих из узла дуг графа и гнездами корневого узла, отличающееся тем, что, с целью расширения класса решаемых задач, оно содержит блоки коэффициентов пересчета и счетчик числа деревьев, причем выходы каждого счетчика соединены со входами блока индикации, входами соотвстствующего блока коэффициентов пересчета и одними из входов соответствующих схем И, вторые входы которых соединены с гнездами входящих в узел дуг графа, а их выходы через схему ИЛИ с усилителями на выходе присоединены к гнездам выходящих из узла дуг графа и ко счетным входам триггеров, подключенных выходами ко входам схемы И, выход которой непосредственно соединен со входом счетчика числа деревьев и одним из входов блока индикации, а через переключатель и диод - со входом останова генератора тактовых импульсов и другим входом блока индикации, выходы блоков коэффициентов пересчета соединены со входом сброса соответствующего счетчика и одним входом схемы ИЛИ, подключенной вторым входом к выходу переполнения предыдущего счетчика и присоединенной выходом к суммирующему входу последующего счетчика и через переключатель ко второму входу последующей схемы ИЛИ, выход генератора тактовых импульсов подключен к суммирующему входу первого счетчика, через линию задержки соединен с гнездами корневого узла и через переключатель со вторым входом первой схемы ИЛИ, выходы последнего блока коэффициентов пересчета, выход переполнения последнего счетчика и выход последнего переключателя через диоды подключены ко входу блока индикации.едактор техн рачев ехр Типография, и р. Сапунова аказ 248/7 Изд. М 93 Тирани 647 ПодписноеЦНИИПИ Комитета по делам изобретений н открытий при Совете Министров СССР Москва, Ж, Раушская наб., д. 45