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

(54) УСТРОЙСТВО ДЛЯ РАЗЛОЖЕНИЯ ГРАФА НА /ШРЕВЬЯ

..-

Изобретение относнтся к вычиспнтельД ной технике и может быть использовано для определения характеристик разложения графа на деревья при исследовании надежности систем, отображаемых вероятностными графами.

По основному авторскому свидетельству № .748428 известно устройство, содержащее элемент И, входы которого подключены к выходам первого наборного поля, входы которого с.оединены с выходами ключей, выход элемента И подключен к счетному входу одного счетчика Н к первым входам элементов И первой группы, выходы которых соединены со счетными входами других счетчикрв, выходысброса счетчиков и нулевые 15ходьь триггеров (N-1)-группы подключены к входу сброса устройства, единичные входы триггеров (N-l)-Tpynn соединены:.с входами записи устройства, элементы задержки, вторая группа элементов И, элементы запрета, второе и третье наборные поля и (N-l) распределителей, входы первого распределителя соединены с единичными выходами триггеров первой группы, входы остальных распределителей подклк чены-к выходам элементов запрета, первые входы которых соединены с единичными выходами триггеров остальных групп, вторые входы элементов запрета подключены к вькодам второго наборного поля, выходы (N-i) распределителей соединены с входами третьего наборного поля вы10ходы которого подключены к управляющим входам ключей, управляющий вход (N-l)-ro распределителя соединен с входом тактовых импульсов устройства и с одними входами элементов И второй группы, друtsгие входы которых подключены к управляющим выходам соответствующих распределителей, выход первого элемента И второй группы соединен с выходом устройства, выходы остальных элементов И

20 второй группы подключены к управляющим входам соответствующих распределителей и через элементы задержки к вторым входам соответствующих элементов И первой группы, вход считывания первого наборного поля соединен с входом опроса устройства, входы второго наборного поля соединены с выходами первых (N-2) распределителей.

К недостатку известного устройства следует отнести низкую точность определения характеристики разложения графа на деревья.

Целью изобретения является повышение точности.

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

На чертеже представлено устройство.

Устройство содержит элемент И 1, наборное прле 2, ключи 3,j-3| ребер, счетчики , элементы И . первой группы, триггеры , ребер, элементы Jr - запрета, распределители 8-i -Sfj-i, наборное попе 9, элементъ И lO/i -10 f. второй группы наборное поле 11, элементы 12(i--12j, задержки, вход 13 импульсов сброса, вход 14 тактовых импульсов, вход 15 импульсов опроса, выход 16 импульсов останова, вход 17 импульсов стираная информации, блок 18 шифратора, дополнительные регистр 10 и распределитель 20, сдвигающие регистры 21л-21 и дополнительный элемент Vi 22,

Входы элемента И 1 подключены к зькодам наборного поля 2, входы котогрого подключены к полюсам ключей 3(3ц ребер, а выход подключен к входу последнего счетчика 4 , к размыкающему входу распределителя 2О и к первым вхо дам элементов И 5 j--5j ;, выходы которых подсоединены к входам остальных

счетчиков 4(j-4jj. Единичные входы триггеров 6 6щ. ребер подсоединены к входам записи.

Входы первого распределителя 8 подсоединены к единичньгм выходам соответи ствующих триггеров 6. Входы остальных распределителей 8 подсоединены к выходам элементов 7 запрета, первые входы которых подсоединены к единичным иыходам соответствующих триггеров 6, а вторые входы подсоединены к выходам наборного поля 9, входы которого noftсоединены к рабочим выходам распреде лителей 8 и к входам набфного поля

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

входы которых соединены с входом тактовых импульсов 14, а выходы подсоединены к управляющему входу предькдущего распределителя 8 И к входу элемента

12задержки, выход которого подсоединен к второму соответствующего

элемента И 5. Входы блока 18 шифраторов подсоединены к выходам наборного поля 2, а выходы кажАояпо шифратора в &1оке 18 ши(}ратора позсоединены к со.

ответствующему ра:зряду регистра 19, выходы которого подсоединены к входу распределителя 2О. Выходы распределителя 20 подключены к входам записи регистров 21,,-21|у|,, а управляющий

выход распределителя соединен с первым входом элемента И 22, второй вход которого соединен с входом 14 тактовых импульсов, а выход подключен к входам импульсов сдвига регистров 21,21..

Нулевые входы триггеров 6 и входы стирания счетчиков 4 соединены с входом

13сброса. Вход опроса наборного поля

2 соединен с входом 15 импульсов опроса; Вход стирания регистров соединен с входом 17 стирания. Выход первого элемента И 10 соединен с выходом 16 останова.

В работе устройства следует выделить Два этапа: этап задания структуры- графа и этап исследования структуры графа.

Под структурным числом графа понимается таблица вида

.

,

... ct

sd

1)®а

где i;jj - номер ребер графа; d; - столбцу содержащие нетлера ребер, образукзшие деревья графа. Этап задания структуры графа полностью аналогичен этомуэтапу в известном устройстве. В дальнейшем, на этапе исследования графа, работа устройства протекает по тактам. В такте I поступает сигнал к входу 13 сброса и на нулевые входы триггеров 6 и стирающие входы счетчиков 4. Триггеры и счетчики устанавливаются в сходное состояние. В такте Ti в соответствии с .матрицей инцидентности поступают сигналы на единичные входы .триггеров 6 ребер, которые устанавливаются в состояние 1 С единичных выходов триггеров 6 ребер, инцидентных первой вершине, поступают сигналы на входы распределителя первой вершины. С единичных выходов триггеров 6 ребер, инцидентным остальным вершинам, сигналы поступают на входы соответствующих распределителей через элементы 7 запрета. В каждом распределителе возбуждается один выход, соответствующий возбужденному входу с менйшим номером. Сигналы с выходов распре делителей поступают.через схему коммутаций наборного поля 9 на входы соответствующих элементов 7 запрета, а через схему коммутаций наборного поля 11 на входы соответствующих ключей 3. .При этом запрещаются сигналы на одноименных, выходах распределителей, соответствующих вершинам со старшими. номерами. В результате в каждом распределителе возбужден только один выход, причем среди возбужденных выходов нет одаоименных. Возбужденные выходы имеют меньшие номера из множества разрешенных номеров. При поступлении сигналов на управляющве входы ключей 3 образуется электрический контакт между их полюсами. В контакте Ш поступает сигнал на вхо 15 опроса, который через схему коммутаций набфного поля 2 поступает, на вхо ДЬ1 элемента И 1 и на соответствующие входы блока 18. С каждого выхода блока закодированный сигнал поступает на вход регистра 19. Т.е. в соответствующие разряды регистра записьшается цифровой код сигнала, поступающего на аналогичные входы элемента И 1. Если возбужденные выходы распределителей соответ- T-yjoT ребрам, образующим дерево, то 9 16 срабатывает элемент И 1 и с его выхо- да подается сигнал в последний счетчик 4 и на разрешающий вход распределителя, который преобразует последовательность цифровых кодов регистра 19 в параллельные коды по разрядам и запись этих кодов в регистры ..-, т.е. в регистрах 21 -21 записан код первого дерева графа. В такте W поступает сигнал на вход 14. тактовых импульсов, который подается на управляющий вход последнего рас- пределителя 8, на входы элементов И 10, на стирающий вход приемного регистра 19 и на второй вход элемента И 22, При этом возбуждается очередной по номеру из разрешенных выходов последнего рас,пределителя 8, Если комбинация- ребер не соответству-, ет дереву, то с выхода элемента И 1 не поступает сигнал на разрешающий вход распределителя 20 и эта комбинация ребер не заносится в регистры .. Если комбинация ребер соответствует дереву, то распределитель производит соотве1 ствуютцую ксмлбинацию цепей и комбинация ребер записывается в регистры . При этом распределитель вьшает сигнал на первый вход элемента И 22. С прИходом тактового импульса на вход 14 он поступает на вход стирания регистра 19 (стирает предыдущую комбинацию ребер и готовит приемньй регистр к новой записи информации), .на второй вход элемента И 22, который при наличии сигнала на правом входе с .выхода выдает сигнал сдвига информации в регисти pax . в сторону старшего разряда. . Дальнейшая работа устройства trpoTeкает путем чередования тактов Ш и W до тех пор,- пока не будет возбужден последний из разрешённых выходов последнего распределителя. Иногда с управляющего выхода распределителя подается сигнал на разрешающий вход соответствующего элемента И 10. Очередной сигнал, поступающий на вход 14 тактовых импульсов, пройдет на вход (M-l)-ro, а через элемент И 10 - на вход (Ы-З)-го распределителей, а также на вход (N-l)-ro элемента 12 задержки. Если выполняются условия образования дерева, то при поо; туплёнии сигнала на вход 15 опроса срабатывает элемент И 1. В результате поступает сигнал на входы N -го и (N-l)-ro счетчиков. При этом возбуждается очередной разрешенный выход в (N-2)-M распределителе и возбуждается

младший R3 разрешенных (с учетом нового состояния (Н-2)оГо распределителя) вькодов(М-1)-го распределителя. Таким о6разоМ| перевод каждого распределителя в новое состояние осушествляе ся при поступлении сигнала на вход 14, если распределители с высшими номерами (но не все) находятся в последних из разрешенньт. состояний.

Работа устройства завершается, если все распределители устанавливаютса э последние Из разрешенных состояний. Тогда 1фи поступлении очере иого сигнала на вход 14 срабатывают вое элементы 1О. Сигналы с выходов элементов И iO переводят распределители в исжойное сос1х яниё, а сигнал с выхода элемента И 1О является сигналом останойа работы устройства. Показание N -го счетчика 4 соответствует деревьев в графе« Показание (K-l)-ro счетчика 4 соответствует числу подмножеств, в которых деревья имеют (Н-2) постояйньОс реб. Позесазания (N-2) счетчика сооти: вётству|рт числу Пошляожеств, в которыхдереэьй имеют (N-3) постоянных ребер и т.д. , :,/:: -... ; - , - ,; . ..

По сравнению с известным устррйс-лвом изобретение обоеспечивает более высокую TowocTb определен ия харак теристнкй графа.

Формула изобр е т е н и я : Устройство для разложения графа на деревья по авт. св. Mi 748428, о т л ич а ю ш е е с я тем, что, с повышения точности, в него введены допол нительные регистры, распределитель и элемент И, сдвигающие регистры и блок шифрат(ов, входы которого подключены соответственно к выходам первого набо1 10 ного поля, выходы бл(жа шифраторов подключЕены с(м тветственно ко входам дополнителыюго регистра, управляюший вход которого соединен с первым входом Дополнительного элемента И и .является

15 входом тактовых импупьсов устройства, выходы дополнительного регистра соединень со влсодами Дополнителыюго распределителя, управляюший вход которого

подключен к выходу элемента И, выход до20 полвительного распределителя соединен со вторым входом дополнительного элементам выход которого подключен к сдвигаюшим входам сдвигаюших регистров, информационны е входы которых соединены соответственно

25 с выходами дополнительного распределите: ™ -. - -;

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

I II

.

I I. N

гц.

«

$

22