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

Изобретение относится к области вычислительной техники и может быть использовано для определения характеристик разложения графа на деревья при исследовании надежности систем, отображаемых вероятностными графами. . . Известно устройство l для поиска прадеревьев направленного графа, содержащее ключевую матрицу, кольцевые коммутаторы, генератор тактовых импульсов, триггеры, схемы И, схемы задержки, блокирующую ячейку, инвертор. Это устройство позволяет сократить число тактовых импульсов, необходимых для поиска всех пра-. деревьев в направленном графе путем исключения частичных графов, в которых повторяются не связанные с корнем компоненты, содержащиеся в ранее рассмотренных частичных графах. Это устройство характеризуется сле дующими недостатками: отсутствие воз можности исследовать ненаправленный граф; отсутствие возможности определения числа деревьев, образованных с участием каждого отдельного ребра графа; отсутствие возможности управ.ления процессом образования деревьев ;отсутствие возможности определения характеристик разложения графа на деревья. Известно устройство для нахождения деревьев графа 2 , содержащее блок индикации, счетчики, диоды, переключатели, линию задержки, блоки коэффициентов пересчета, счетчики числа деревьев. Этому устройству присущи следукицие недостатки: отсутствие возможности определения числа деревьев, образованных с участием каждого отдельного ребра графа-, отсутствие возможности управления процессом образования деревьев} отсутствие возможности определения характеристик разложения .графа на деревья. Наиболее близким техническим решением к изобретению является устройство для определения числа деревьев L3,содержащее элемент И, входы которого подключены к выходам первого наборного поля, входы которого соединены с выходами ключей, выход элемента И подключен к счетному входу одного счетчика и к первым входам элементов И первой группы, выходы которых соединеныс счетными входами других счетчиков, выходы сброса счетчиков и нулевые входы триггеров ( N -1) групп подключены к входу с са Устройства, единичные входы три геров (N -1) групп соединены с вход записи устройства. Кроме того, уст ройство содержит блок перебора состояний. Недостатками прототипа являются отсутствие возможности управления процессом образования деревьев; отсутствие возможности определения ха рактеристик разложения графа на деревья. Характеристиками разложения графа на деревья являются числа подмножеств, в которых деревья имеют постоянными одно, два и т. д ребер. Цель изобретения - повышение точ ности исследования путем реализации дополнительной функции определения чисел подмножеств, в которых деревь имеют постоянными одно, два и т. д ребер, и представления возможности управления процессом образования де ревьев. Цель достигается тем, что в устройство, содержащее элемент И, входы которого подключены к вьгходам первого наборного поля, входы которого coeдиrfeны с выходами ключей, ход элемента И подключен к счетному входу одного счетчика и к первым вхЬдам элементов И первой груп пы, выходы которых соединены с сче ными входами других счетчиков, выходы сброса счетчиков и нулевые вхо ды триггеров .{н - 1) групп подключены к входу сброса устройства, единичные входы триггеров ( М - 1) групп соединены с входами записи устройства, введены элементы задерж ки, вторая группа элементов И, эле менты .запрета, второе и третье наборные поля и ( N -1) распределителей, входы первого распределителя соединены с единичными выходами тр геров первой группы, входы остальных распределителей подключены к выходам элементов запрета, первые входы которых соединены с единичными выходами триггеров остальных групп.- вторые входы элементов запр та подключены к выходам второго Наборного поля, выходы {N - 1) рас пределителей соединены с входами третьего наборного поля, выходы ко торого подключены к управляющим вх дам ключей, управляющий вход (. i -го распределителя соедийен с вход тактовых импульсов устройства и с одними входами элементов И второй группы, другие входы которых подключены к управляющим выходам соот ветствующих распределителей, выход первого элемента И второй группй соединен с выходом устройства, вых ды остальных элементов И второй группы подключены к управляющим входам соответствующих распредели телей и через элементы задержки к вторым входам соответствующих элементов И первой группы, вход считывания первого наборного поля соединен с входом опроса устройства,в.ходы второго наборного поля соединены с выходами первых N -2 распределителей. Функциональная схема устройства представлена на чертеже. Устройство содержит элемент И 1, первое наборное поле 2, ключи , (ребер), счетчики 4,, элементы И 5, 5 первой группы, триггеры б т CN,,. (ребер), элементы запрета / т /r,4-,N- / распределители 8 т БМ, второе наборное поле 9, элементы И 10 4- Юц- второй группы, третье наборное поле 11, элементы задержки 12 4- ,, , вход сброса 13, вход тактовых импульсов 14, вход опроса 15, выход импульсов останова 16,вход записи 17,В триггерах 6 , - номер вершины, j -номер ребра, инцидентного данной вершине. В работе устройства следует выделить два этапа,: этап задания структуры графа и этап исследования структуры графа. Рассмотрим этап задания структуры графа. Основой для задания графа в Устройстве является, граф, имеющий N вершин и М ребер, в- котором все элементы перенумерованы. Элементы устройства упорядочиваются в соответствии с принятой нумерацией,. Номера вершин присваиваются распределителям 8 и входам-, элемента И 1. Количество распределителей равноН -1, количество входов элемента И 1 равно Н . Номера ребер, ,инцидентных вершинам присваиваются входным и выходным цепям распределителей 8 Номера возрастают слева направо. На наборном поле 2 входы з лемента И 1 и ключи (ребер) 3, г 3 соединяются в топологическую схему графа. На наборном поле 11 выходы распределителей 8 и входы ключей 3, соответствующие одноименным ребрам графа, соединяются между собой. На наборном поле 9 выходы распределителей 8 и входы элементов запрета7, соответствующие одноименньгм ребрам, но инцидентные разным вершинам, соединяются feждy собой. При этом соблюдается правило: выход распределителя, соответствующего вершине с меньшим номером, должен быть соединен с ВХ.ОДОМ одноименного элемента запре-та соответствуюшёго вершине с большим номером. В дальнейшем на этапе исследования графа работа устройства протекает по тактам. В первом такте поступает сигнал по входу сброса 13 на нулевые входы триггеров 6 и стирающие входы счетчиков 4. Триггеры и счетчики устанавливаются в исходное состояние. Во втором такте в соответствии с матрицей инцидентности поступают си налы на единичные входы триггеров (ребер) 6, которые устанавливаются состояние 1, С единичных выходов триггеров б (ребер), инцидентных пе вой вершине, поступают сигналы на входы распределителя первой вершины С единичных выходов триггеров б (ребер), инцидентных остальным вершинам, сигналы поступают на входы соответствующих распределителей через элементы запрета 7. В каждом распределителе возбуждается один выход, соответствующий возбужденном входу с меньшим номером. Сигналц с выходов распределителей поступают через схему коммутаций наборного по ля 9 на входы соответствующих элементов запрета 7, а через схему ком мутаций наборного поля 11 на входы соответствующих ключей 3. При этом запрещаются сигналы на одноименных выходах распределителей, соответствующих вершинам со старшими номера ми. В результате в каждом распределителе будет возбужден только один выход, причем среди возбужденных вы ходов не будет одноименных. В.озбужденные выходы будут иметь меньшие номера из множества разрешенных номеров, При поступлении сигналов на управляющие входы ключей 3-образует электрический контакт между их полю сами. В третьем такте поступает сигнал на вход опроса 15, который через схему коммутаций наборного поля 2 поступает на. входы элемента И 1. Ес возбужденные выходы распределителей соответствуют ребрам, образующим дерево, то срабатывает элемент И 1 и с его выхода подается сигнал в по ледний счетчик 4. В четвертом такте поступает сигн на вход тактовых импульсов 14, кото |рьтй подается на управляющий вход по леднего распределителя 8 и входы эле ментов И 10. При этом.возбуждается очередной по номеру из разрешенных в ходов последнего распределителя 8. Дальнейшая работа устройства протекает путем чередования третьегои четвертого тактов до тех пор, пока не будет возбужден последний из разрешенных выходов последнего распределителя. Тогда-с управляющего выхода распределителя подается сигнал на разрешающий вход соответствую щего элемента И 10. Очередной сигнал поступающий на вход тактовых импульсов 14, проходит на входМ ; -го, а через элемент И 10 .на вхрд(Ц-7-го рас пределителей и на вход М 2 -го элемента задержки 12. Если выполняются условия образования дерева, то при поступлении сигнала на вход опро::а 15 сработает элемент И 1. В результате поступит сигнал на входы N -го и N -1 -го счетчиков. При этом возбуждаетсяочерёдной разрешенный выход в N-2-м распределителе и возбуждается младший из разрешенных (с учетом нового состояния N-2-го распределителя) выходов Ы -1 - го распределителя. Таким образом, перевод каждого расп.ределителя в новое состояние осуществляется при поступлении сигнала на вход 14, если распределители с высшими номерами находятся в последних из разрешенных состояний. Работа устройства завершается, если все распределители устанавливаются в последние из разрешенных состояний. Тогда при поступлении очередного сигнала на вход 14, срабатывают все элементы И 10. Сигналы с выходов элементов И 10 переводят распределители в исходное состояние, а сигнал с выхода первого элемента И 10 является сигналом останова работы устройства. Показание N -го счетчика 4 соответствует числу деревьев в графе. Показанием -1-го счетчика 4 соответствует числу подмножеств, в которых деревья имеют N-2 постоянных ребер. Показаниям -2-го счетчика соответствуют числу подмножеств в которых деревья имеют Н -3 постоянных ребер и т. д. Таким образом благодаря введению новых элементов и связей между ними повысилась точность и глубина исследования разложения графа на деревья. Устройство позволяет определить характеристики разложения графа на деревья. Показания счетчиков характерны для принятой нумерации вершин в графе. Следовательно, имеется возможность управлять процессом образования деревьев, так как с изменением этой нумерации изменяется последовательность образования деревьев. Кроме того, предлагаемое устройство позволяет работать с графами, у которых число вершин и ребер может быть переменным. Формула изобретения Устройство для разложения графа на деревья, содержащее элемент И, входы которого подключены к выходам первого наборного поля, входы которого соединены с выходами ключей, выход элемента И подключен к счетному входу одного счетчика и к первым входам элементов И первой группы, выходы которых соединены со счетными входами других счетчиков, выходы feriTT-n,---L .r°-.. соединены с входами записи устройства, отличающееся ТРМ что, с целью повышения точности в него введены элементы зШДержкй з1поет/ ° И,элементы nonnl ( и третье на€орШё распределителей, входы первого распределителя соединены с единичными выходами триггеро первой группы, входы остальных рйспо JSsSoLr динент °Д которых со динены с единичными выходами триггеэл ентп °Р °ДЬ1 ходам «тп Р подключены к выходам второго наборного поля, выходы входами Р Р далителей соединены с входами третьего наборного поля, выходы которого подключены к управляющим входам ключей, управляющий вход N -1}-го распределителя соединен с входом тактовых импульсов. ySSpoft8ства и с одними входами элементов И второй группы, другие входы которых подключены к управляющим выходам соответствующих распределителей, выход первого элемента и второй группы соединен с выходом устройства, выходы остальных элементов и второй группы подключены к управляющим входам соответствующих распределителей и через элементы задержки к вторым входам соответствующих элементов и первой группы, вход считывания первого на-борного поля соединен с входом опроса устройства, .входы второго наяыГы°/° соединены с выходами первых Н -2 распределителей. Источники информации, принятые во внимание при экспертизе № свидетельство СССР № 271906, кл. G 06 G 7/48, 1969 № свидетельство СССР № 364939, кл. G 06 G 7/48 1971 OQ,. свидетельство СССР 329538, кл. G Об G 7/48, 1970 прототип).

/7 17 17 Г7 17 7 17 П

I. I, . 1-..

1}