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

ОП ИСАНИ ИЗОБРЕТЕН И К АВТОРСКОМУ СВИДЕТЕЛЬСТ 1922781 Союз СоветскихСоциалистическихРеспублик вид-ву М 7 ополнительное к авт 22)Заявлено 01.11,78 (2 2680041/ 3 Ьеударетеенный каинт 066 7/122 с присоединением заявк 3)Приорит СССР ао делан изобретенийОпубликовано 2 З,2. Бюл 3) УДК 681. ,ЗЗЗ(088.8) . открытий ата опубликования нсання 2ЛЯ РАЗЛОЖЕНИЯДЕРЕВЬЯ 1Изобретение относится к вычислитель- ной технике и может быть использовано для определения характеристик разложения графа на деревья при исследовании надеж ности систем, отображаемых вероятностными графами.По основному авторскому свидетельству %.748428 известно устройство, содержащее элемент И, входы которого подключены к выходам первого наборного поля, входы которого соединены с выходами ключей, выход элемента И подключен к счетному входу одного счетчика и к первым входам элементов И первой группы, выходы которых соединены со счетными входами других счетчиков, выхошасброса счетчиков и нулевые входы триггеров (И)-группы подключены к входу сброса устройства, единичные входы триггеров (М)-групп соединены:.с входами записи устройства, элементы задержки, вторая группа элементов И, элементы запрета, второе и третье наборные поля и (М) распределителей, входы первого распределителя соединены с единичными выходами триггеров первой группы, входы остальных распределителей подключены к выходам элементов запрета, первые входы которых соединены с единич. ными выходами триггеров остальных групвторые входы элементов запрета подключены к выходам второго наборного поля, выходы (М) распределителей соединены 10с входами третьего наборного поля:, выходы которого подключены к управляющим входам ключей, управляющий вход (й)-г распределителя соединен с входом тактовых импульсов устройства и с одними 15входами элементов И второй группы, другие входы которых подключены к управляющим выходам соответствующих распределителей, выход первого элемента И второй группы соединен с выходом устройства, выходы остальных элементов И второй группы подключены к управляющим входам соответствующих распределителей и через элементы задержки к вторым входам соответствующих элементов И пер5гдэ й - номер ребер графа;б; - столбцы, содержащие номераребер, образующие деревья графа.Этап задания структуры графа полностью аналогичен этому этапу в извес ном устройстве.В дальнейшем, на этапе исследованграфа, работа устройства протекает по тактам.В такте 1 поступает сигнал к входу13 сброса и на нулевые входы триггеро 6 и стирающие входы счетчиков 4. Три е геры и счетчики устанавливаются в исходное состояние.В такте Й в соответствии с,матрицеинцидентности поступают сигналы на единичные входы триггеров 6 ребер, которые устанавливаются в состояние ф С единичных выходов триггеров 6 ребер. инцидентных первой вершине, поступаютсигналы на входы распределителя перво вершины. С единичных выходов трцггеро 6 ребер, инцидентным остальным верши нам, сигналы поступают нв входы соответствующих распределителей через эле менты 7 запрета. В каждом распредели теле возбуждается адин выход, соответ ствующий возбужденному входу с мень- шим номером, Сигналы с выходов расделителей поступают, через схему коммутаций наборного поля 9 на входы соответствующих элементов 7 запрета, а че рез схему коммутаций наборного поля 1 на входы соответствующих ключей ЗП этом запрещаются сигналы на одноимен ных выходах распределителей, соответст вующих вершинам со старшими. номерам В результате в каждом распределителе возбужден только один выход, причем среди возбужденных выходов нет одноименных, Возбужденные выходы имеют меньшие номера из множества разрешен ных номеров.При поступлении сигналов на управляющие входы ключей 3 образуется электрический контакт между их полюсами.4 ЬВ контакте 6 поступает сигнал на вх15 опроса, который через схему комму таций наборного поля 2 поступает.на вх дыэлемента И 1 и на соответствующие входы блока 18. С каждого выхода блок закодированный сигнал поступает на вхо регистра 19. Т.е, в соответствующие разряды регистра записывается цифровой код сигнала, поступающего на аналогичные входы элемента И 1, Если возбужденные выходы распределителей соответ- т ют ребрам, образующим деревото 40 922781 6срабатывает элемент И 1 и с его выхода подается сигнал в последний счетчик4 и на разрешающий вход распределителя,который преобразует последовательностьцифровых кодов регистра 19 в параллельт- ные коды по разрядам и запись этих кодов в регистры 211-21т,е. в регистия рах 21-21 записан код первого дереваграфа.В такте Ь поступает. сигнал на вход14: тактовых импульсов, который подается на управляющий вход последнего раог- пределителя 8, нв входы элементов И 10,на стирающий вход приемного регистра15 19 и на второй вход элемента И 22. Прий этом возбуждается очередной по номеруиз разрешенных выходов последнего рас-пределителя 8,1 ф,Если комбинация ребер не соответству-,20 ет дереву, то с выхода элемента И 1 непоступает сигнал нв раэрешающйй входй распределителя 20 и эта комбинацияв ребер не заносится в регистры 21 -21 .Если комбинация ребер соответствует де 25 реву, тораспределительпроиэводитсоответствующую комбинацию цепей и комбинацияребер записывается в регистры 21-21.,При этом распределитель выдает сигналнв первый вход элемента И 22. С припре- З 0 ходом тактового импульса на вход 14он поступает на вход стирания регистра19 (стирает предыдущую комбинациюребер и готовит приемный регистр к но 1 вой записи информации), на второй входри З 5 элемента И 22, который при наличиисигнала на правом входе с.выходв выдает сигнал сдвнга информации в регисъи, рвх 21.,-23., в сторону старшего разряда.Дальнейшая работа устройства протекает путем, чередования тактов 1 Г и ядо тех пор, пока не будет возбужденпоследний из разрешенных выходов последнего распределителя, Иногда с управляющего выхода распределителя подаетсясигнал на разрешающий вход соответствующего элемента И 10. Очередной сигод нал, поступающий на вход 14 тактовыхимпульсов, пройдет на вход (К)-го, во- через элемент И 10 - на вход (й-)-го50распределителей, а также на вход (Й)-гоа элемента 12 задержки, Если выполняютсяд условия образования дерева, то при поо",туплении сигнала нв вход 15 опроса сра 55батывает элемент И 1, В результатепоступает сигнал на входы Н -го и(Й)-го счетчиков. При этом возбуждается очередной разрешенный выход в7. 92младший из разрешенных (с учетом нового состояния (К) "го распределителя)выходов (М) го распределителя. Таким образом, перевод каждого распределителя в новое состояние осуществляеься прн поступлении сигнала на вход 14,если распределители с высшими номерамн (но не все) находятся в последнихиз разрешенных состояний.Работа устройства завершается, эслввсе распределители устанавливаются впоследние нз разрешенных состояний.Тогда прн поступлении очередного сигна. ла на вход 14 срабатывают все элеменйю 1 О Сигналы с выходов элементов И3.0 переводят распределители в исходноесостояние, а сигнал с выхода первогоэлемента И. 10 является сигналом останова работы:усчройства. Показание М -госчвтчнка 4 соответствует чисйу деревьевв графе. Показание (М)-го счетчика 4соответствует числу подмножеств, в которых деревья Имеют (й) постоянныхребер. Показания (М) счетчика сооь-ветству 1 от числу подмножеств, в которыхдеревья имеют (й) постоянных реберн т,д,По сравнению с известным устройсввьм изобретение обоеспечнвает болеевысокую точносаь определения характеристики графа 2781 8формула изобре тенияУстройство дпя разложения графа надеревья по авт. св, М 748428, о т л ич а ю щ е е с я тем, что, с цвлью повышения точности, в него введены допол.ннжльные регксзры, распределитель иэлемент И, сдвигающие регистры и блокшифраторов, входы которого подключенысоответственно к выходам первого набор 1 е ного поля, выходы блока шифраторов подключены соответственно ковходам дополнительного регистра, управляющийвход которого соединен с первым входомдополнительного элемента И н.является1% входом тактовых импульсов устройства,вцходы дополнительного регистра соединены со входамн дополнительного распрещщнтеля, управляющий вход которогоподключен:к выходу элемента И, выход дой полнительного распределителя соединен совторым входом дополнительного элемента И,выход которого подключен к сдвигаюшим.входвмсдвнгающихрегистров, информационныевходы которых соединены соответственнос выходами дополнительного распределителя,Источники информации, .принятые во внимание при экспертизе1. Авторское свидетельство СССР% 748428, кл. Я 0657/122, 1978022781 и 3 Филиал ППП "Патент", г, Ужгород, ул, Проектная, 1 Редактор Л. ЛукачЮ ейейвьеЗаказ 2584/66ВНИИ Составитель И. ЗагорбТехред И. Гайду КорТираж 732 ПодиПИ Государственного коделам изобретений и о35, Москва, Ж 35, Ра ининаректор С. Шекмарсноемитета СССРткрытийушская нвб., д. 4/5