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

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

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

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

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

сбОтветствующего счетчика группы, выход

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

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

Устройство содержит элемент 1 И мрдели дерева, триггеры 2 вершин, элементы 3. - 3 ( ИЛИ столбцов, элементы 4 - 4,И, триггеры 5 -З ребер, элементы 6 - И группы, первый распределитель 7, триггер 8 фиксации деревьев, счетчик 8 степени вершины, дешифратор 10, второй распределитель 11, группу счетчиков 12 -12ц, блок 0 13 перебора сочетаний, входы 14, 15, 16 и 17 устройства.

Типология графа задается отпиранием N каналов в блоке перебора сочетаний, соответствующих Vl ребрам графа. Путем 5 образования сигналов в N- 1 канале из N блок перебора сочетаний генерирует множество состояний графа, содержащего Ь1 вершин и N-1 ребер, идя каждого состояния в работе устройства можно вы0 делить два этапа На первом этапе проверяется условие образования дерева, пу тем проверки связности всех вершин графа при различных сочетаниях из N ребер графа по Н-1 ребер. Связный 5 граф, содержащий вершин и N -1 ребер, является деревом. На втором этапе определяется распределение степеней вершин в дереве. Степень вершины характеризует число ребер инцидентныхей.

0 - „

Работу устройства рассматривают

потактам.

В такте i; на. вход 14 устройства поступает сигнал, который устанавлива- , j ют триггеры 5.. - 5,;,, 2 - 2{, 8 в нулевое состояние и стирает содержимое счетчиков 9, 12. - такте t - поступает сигнал на вход

15устройства. При этом триггер 2, переходит в состояние 1, подает сигнал на первый вход элемента 6 И, а

в N - 1 канале блока перебора сочетаний появляются сигналы, которые, поступая на единичные входы соответствующих , триггеров 5. - S-1N f переводят их в состояние I.

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

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

C входы которых поступает сигнал с единичных выходов триггеров 5 - .

С выходов сработавших элементов 4.J - 4. j И сигналы поступают через элементы 3 - ИЛИ на единичные входы триггеров 2 - 2jyj, устанавливая их. в состояние 1. Номера триггеров, перешедших в состояние 1, соответст- вуют номерам вершин, связанных с первой вершиной и отстоящих от нее на .рас стоянии . Сигналы с единичных выхо дов триггеров 2 -2 поступают на первые входы элементов 6 - 6 И. В такте 4 сигнал с выходов распре делителя 7 проходит через элементы 6.6 И группы на вторые входы эле- ментов 4 - 4,j И.тех строк, которые соответствуют вершинам, отстоящим от первой на расстоянии d 1. Срабатывают те элементы 4 И, которые соответствуют ребрам, инцидентным этим вершинам. С выходов сработавших элементов 4 И сигналы поступают через элементы 3 ИЛИ на единичные входы триггеров 2j - 2 f вершин, устанавливая в состояние 1 те триггеры, кото рые соответствуют вершинаКг, отстоящим от первой на расстоянии d 2. В последующих тактах работы ,распре делителя определяются вершины, отстоящие от первой на расстоянии с1 3 4... Ы-1. Обгцее число вершин, связанных с первой, запоминается триггерами Если N - 1 ребер и М вершин не составляют дерево, то после тактов работы распределителя происходит его останов. Устройство переходит к работе на таКте t . Далее проверяется условие образо-. вания дерева при другой комбинации сигналов на выходах блока 13 перебора сочетаний. Если N-1 ребер и N вершин образуют дерево, то все триггеры 2 Обознача- навливаются в состояние ют данный такт через Ь-),. Срабатывает элемент 1 И, с выхода которого посту- пает сигнал на единичный вход триггера 8. Триггер 8 устанавливается в состояние I. Устройство переходит к второму этапу работы. При этом с единичного выхода триггера 8 сигнал пос тупает на вход управления счетчика 9 и угфавляю- щий вход распределителя 7. Счетные входы счетчика 9 отпираются. Распределитель 7 переходит к работе в режиме проверки степеней вершин дерева, - .В такте t| проверяется степень пер вой вершины. В этом такте с первого выхода распределителя 7 подается саг нал через элемент 6 И, на вторые входы элементов 4, - 4 И первой строки. Срабатывают элементы 4 И, соот- J4 уставетствующие инцидентным ребрам первой Вершины. Сигналы с выходов этих элементов через соответствующие элементы 3 - поступают на счетные входы счетчика 9. Счетчик 9 фиксирует степень первой вершины. Сигнал с соответствующих выходов счетчика 9 поступает на входы дешифратора Ю. С выхода дешифратора Ю, соответствующего значению степени вершины, сигнал поступает на вход распределителя 11. Распределитель 11 подключает вход счетчика 12 соответствующего значения степени вершины . к входу записи 17 устройства. Сигнал, поступающий на вход записи 17, подает- ся на вход выбранного счетчика 12 . В такте 2,проверяется степень второй веро1инь1. В этом такге сигнал подается со второго выхода распределителя 7. Через элемент .б И на вто рые входы элементов 4 И второй строки. Срабатывают элементы 4 И, соответствующие инцидентным ребрам второй . вершины. Дальнейшая работа аналогична работе в такте и т. д. В такте-fcj проверяется степень N -ной вершины . Номера счетчиков 12 j-12 j соответствуют значениям степеней вершин. Числа, фиксируемые счетчиками,, соответствуют числу вершин с данной степенью. Таким образом, номера счетчиков и их содержимое определяют распределение степеней вершин в данном дереве Далее устройство переходит к работе по тактам fe,-t2 - Р новой комбинации сигналов на выходах .блока 13 перебора сочетаний. Работа устройства заканчивается после выдачи всех возможных сочетаний блоком 13. Благодаря введению новых блоков и связей между ними устройство позволяет не только определит число деревьев в графе, но и получить распределение степешй вершин в деревьях, что повышает полноту и точность анализа. ормула нгобретения Устройство для определения числа деревьев графа, содержащее счетчик, группу элементов И, группу счетчиков и матричную модель графа, каждый уаел которой состой из элемента И и триггера ребра, единичный вход каждого триггера ребра соединен с соответствующим