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

(51) М. Кл. О 06 с присоединением за Гасударственный номнтет Севета Мнннстров СССР ве делам нзобретеннй н атнрьтнйтветствии тому, что ребора со- входами Изобретение отнссится к вычислитель-ной технике, в частности к устройствамдля моделирования графов, и может бытьиспользовано при определении числа деревьев графа, образованных с у.частием 5каждого ребра,Известно устройство для определениячисла деревьев графа, содержашее блокперебора сочетаний, элементы И по количеству простых циклов графа, число реберкоторых меньше числа вершин этого графаэлемепт ИЛИ, инвертор, счетчик числа деревьев, ключи, линию задержки, вентиль, счетчики участия ребер ь образованиидеревьев, первые входы которьх, первые 1 нвходы блока перебора. сочетаний и счетчика числа деревьев соединены с установочным входом устройства, а вторые входысчетчиков участия ребер в образованиидеревьев соединены с выходами ключей.Цель изобретения - повышение быстродействия устройства,Достигается это благодаряв устройстве выходы блока печетаний соединены с первыми оответствуюших ключей и в со стру.ктурои графа - с входами элементов И, выходы которых через элементИЛИ и инвертор соединены с одним входом вентиля, выход которого соединенс вторым входом счетчика числа деревьеви со вторыми входами ключей, а другойвход вентиля через линию задержки соединен с синхронизируюшим входом устройства и вторым входом блока переборачетаний, индикационный выход которосоединен с выходом устройства.На чертеже приведена блок-схемаустройства,Устройство для определения числа деревьев графа содержит блок 1 переборасочетаний, вентиль 2, элементы И 3,элемент ИЛИ 4, инвертор 5, счетчик 6числа деревьев, ключи 7, счетчики 8участия ребер в образовании деревьев,линию задержки 8, установочный вход 10,синхронизируюший вход 11 и индикационный выход 12.Работа устройства происходит следующим образом, Первоначально у исследу-4 держки 9 поступает на другой вход вентиля 2, то он проходит на вход счетчика 6 числа деревьев, увеличивая его показания на единицу, и через ключи 7 - на выходы тех счетчиков 8 участия ребер в образовании деревьев, которые соответствуют набору ребер, образующих данное дерево (показания этих счетчиков увеличиваются на единицу). Для определения числа деревьев графа и числа деревьев, образованных с:участием каждого ребра, необходимо перебрать все сочетания из П по (Ф -1), После того, как блок 1 перебора сочетаний перебрал все возможные сочетания, на выходе 12 появляется сигнал, который говорит об окончании испытания. Счетчик 6 числа деревьев графа показывает число сочетаний, которые не содержат простых циклов исследуемого графа, т,е. число деревьев графа, Счетчики 8 участия ребер в образовании деревьев показывает число деревьев графа, образованных с участием со- .ответствуюшего ребра.Повышение быстродействия устройства достигается за счет сокрашения числа рабочих тактов для анализа каждого сочетания ребер, а также за счет исключения затрат времени на определение электрическойпрово димости между "условными" вершинами модели графа в известном устройстве. емого графа определкотся все простые циклы с числомребер не более 5 -1, где 1,- число вершин графа. Блок 1 перебора сочетаний имеет Явыходов, где Я- число ребер графа. Каждый выход соответствует определенному ребру исследуемого графа. На входы элементов "И" 3 подключаются выходы блока перебора сочетаний, которые соответствуют ребрам, образующимФ У10 простой цикл. Каждый элемент И 3 соответствует определенному простому циклу графа и на ее входы подключены выходы блока, перебора сочетаний, которые соответствуют ребрам, образующим данный простой цикл, если число этих ребер не превышает вели 15 чиный -1, После установки устройства импульсом по входу 10 в исходное состояние (счетчиков 8 участия ребер в образовании деревьев и счетчика 6 числа деревьев в нулевое положение, блока 1 перебора сочета 20 ния в первое положение ), по синхронизуюшему входу 11 поступает серия тактовых импульсов на блок перебора сочетаний и на вход линии задержки 9. Блок перебора сочетаний,25 по каждому приходяшему импульсу выдает по вБходам очередное сочетание изщэлементов по (б, -1). Если очередное сочетание ( О -1) ребер не является деревом графа, то оно содержит как минимум один30 простой цикл, число ребер которого ее превышает (и). В этом случае при выдаче блоком перебора сочетаний этого сочетания на всех входах элементов И" 3, соответствуюшей простому циклу, входяшему в это сочетание, имеются сигналы, Элемент фИ" 3 срабатывает, и сигнал с ее выхода поступает на вход элемента ФИЛИ" 4, При одном и том же сочетании возможно, чти сработает несколько элементов И 3, При появлении сиг нала на выходе любого из этих элементов появляется сигнал на выходе элемента "ИЛИ" 4, который через инвечтор 5 не дает возможности импульсу с линии задержки 9(поступает в промеж:тке между двумя тактовыми им пульсами) пройти через вентиль 2 на входы ключей 7 и на входы счетчика 6 числа деревьев. Если сочетание, выданное блоком перебора сочетаний, соответствует (и) ребрам, образующим дерево в данном графе, то .оно не содержит ни одного простого цикла исследуемого графа, Б этом случае сочетание, выданное блоком перебора сочетаний, ие обеспечивает наличия всех сигналов на любом из элементов И 3, Следовательно, на выходах всех элементов "И" 3 и на выходе элемента "ИЛИ" 4 отсутствуютсигналы и тогда на выходе инвертора 5 имеется сигнал, который подается на вход вентиля 2. Когда задержанный тактовый сигнал с линии за 1 Предмет изобретенияУстройство для определения числа деревьев графа, содержащее блок перебора сочетаний, элементы И по количеству простых циклов графа, число ребер которых меньше числа вершин этого графа, элемент ИЛИ, инвертор, счетчик числа деревьев, ключи, линию задержки, вентиль, счетчики участия ребер в образовании деревьев, первые входы которых, первые входы блока перебора сочетаний исчетчика числа деревьев соединены с установочным входом устройства, а вторые входы счетчиков участия ребер в образовании, деревьев соединены с выходами ключей, о эл и ч а ю ш е е с я тем, что, с целью повышения быстродействия, в нем выходы блока перебора сочетаний соединены с первыми входами соответствующих ключей и в соответствии со структурой графа - с вхо, дами элементов И, выходы которых через элемент ИЛИ и инвертор соединены с одним входом вентиля, выход котррого соединен со вторым входом счетчика числа деревьев и со вторыми входами ключей, а другой вход вентиля через линию задержки соединен с синхронизируюшим входом устройства и вторым входом блока перебора сочетаний, индикационный выход которого соединен с выходом устройства.1485452 з ;3 Тираж одписно ннстров СС Н редпрнятие Патент, Москва, Г.59, Бережковская наб., 24 Изд, М Государственнопо делам Москва, 1 о комитета Советазобретений и открыт035, Раушская наб.,