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

ОП ИКАНИЕ ИЗОБРЕТЕН ИЯ(в 739550Союз Советскнн Соцкапистическнн Республик К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ(53) УДК 681.333. ,57(088, 8) ло делам наобретеннйк открытий Опубликовано 05,06.80. Бвллетень Я 21 Дата опубликования описания 08,06.80(54) УСТРОЙСТВО ДЛЯ ОПРЕДЕЛЕНИЯ ЧИСЛА ДЕРЕВЪЕВ ГРАФАИзобретение относится к вычислительной технике и может быть использованодля определения обще"о числа деревьев графа и распределения степеней вершин деревьев графа при исследовании надежности систем, отображаемых вероятност 5ными графами.Известно устройство для нахождения деревьев графа, содержащее блок индика-. ции, счетчики, диоды, переключатели, линию задержки, блоки коэффициентов пе ресчета, счетчики числа деревьев 11.Недостатки устройства - невозможность определения числа деревьев, образованных с участием каждого отдельно15го ребра графа, отсутствие возможностиопределения распределения степеней вершин в дереве.Наиболее близким техническим решекием к изобретению является устройстводля определения числа деревьев графа, содержащее счетчик, группу элементовИ, группу счетчиков и матричную модель графа, каждый узел которой состоит из 2элементов И и триггера ребра, единичный вход каждого триггера ребра соединен с соответствующим выходом блока перебора сочетаний, единичный выход каждого триггера ребра подключен к первому входу элемента И данного столбца, вторые входы элементов И каждой строки сое-динены с выходом соответствующего элемента И группы, первые входы элементов И группы подключены к выходам соответствующих триггеров вершин, входы элемента И модели дерева соединены с выходами триггеров вершин, единичный вход каждого из которых соединен с выходом соответствующего элемента ИЛИ столбца, входы которого подключены к выходам элементов И узлов матрицы соответствующего столбца 2. Недостатком устройства является отсутствие возможности определять распределения степеней вершин в дереве,Цель изобретения - расширение функциональных возможностей путем реализа3 739ции дополнительной функции определенияраспределения степеней вершин в дереве.Поставленная цель достигается тем,что в устройство для определения числадеревьев графа, содержащее счетчик,группу элементов И, группу счетчиков иематричную модель графа, каждый узелкоторой состоит из элемента И и тригге;:- ра ребра, единичный вход каждого трите,ра ребра соединен с соответствующим выходом блока перебора сочетаний, единичный выход каждого триггера ребра подключен к первому входу элемента И данного столбца, вторые входы алементовИ каждой строки соединены с выходомсоответствующего элемента И группы,первые входы алементов И групйы подкЛючены к выходам соответствующихтриггеров вершин, входы элемента Имодели дерева соединены с выходамитриггеров вершин, единичный вход каждого из которых соединен с выходомсоответствующего элемента ИЛИ столбца, входы которого подключены к выходам элементов И узлов матрицы соответствующего столбца, в него введеныпервый и второй распределители, дешиф.ратор и триггер фиксации деревьев, единичный выход которого соединен с управляющим входом первого распределителяи- с управляющим входом счетчика, каждый выходкоторого подключен к соответствующему входу дешифратора, каждыйвыход которого соединен с соответствующимвходом второго распределителя, каждый выход которого подключен к входу"-соответствующего счетчика группы, выходэлемента И дерева. соединен с единичнымвходом триггера фиксации деревьев, нулевой вход которого соединен с первымвходом устройства, с нулевыми входамитриггеров ребер, с нулевыми входамитриггеров вершин, с входами сброса счетчиков группы и с входом сброса счетчика,разрядные входы которого соединены свыходами элементов ИЛИ столбцов, единичный вход триггера первой вершины:подключен к входу блока перебора сочетаний и к второму входу устройства,третий вход которого соединен с входомпервого распределителя, каждый выходкоторого подключен к второмувходу.соответствующего элемента И группы, вход записи второго распределителя соединен с четвертым входомустройства.На чертеже представлена функциональная схема предлагаемого устройства. 5.5 О фУстройство содержит элемент 1 И мо-дели дерева, триггеры 2- 24 вершин,элементы 3 - ЗЛИЛИ столбцов, элементы 4- 404 И, триггеры 5-5 ребер,5элементы 61 - 64 И группы, первыйраспределитель 7,.триггер 8 фиксациидеревьев, счетчик 8 степени вершины,дешифратор 10 второй распределитель11, группу счетчиков 12 -12, блок10 13 перебора сочетаний, входы 14, 15,16 и 17 устройства.Типология графа задается отпираниемМ каналов в блоке перебора сочетаний,соответствующих М ребрам графа. Путем15 образования сигналов в М каналеиз Я блок перебора сочетаний генерируетмножество состояний графа, содержащегоЬ вершин и Мребер. Для каждогосостояния в работе устройства можно вы 20 делить два этапа На первом этапе проверяется условие образования дерева, путем проверки связности всех Щ вершинграфа при различных сочетаниях из Иребер графа по Мребер, Связныйграф, содержащийвершин и йребер, является деревом, На втором этапеопределяется распределение степеней вершин в дереве. Степень вершины характеризует число ребер инцидентных ей,30Работу устройства рассматриваютпотактам.В такте 1. на,вход 14 устройствапоступает сигнал, который устанавливаФ35ют триггеры 5 - 5 щ 21 - 2 мв нулевое состояние и стирает содержимое счетчиков 9, 12 12,В такте 1поступает сигнал на вход15 устройства. При атом триггер 2переходит. в состояние 1", подает сиг 40нал на первый вход алемента 64 И, ав Н - 1 канале блока перебора сочетанийпоявляются сигналы, которые, поступаяна единичные входы соответствующих45.триггеров 5 ф - 5 переводят ихсостояние ф 1,В такте 1 з поступает сигнал -на вход16 устройства, который включает в работу распределитель 7. При этом навсех выходах распределителя появляется50сигйал, который проходит только черезалемент 6 И, на вторые входы алементов 4, - 444 И первой строки, Срабатывают те элементы 4- 4 И, на первые .55входы которых постуйает сигнал с единичных выходов триггеров 5,И - 54.С выходов сработавших элементов4 - 4, И сигналы поступают через11элементй 3 - 34 ИЛИ на единичные0 6ветствующие инцидентным ребрам первой вершины.Сигналы с выходов этих элементов через соответствующие элементы 3ЗцИ поступают на счетные входы счет чика 9. Счетчик 9 фиксирует степень первой вершины. Сигнал с соответствующих выходов счетчика 9 поступает на входы дешифратора 10. С выхода дешифратора 10, соответствующего значению степени. вершины, сигнал поступает на вход распределителя 11, Распределитель 11 подключает вход счетчика 12 соот ветствующего значения степени вершины .к входу записи 17 устройства, Сигнал, поступающий на вход записи 17, подает-" ся на вход выбранного счетчика 2",В тактепроверяется степеньК+2 евторой вершины. В этом такте сигнал подается со второго выхода распреде лителя 7. Через элемент.6 И на вто рые входы элементов 4 И второй стро ки. Срабатывают элементы 4 И, соответ ствующие инцидентным ребрам второй вершины. Дальнейшая работа аналогична работе в такте + и т. д.В тактепроверяется степеньк+ИЙ -ной вершиныНомера счетчиков 12 -12соответ ствуют значениям степеней вершин. Числа, фиксируемые счетчиками, соответсФ вуют числу вершин с данной степенью. Таким образом, номера счетчиков и их содержимое определяют распределение степеней вершин в данном деревеДалее устройство переходит к работе по тактам., при новой комби нации сигналов на выходах блока 13 перебора сочетаний. Работа устройства заканчивается после выдачи всех возможных сочетаний блоком 13.Благодаря введению новых блоков исвязей между ними устройство позволяет не только определить число деревьевв графе, но и подучить распределениестепеней вершин в деревьях, что повышает полноту и точность анализа,5 73955 входы триггеров 21 - 2, устанавливая их в состояние "1". Номера триггеров, перешедших в состояние 1, соответст% вуют номерам вершин, связанных с пер- вой вершиной и отстоящих от нее на,расстоянии О =1, Сигналы с единичных выхо дов триггеров 21 -2 поступают на первые входы элементов 6 - 6 И.В такте Ф 4, сигнал с выходов распределителя 7 проходит через элементы 6 -6 И группы на вторые входы элементов 4- 4 И тех строк,.которые1соответствуют вершинам, отстоящим от первой на расстоянии д =1.Срабатывают те элементы 4 И, кото рые соответствуют ребрам, инпицентным этим вершинам, С выходов сработавших элементов 4 И сигналы поступают через элементы 3 ИЛИ на единичные входы триггеров 2 - 2 вершин, устанавли вая в состояние "1" те триггеры, которые соответствуют вершинам, отстоящим от первой на расстоянии Й =2.В последующих тактах работы, распре- целителя определяются вершины, отстоящие от первой на расстоянии Д дЗ, 4Й. Общее число вершин, связанных с первой, запоминается триггерами 2 - 2.Если й ребер и М вершин не гос ЗО тавляют дерево, та после тактов работы распределителя происходит его останов. Устройство переходит к работе на такте 1 . Далее проверяется условие образо-. вания дерева при другой комбинации сиг налов на выходах блока 1 3 перебора сочетаний.Если Мребер и М вершин образуют дерево, то все триггеры 2 - 2 устанавливаются в состояние "1 ". Обознача- ф ют данный такт через , Срабатывает элемент 1 И, с выхода которого посту -" пает сигнал на единичный вход триггера 8. Триггер 8 устанавливается в состояние ф 1". Устройство переходит к второму этапу работы. При этом с единичного выхода триггера 8 сигнал поступает на вход управления счетчика 9 и управляющий вход распределителя 7, Счетные входы счетчика 9 отпираются. Раснрэде о литель 7 переходит к работе в режиме проверки степеней вершин дерева. : В такте ,проверяется степень нер вой вершины. В этом такте с первого выхода распределителя 7 подается сиг нал через элемент 6 И, на вторые входы элементов 4,Н - 4 И первой строки, Срабатывают элементы 4 А 41 И, соот формула изобретения Устройство для определения числа деревьев графа, содержащее счетчик, группу элементов И, группу счетчиков и матричную модель графа, каждый узел которой состоит из элемента И и триггера ребра, единичный вход каждого триггера ребра соединен с соответствующим7 7 ЗОБ выходом блока перебора сочетаний, единичный выход каждого триггера ребра подключен к первому входу элемента И данйого столбца,вторые вхйй элемен- тов И каждой строки соединены с,выходом соответствующего элемента И группы, первые входы элементов И груйпы подключепы к выходам соответствующих триг. геров вершин, входы элемента И модели дерева соединены с выходами триггеров 10 вершин, единичный вход каждого из ко торыхсоединен с выходом соответствую щего элемента ИЛИ столбца, входы которого подключены к выходам элементов И узлов матрицы соответствующего столбце, 15 о т л и ч а ю щ е е с я тем, что, с Келью расширения функциональных возможностей за счет определения распределения степеней вершин в деревьях, в него введены первый и второй распределиели, дешифратор и триггер фиксаций деревьев, единичный выход которого соединей суправляющим входом первого распределителя и с управляющим входом счетчика, каждый выход которого подключен25 к соответствующему входу дешифратора, каждый выход которого соединен с соответетвующим входом второго распредели 50 8теля, каждый выход, которого подключен к входу соответствующего счетчика группы, выход элемента И дерева соединен с единичным входом триггера фиксации деревьев, нулевой вход, которого соединен с первым входом устройства, с нулевыми входами триггеров ребер, с нулевыми входами триггеров вершин, с входами сброса счетчиков группы и с входом сброса1 счетчика, разрядные входы которого соединены с выходами элементов ИЛИ столб-цов, единичный вход триггерапервой вершины подключен к входу блока перебора сочетаний ик второму входу устройства, третий вход которого соединен с входом первого распределителя, каждыйвыход которого подключен к .второму входу соответствующего элемента И группы, вход записи второго распределителя соединен с четвертым входом устройства.Источники информации, принятые во внимание при экспертизе1. Авторское свидетельство СССРМ 367939 ю кл. 6 06 б 7/48, 1970.2, Авторское свидетельство СССРМц 329538, кл. 6 067/48, 1970