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

 

ОП ИСАНИ

ИЗОБРЕТЕН И

К АВТОРСКОМУ СВИДЕТЕЛЬСТ

1922781

Союз Советских

Социалистических

Республик (6) ) Дополнительное к авт. свид-ву ¹ 748 (22) Заявлено 01. 11.78 (2l ) 2680041у

l)NL. Кл.

9066 7/122 с присоединением заявки J% фяударетвенный каиитет

СССР но делан изобретений н открытий (23) Приоритет

Опубликовано 2З.04.82. Бюллетень

Ъ

Дата опубликования описания 2З.О

3) УДК 681. .ЗЗЗ(088,8)

I

1,.: .. .: j

В. Н. Черьяцов и А, Н. Кирьянов / " -.. " -,!

/ (72) Авторы изобретения (71) Заявитель (54) УСТРОЙСТВО ДЛЯ РАЗЛОЖЕНИЯ

ГРАФА НА ДЕРЕВЬЯ

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

По основному авторскому свидетельству ¹.77448844228 8 lиlз вBеeс т но у с т роoй с т вBо0, содержащее элемент И, входы которого подключены к выходам первого наборного

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

15 счетными входами других счетчиков, Bblходы сброса счетчиков и нулевые входы триггеров (И-1)-группы подключены к входу сброса устройства, единичные входы триггеров (N-1)- групп соединены ..c

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

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

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

Поставленная цель достигается тем, что в устройство введены дополнительные регистры, распределители и элемент

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

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

Устройство содержит элемент И 1, наборное поле 2, ключи 3 -3 ребер, счетчики 4 -4н, элементы И 5п -5g q первой группы, триггеры 6 -6N-qð ребер, элементы 7 - 7 q,ц запрета, распределители 8 -8N q, наборное поае

9, элементы И. 10 -10 второй группы, наборное поле 11, элементы 12 -12, задержки, вход 13 имйульсов сброса, вход 14 тактовых импульсов, вход 15 импульсов опроса, выход 16 импульсов останова, вход 17 импульсов стирания информации, блок 18 шифратора, дополнительные регистр 19 и распределитель

20, сдвигающие регистры 21 -21 „и допсанительный элемент И 22, Входы элемента И 1 подключены к выходам наборного поля 2, входы кото-, рого подключены к полюсам ключей 3 3 ребер, а выход подключен к входу последнего счетчика 4, к размыкаюшему входу распределителя 20 и к первым входам элементов И 5 -5 1, выходы которьи подсоединены к входам остальных

2781 4

1 счетчиков 4 -4 .1. Единичные входы триггеров 6 „-6 i,éðeáåð подсоединены

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

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

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

12 задержки, выход которого подсоеди2S нен к второму входу соответствующего элемента И 5. Входы блока 18 шифраторов подсоединены к вьиодам наборного поля 2, а выходы каждого шифратора в бпоке 18 шифратора подсоединены к со зэ ответствующему разряду регистра 19, вьиоды которого подсоединены к входу распределителя 20. Выходы распределителя 20 подключены к входам записи регистров 21<-21N.1, а управляющий

3s выход Распределителя соединен с первым входом элемента И 22, второй вход которого соединен с входом 14 тактовьи импульсов, а выход подключен к ВхоааМ импульсов сдвига регистров 21.1-21ц . п Нулевые входы триггеров 6 и входы стирания счетчиков 4 соединены с входом

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

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

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

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

9*И:"*%ii

5 где с „.1 — номер ребер графа;

a; - столбцы, содержащие номера ребер, образующие деревья графа.

Этап задания структуры графа полностью аналогичен этому этапу в извес ном устройстве.

В дальнейшем, на этапе исследован графа, работа устройства протекает по тактам.

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

13 сброса и на нулевые входы триггеро

6 и стирающие входы счетчиков 4. Три е геры и счетчики устанавливаются в исходное состояние.

В такте и в соответствии с,матрице инцидентности поступают сигналы на единичные входы триггеров 6 ребер, которые устанавливаются в состояние "

С единичных выходов триггеров 6 ребер . инцидентных первой вершине, поступают сигналы на входы распределителя перво вершины. С единичных выходов трщ геро

6 ребер, инцидентным остальным верши нам, сигналы поступают на входы соответствующих распределителей через эле менты 7 запрета. В каждом распредели теле возбуждается адин выход, соответ ствующий возбужденному входу с меньшим номером. Сигналы с выходов рас делителей поступают. через схему комму таций наборного поля 9 на входы соответствующих элементов 7 запрета, а че рез схему коммутаций наборного поля 1 на входы соответствующих ключей З.,П этом запрещаются сигналы на одноимен ных выходах распределителей, соответст вующих вершинам со старшими. номерам

В результате в каждом распределителе возбужден только один выход, причем среди возбужденных выходов нет одноименных. Возбужденные выходы имеют меньшие номера из множества разрешен ных номеров.

При поступлении сигналов на управля ющие входы ключей 3 образуется электрический контакт между их полюсами.

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

15 опроса, который через схему комму таций наборного поля 2 поступает.на вх ды элемента И 1 и на соответствующие входы блока 18. С каждого выхода блок закодированный сигнал поступает на вхо регистра 19. Т.е. в соответствующие разряды регистра записывается цифровой код сигнала, поступающего на аналогичные входы элемента И 1. Если возбужденные выходы распределителей соответ

- т ют ребрам, образующим дерево„то

922781 6 срабатывает элемент И 1 и с его выхода подается сигнал в .последний счетчик

4 и на разрешающий вход распределителя, который преобразует последовательность цифровых кодов регистра 19 в параллельт ные коды по разрядам и запись этих кодов в регистры 21.;-21«» т.е. в регистия . рах 21„-21 <записан код первого nepesa графа.

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

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

15 19 и на второй вход элемента И 22. При и этом возбуждается очередной по номеру из разрешенных выходов последнего рас пределителя 8, 1 Если комбинация ребер не соответству-, 20 ет дереву, то с выхода элемента И 1 не поступает сигнал на раэрешающйй вход и распределителя 20 и эта комбинация в ребер не заносится в регистры 21 -21 (»„.

Если комбинация ребер соответствует де25 реву, тораспределительпроиэводитсоотве1 ствующую комбинацию цепей и комбинация ребер записывается в регистры 21 -21 . .

При этом распределитель выдает сигнал на первый вход элемента И 22. С припре-50 ходом тактового импульса на вход 14 он поступает на вход стирания регистра

19 (стирает предыдушую комбинацию ребер и готовит приемный регистр к но1 вой записи информации), на второй вход ри 35 элемента И 22, который при наличии сигнала на правом входе с.выхода выдает сигнал сдвнга информации в регисъи. рах 21.,-23 < в сторону старшего разряда в

Дальнейшая работа устройства протекает путем, чередования тактов1 В и ф до тех пор, пока не будет возбужден последний из разрешенных выходов последнего распределителя. Иногда с управляющего выхода распределителя подается сигнал на разрешающий вход соответствующего элемента И 10. Очередной сигод нал, поступающий на вход 14 тактовых импульсов, пройдет на вход (К-1)-го, а о- через элемент И 10 - на вход (й-2)-го

50 распределителей, а также на вход (N-1)-го а элемента 12 задержки. Если выполняются д условия образования дерева, то при поо". туплении сигнала на вход 15 опроса сра55 батывает элемент И 1, B результате поступает сигнал на входы N -го и (N-1)-го счетчиков. При этом возбуждается очередной разрешенный выход в (И-2)-м распределителе и возбуждается

7 92 младший из разрешенных (с учетом нового состояния (К-2) «ro распределителя) выходов (М-1) го распределителя. Та» ким образом, перевод каждого распреде лителя в новое состояние осушествляеь ся при поступлении сигнала на вход 14, если распределители с высшими номера ми (но не все) находятся в последних из разрешенных состояний.

Работа устройства завершается, если все распределители устанавливаются в последние из разрешенных состояний.

Тогда при поступлении очередного сигнала íà вход 14 срабатывают все элементы 10.. Сигналы с выходов элементов И

i0 переводят распределители в исходное состояние, а сигнал с выхода первого элемента И. 10 является сигналом останова работы:устройства. Показание М -го счетчика 4 соответствует чисйу деревьев в графе. Показание (М-1)-го счетчика 4 соьтве гствует числу подмножеств, в ко» торых деревья имеют (й-2} постоянных ребер. Показания (й-2) счетчика сооь- ветству1от числу подмножеств, в которых деревья имеют (й-3) постоянных ребер и т,д.

По сравнению с известным устройст»вьм изобретение обоеспечивает более высокую точносж определения характеристики графа, 2781 8

Формула изобре тения

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

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

1. Авторское свидетельство СССР % 748428, кл. Я 06© 7/122, 1978 (прототип).

922781

Составитель И. Загорбинина

Редактор Л. Лукач Техред И. Гайду Корректор С. Шекмар

° Ю \6 МВВ 3ВЮ ЮВ °

Заказ 2584/66, Тираж 732 Подписное

ВНИИПИ Государственного комитета СССР по делам изобретений и открытий

113035, Москва, Ж 35, Раушская нвб., д. 4/5

Филиал ППП "Патент", г, Ужгород, ул, Проектная,