Устройство для определения числа деревьев графа Советский патент 1975 года по МПК G06F15/173 

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

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

Цель изобретения - повышение быстродействия устройства.

Достигается это благодаря тому, что в устройстве выходы блока перебора сочетаний соединены с первыми входами

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

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

Устройство для определения числа деревьев графа содержит блок 1 перебора сочетаний, вентиль 2, элементы И 3, элемент ИЛИ 4, инвертор 5, счетчик 6 числа деревьев, ключи 7, счетчики 8 участия ребер в образовании деревьев, линию задержки 9, установочный вход 10 синхронизирующий вход 11 и индикационный выход 12.

Работа устройства происходит следующим образом. Первоначальна у исследу емого графа определяются все простые циклы с числомребер не более -, где fj,- число вершин графа. Блок 1 перебора . сочетаний имеет ffl выходов, где/П- число ребер графа. Каждый выход соответствует определенному ребру исследуемого графа. На входы элементов подключаются выходы блока перебора сочетаний, которые соответствуют ребрам, образующим простой цикл. Каждый элемент И 3 соответствует определенному простому циклу гр фа и на ее входы подключены выходы блока перебора сочетаний, которые соответствуют ребрам, образующим данный простой цикл, если число этих ребер не превышает вели- чиныП-1. После установки устройства импульсом по входу 10 в исходное состояние (счетчиков 8 участия ребер в образовании деревьев и счетчика 6 числа деревьев в нулевое положение, блока 1 перебора сочетания- в первое положение ), по синхронизующ му входу 11 поступает серия тактовых импульсов на блок перебора сочетаний и на вх линии задержки 9, Блок перебора сочетаний по каяедому приходящему импульсу выдает по вб1ходам очередное сочетание из|)7элемен тов по (/г-1). Если очередное сочетание (ft -1) ребер не является деревом графа, то оно содержит как минимум один простой цикл, число ребер которого ее превышает (л-1). В этом случае при выдаче блоком перебора сочетаний этого сочетания па всех входах элементов И 3, соответст вующей простому циклу, входящему в это сочетание, имеются сигналы. Элемент И 3 срабатывает , и сигнал с ее выхода поступа на вход элемента ИЛИ 4. При одном и то же сочетании возможно, что сработает несколько элементов И 3. При появлении сиг нала на выходе любого из этих элементов появляется сигнал на выходе элемента ИЛИ который через инвертор 5 не дает возможности импульсу с линии задержки 9(поступа в промеж}аке между двумя тактовыми импульсами) пройти через вентиль 2 на входы ключей 7 и на входы счетчика 6 числа деревьев. Если сочетание, выданное блоком перебора сочетаний, соответствует (п-1) ре рам, образующим дерево в данном графе, то -Оно не содержит ни одного простого цикла исследуемого графа. В этом случае сочетание , выданное -блоком перебора сочетаний, не обеспечивает наличия всех сигналов на любом изэлементов И 3. Следовательно, на выходах всех элементов И 3 и на выходе элемента ИЛИ 4 отсутствуют сигналы тогда на выходе инвертора. 5 имеется сигнал который подается на вход вентиля 2. Когда задержанный тактовый сигнал с линии за- ержки 9 поступаетна другой вход вентиля 2, о он проходит на вход счетчика 6 числа еревьев, увеличивая его показания на еди- ииу, и через ключи 7 - на выходы тех счетиков 8 участия ребер в образовании деревьев, оторью соответствуют набору ребер, обраующих данное дерево (показания этих счетиков увеличиваются на единицу). Для определеия числа деревьев графа и числа деревьев, бразованных с; участием каждого ребра, необходимо перебрать все сочетания из fn по (ft -l). После того, как блок 1 перебора сочетаний перебрал все возможные сочетания, на выходе 12 появляется сигнал, который говорит об окончании испытания. Счетчик 6 числа деревьев графа показывает число сочетаний, которые не содержат простых циклов исследуемого графа, т.е. число деревьев графа. Счетчики 8 участия ребер в образовании деревьев показывает число деревьев графа, образованных с участием соответствующего ребра. Повышение быстродействия устройства достигается за счёт сокращения числа рабочих тактов для анализа каждого сочетания ребер, а также за счет исключения затрат времени на определение электрическойпррводимости между условными вершинами модели графа в известном устройстве. Предмет изобретения Устройство для определения числа деревьев графа, содержащее блок перебора сочетаний, элементы И по количеству простых циклов графа, число ребер которых меньше числа вершин этого графа, элемент ИЛИ, инвертор, счетчик числа деревьев, клк)чи, линию задержки, вентиль, счетчики участия ребер в образовании деревьев, первые входы которых, первые входы блока перебора сочетаний и . счетчика числа деревьев соединены с установочным входом устройства, а вторые входы счетчиков участия ребер в образовании . деревьев соединены с выходами ключей, о т- личающееся тем, что, с целью повышения быстродействия, в нем выходы блока перебора сочетаний соединены с первыми входами соответствующих ключей и в соответствии со структурой графа - с вхо, дами элементов И, выходы которых через элемент ИЛИ и инвертор соединены с одним входом вентиля, выход котррого соединен со вторым входом счетчика числа деревьев и со вторыми входами ключей, а другой вход вентиля через линию задержки соединен с синхронизирующим входом устройства и вторым входом блока перебора сочетаний, индикационный выход которого соединен с выходом устройства.

10

12