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

 

% 56@3 Совете 1их

Соцналмстнчаскин Респ онии

И . .. (3 Б Р Е Т Е Й И Я

H АВТОРСКОМУ СВИДИИЛЬСУВУ (61) Дополнительное к авт. саид-ву(22) Заявлено 08 01.73(21)1870365/18 24 с присоединением заявки № (51) М. Кл.

О 06 . 15/20

Гасударстеенный номнтет бенета Мнннетрое ССОР пе делам нзобретеннй н атнрь тнй (43) Опубликовано 25,08.75Бюллетень ¹ 35 (53) уды

681, 326 (088.8) ;.") Й т G óáë11êoâàêHH описания 3g 01 7-6,. (72) Автору изобретения

H. H,, Епихин (71) Заявитель (54) С.г.с т- ВО ДЧя ОГРЬДЕт1ЕИИЧ -ИС1л, ДЕРЕВЬЕВ ГРАФА

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

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

Достигается это благодаря тому, что в устройстве выходы блока перебора сочетаний соединены с первыми входами l 25 соответствующих ключей и в соответствии со стру-ктурой графа - с входами эпементов И, выходы которых через элемент

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

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

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

Работа устройства происходит следующим образом. 11ервоначапьно у исспеду-

485452

4 держки 9 поступает на другой вход вентиля 2, то он проходит на вход счетчика 6 числа деревьев, увеличивая его показания на единицу, и через ключи 7 - на выходы тех счетчиков 8 участия ребер в образовании деревьев, которые соответствуют набору ребер, образуюших данное дерево (показания этих счетчиков увеличиваются на единицу). Для определения числа деревьев графа и числа деревьев, образованных с:участием каждого ребра, необходимо перебрать все сочетания из П по (Ф -1). После того, как блок 1 перебора сочетаний перебрал все возможные сочетания, на выходе 12 появляется сигнал, который говорит об окончании испытания. Счетчик 6 числа деревьев графа показывает число сочетаний, которые не содержат простых циклов исследуемого графа, т.е. число деревьев графа. Счетчики 8 участия ребер в образовании деревьев показывает число деревьев графа, образованных с участием со- . ответствуюшего ребра.

Повышение быстродействия устройства достигается за счет сокрашения числа рабочих тактов для анализа каждого сочетания ребер, а также за счет исключения затрат времени на определение электрическойпрово димости между "условными" вершинами модели графа в известном устройстве. емого графа определюотся все простые циклы с числом ребер не болееф-1, где 1,- число вершин графа. Блок 1 перебора сочетаний имеет Явыходов, где ffl- число ребер графа. Каждый выход соответствует определенному ребру исследуемого графа.

На входы элементов "И 3 подкпючаются выходы блока перебора сочетаний, которые соответствуют ребрам, образуюшим

O Ю

10 простой цикл. Каждый элемент И 3 соответствует определенному простому циклу графа и на ее входы подключены выходы блока, перебора сочетаний, которые соответствуют ребрам, образующим данный простой цикл, если число этих ребер не превышает вели15 чиный -1. После установки устройства импульсом по входу 10 в исходное состояние (счетчиков 8 участия ребер в образовании деревьев и счетчика 6 числа деревьев в нулевое положение, блока 1 перебора сочета20 ния в первое положение ), по синхронизуюшему входу 11 поступает серия тактовых импульсов на блок перебора сочетаний и на вход линии задержки 9. Блок перебора сочетаний ,25 по каждому приходяшему импульсу выдает по вБ ходам очередное сочетание изщэлементов по (Cl -1). Если очередное сочетание (П -1) ребер не является деревом графа, то оно содержит как минимум один

30 простой цикл, число ребер которого ее превышает (и-1). В этом случае при выдаче блоком перебора сочетаний этого сочетания на всех входах элементов И" 3, соответствуюшей простому циклу, входящему в это сочетание, имеются сигналы, Элемент "И" 3 срабатывает, и сигнал с ее выхода поступает на вход элемента "ИЛИ" 4, При одном и том же сочетании возможно, чт з сработает несколько элементов И 3. При появлении сиг- 40 нала на выходе любого из этих элементов появляется сигнал на выходе элемента "ИЛИ" 4, который через инвестор 5 не дает возможности импульсу с линии задержки 9(поступает в промеж :тке между двумя тактовыми им- 45 пульсами) пройти через вентиль 2 на входы ключей 7 и на входы счетчика 6 числа деревьев. Если сочетание, выданное блоком перебора сочетаний, соответствует (и-1) ребрам, образуюшим дерево в данном графе, то

-оно не содержит ни одного простого цикла исследуемого графа. В этом случае сочетание, выданное блоком перебора сочетаний, ие обеспечивает наличия всех сигналов на любом из элементов И 3. Следовательно, на выходах всех элементов "И" 3 и на выходе элемента "ИЛИ" 4 отсутствуютсигналы и тогда на выходе инвертора. 5 имеется сигнал, который подается на вход вентиля 2. Когда задержанный тактовый сигнал с линии за- б0

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

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

485452

Подписное

Предприятие «Патент», Москва, Г-59, Бережковская наб., 24

Заказ ) 3Я Изд. 14 0Я ТиРаж 679

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

Москва, 113035, Раушская наб., 4