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

 

OllHCАНКЕ

ИЗОБРЕТЕН Ия

< >739550

Союз Советски н

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

Республик

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (61) Дополнительное к авт, свил-ву— (22) Заявлено 30.01.78 (21) 2574607/18-24 (5! ) Я !(,л

G 06 Ci 7/122 с присоединением заявки ¹

Государственный комитет (26) П рнорнтет— (53) УДК681.333. .57(088.8) II0 делам наобретеннй к открытий

Опубликовано 05 06.80.Бюллетень ¹21

Дата опубликования описания 08,06.80 (72) Автор изобретения

В, Н. Червяцов (7! ) Заявитель (54) УСТРОЙСТВО ДЛЯ ОПРЕДЕЛЕНИЯ ЧИСЛА

ДЕРЕВЬЕВ ГРАФА

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

i деревьев графа, содержащее блок индика-. ции, счетчики, диоды, переключатели, линию задержки, блоки коэффициентов пе ресчета, счетчики числа деревьев (1}.

Недостатки устройства - невозмож

1 I (ность определения числа деревьев, образова нных с участием каждого отдельно

15 го ребра графа, отсутствие возможности определения распределения степеней вершин в дереве.

Наиболее близким техническим реше» кием к изобретению является устройство для определения числа деревьев графа, содержащее счетчик, группу элементов

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

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

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

Недостатком устройства является отсутствие возможности определять распределения степеней вершин в дереве.

Цель изобретения - расширение функциональных возможностей путем реализа5,50 4

Устройство содержит элемент 1 И модели дерева, триггеры 2 - 2 вершин, элементы 3 - 3 ДИЛИ столбцов, элементы 4„„- 4 ®И, триггеры 5.< -5 ребер, 5 элементы 61 — 6 И группы, первый распределитель 7,.триггер 8 фиксации деревьев, счетчик 9 степени вершины, дешифратор 10, второй распределитель

11, группу счетчиков 12 -12, блок щ 13 перебора сочетаний, входы 14, 15, 16 и 17 устройства.

Типология графа задается отпиранием

N каналов в блоке перебора сочетаний, соответствующих М ребрам графа. Путем

15 образования сигналов в N- 1 канале из N блок перебора сочетаний генерирует множество состояний графа, содержащего вершин и N-1 ребер. Нля каждого состояния в работе устройства можно выделить два этапа. На первом этапе проверяется условие образования дерева, путем проверки связности всех Щ вершин графа при различных сочетаниях из И ребер графа по N.-l ребер. Связный граф, содержащий Я вершин и \4-1 ребер, является деревом. На втором этапе определяется распределение степеней вершин в дереве. Степень вершины карактеризует число ребер инцидентных ей.

Работу устройства рассматривают по тактам. .В такте Ь на,вход 14 устройства поступает сигнал, который устанавливаФ

35 ют триггеры 5 - 5 щ, 2. - 2, 8 в нулевое состояние и стирает содержимое счетчиков 9, 12 12 .

В такте 4 g поступает сигнал на вход

15 устройства. При атом триггер 2 переходит. в состояние 1.", подает сиг40 нал на первый вход алемента 6 И, а в К - l канале блока перебора сочетаний появляются сигналы, которые, поступая на единичные вкоды соответствующих

45 триггеров 5 . - 5, переводят их в состояние l

В такте 1 поступает сигнал -на вход

16 устройства, который включает в работу распределитель 7. При этом на всех выходах распределителя появляется

50 сигйал, который проходит только через алемент 6 И, на вторые входы алементов 4, - 4 И первой строки. Срабаты-. вают те элементы 4„„- 4 И, на первые .

55 входы которых постуйает сигнал с единич» ных выходов триггеров 5+ - 548

С выходов сработавших элементов

4 — 4. И сигналы поступают через

14 элементй 3 - 3 ИЛИ на единичные

3 739 ции дополнительной функции определения распределения степеней вершин в дереве.

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

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

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

На чертеже представлена функциональная схема предлагаемого устройства.

О 6 ветствующие инцидентным ребрам первой вершины.

Сигналы с выходов этих элементов через соответствующие элементы 3

З цИ поступайл на счетные входы счет чика 9. Счетчик 9 фиксирует степень первой вершины. Сигнал с соответствующих выходов счетчика 9 поступает на входы дешифратора 10. С выхода дешифратора 10, соответствующего значению степени. вершины, сигнал поступает на вход распределителя 11. Распределитель

11 подключает sron счетчика 12< соот ветствующего значения степени вершины . к входу записи 17 устройства. Сигнал, поступающий на вход записи 17, подает-" ся на вход выбранного счетчика 2„" .

В такте $ проверяется степень ю, + 2. второй вершины. В этом такте сигнал подается со второго выхода распреде лителя 7. Через элемент.6 И на вто» рые входы элементов 4 И второй стро» ки. Срабатывают элементы 4 И, соответ ствующие инцидентным ребрам второй вершины. Дальнейщая работа аналогична работе в такте + и т. д.

В такте $ проверяется степень к+й

Я -ной вершины, Номера счетчиков 12 -12 соответ ствуют значениям степеней вершин. Чис ла, фиксируемые счетчиками, соответст вуют числу вершин с данной степенью.

Таким образом, номера счетчиков и их содержимое определяют распределение степеней вершин в данном дереве

Далее устройство переходит к работе по тактам .. при новой комби нации сигналов на выходах блока 13 перебора сочетаний. Работа устройства заканчивается после выдачи всех воз можных сочетаний блоком 13.

Благодаря введению новых блоков и связей между ними устройство позволя

: ет не только определить число деревьев в графе, но и получить распределение степеней вершин в деревьях, что повы шает полноту и точность анализа, .73955 входы триггеров 21 - 2, устанавливая их в состояние 1". Номера триггеров, перешедших в состояние 1, соответст% вуют номерам вершин, связанных с пер- вой вершиной и отстоящих or нее на,расстоянии Q =1. Сигналы с единичных выхо дов триггеров 21 -2мпоступают на первые входы элементов 6 - 6 И.

В такте tg сигнал с выходов распределителя 7 проходит через элементы

6 -6 И группы на вторые входы элементов 4 - 4N> И тех строк,.которые 1 соответствуют вершинам, отстоящим от первой на расстоянии д =1.

Срабатывают те элементы 4 И, которые соответствуют ребрам, инцидентным этим вершинам. С выходов сработавших элементов 4 И сигналы поступают через элементы 3 ИЛИ на единичные входы триггеров 2. - 2 „ вершин, устанавливая в состояние "1" те триггеры, которые соответствуют вершинам, отстоящим от первой на расстоянии Й =2.

В последующих тактах работы, распределителя определяются вершины, отстоящие от первой на расстоянии Д =3, 4...

Я-1. Общее число вершин, связанных с первой, запоминается триггерами

2 .- 2 .

Если Я - 1 ребер и М вершин не составляют дерево, то после тактов работы распределителя происходит его останов.

Устройство переходит к работе на такте

1 . Далее проверяется условие образо-. вания дерева при другой комбинации сиг- 35 налов на выходах блока 1 3 перебора сочетаний.

Если N-1 ребер и К вершин образуют дерево, то все триггеры 2 1 - 2> устанавливаются в состояние 1". Обозначают данный такт через - . Срабатывает элемент 1 И, с выхода которого посту пает сигнал на единичный вход триггера

8. Триггер 8 устанавливается в состояние "1". Устройство переходит к второ» му этапу работы. При этом с единичного выхода триггера 8 сигнал поступает на вход управления счетчика 9 и управляющий вход распределителя 7. Счетные входы счетчика 9 отпираются. Расцрэде» литель 7 переходит к работе в режиме проверки степеней вершин дерева.

= -.В такте, < проверяется степень пер вой вершины. В этом такте с первого выхода распределителя 7 подается сиг нал через элемент 6 И, на вторые входы элементов 4. - 4 И первой строки.

Срабатывают элементы 4 41 И, соот

Формула изобретения

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

7 7395 выходом блока перебора сочетаний, единичный выход каждого триггера ребра подключен к первому входу элемента И данйого столбца," вторые вхй и элементов И каждой строки соединены с,выходом соответствующего элемента И группы, первые входы элементов И груйпы подключепы к выходам соответствующих триггеров вершин, входы элемента И модели

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

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

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

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

J записи второго-распределителя соединен с четвертым входом устройства.

Источники информации, принятые во внимание при экспертизе

1. Авторское свидетельство СССР

N. 367939, кл. 5 06 G 7/48, 1970.

2. Авторское свидетельство СССР

М 329538, кл. G 06 7/48, 1970 (прототип).

ЦНИИПИ Заказ 3048/8

Тираж 751 Подписное

Филиал ППП "Патент, r. Ужгород, yir. Проектная,4