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

 

О П И С А Н И Е <н748428

ИЗОБРЕТЕНИЯ

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

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

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

Республик

{61) Дополнительное к ввт. свид-ву

I (22) Заявлено 1003.78 (21) 2588679/18-24 с присоединением заявки М (23) Приоритет

Опубликовано 1507.80. Бюллетень М 26

Дата опубликования описания 150780 (51)М. Кл.

G 06 G 7/122

Государственный комитет сссР по делам изобретений и открытий (53) УДК 6 81. 3 3 3 (088.8) (72) Автор изобретения

В. Н. Червяцов (11 ) 3a яв и тель (54) УСТРОЙСТВО ДЛЯ РАЗЛОЖЕНИЯ ГРАФА

HA ДЕРЕВЬЯ

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

Известно устройство $1j для поиска прадеревьев направленного графа, содержащее ключевую матрицу, кольцевые коммутаторы, генератор тактовых импульсов, триггеры, схемы И, схемы задержки, блокирующую ячейку, инвертор. Это устройство позволяет 15 сократить число тактовых импульсов, необходимых для поиска всех пра-. деревьев в направленном графе путем исключения частичных графов, в которых повторяются не связанные с кор- 20 нем компоненты, содержащиеся в ранее рассмотренных частичных графах.

Это устройство характеризуется сле1дующими недостатками: отсутствие возможности исследовать ненаправленный граф," отсутствие возможности определения числа деревьев, образованных с участием каждого отдельного ребра. графа, отсутствие возможности управ.ления процессом образования деревьев;ЗО отсутствие возможности определения характеристик разложения графа на деревья.

Известно устройство для нахождения деревьев графа (21, содержащее блок индикации, счетчики, диоды, пере-. ключатели, линию задержки, блоки коэффициентов пересчета, счетчики числа деревьев. Этому устройству присущи следующие недостатки: отсутствие возможности определения числа деревьев, образованных с участием каждого отдельного ребра графа; отсутствие возможности управления процессом образования деревьев; отсутствие возможности определения характеристик разложения графа на деревья.

Наиболее близким техническим решением к изобретению является устройтво для определения числа деревьев

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

748428 (11 -1) Групп подключены к входу сброса устройства, единичные входы триггеров (11 -1) групп соединены с входами записи устройства. Кроме того, устройство содержит блок перебора состояний.

Недостатками прототипа являются: отсутствие воэможности управления процессом образования деревьев, отсутствие возможности определения характеристик разложения графа на деревья. Характеристиками разложения графа на деревья являются числа подмножеств, в которых деревья имеют постоянными одно, два и т. д. ребер.

Цель изобретения — повышение точности исследования путем реализации дополнительной функции определения чисел подмножеств, в которых деревья имеют постоянными одно, два и т. д. ребер, и представления возможности 20 управления процессом образования деревьев.

Цель достигается тем, что в устройство, содержащее элемент И, входы которого подключены к выходам 25 первого наборного поля, входы которого соединены с выходами ключей, выход элемента И подключен к счетно му входу одного счетчика и к первым вхЬдам элементов И первой группы, выходы которых соединены с счетными входами других счетчиков, выходы сброса счетчиков и нулевые входы триггеров .(11 -1) групп подключены к входу сброса устройства, единичные входы триггеров (N -1) групп соединены с входами записи устройства, введены элементы задержки, вторая группа элементов И, элементы .запрета, второе и третье наборные поля и (N -1) распределите- 40 лей, входы первого распределителя соединены с единичными выходами триггеров первой группы, входы остальных распределителей подключены к выходам элементов запрета, первые .45 входы которых соединены с единичными выходами триггеров остальных групп. вторые входы элементов запрета подключены к выходам второго наборного поля, выходы (М - 1) распределителей соединены с входами третьего наборного поля, выходы которого подключены к управляющим входам ключей, управляющий вход (, N -1)-ro распределителя соединен "с входом тактовых импульсов устройства и с

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

Функциональная схема устройства представлена на чертеже.

Устройство содержит элемент И 1, первое наборное поле 2, ключи 3 -3 (ребер), счетчики 4т-, 4„, элементы

И 5 - . 5ц.„ первой группы, триггеры бл -, б „„,„q (ребер), элементы запрета 7 -, 7ц RAN „, распределители

8 - . 8< л, второе наборное поле 9, элементы Й 10 †. 10ц q второй группы, третье наборное поле 11, элементы задержки 12 2 †: 12N-5 вход сброса

13, вход тактовых импульсов 14, вход опроса 15, выход импульсов останова 1б,вход записи 17.В триггерах б; „; — номер вершины, j -номер ребра, инцидентного данной вершине.

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

Рассмотрим этап задания структуры графа. Основой для задания графа в устройстве является граф, имеющий 11 вершин и M ребер, в котором все элементы перенумерованы. Элементы устройства упорядочиваются в соответствии с принятой нумерацией. Номера вершин присваиваются распределителям 8 и входам, элемента И 1. Количество распределителей равной -1, количество входов элемента И 1 равно

N . Номера ребер, инцидентных вершинам присваиваются входным и выходным цепям распределителей 8,Номера возрастают слева направо, На наборном поле 2 входы элемента

И 1 и ключи (ребер) 3 †. Зм соединяются в топологическую схему графа.

На наборном поле 11 выходы распределителей 8 и входы ключей 3, соответствующие одноименным ребрам графа, соединяются между собой. На наборном поле 9 выходы распределителей 8 и входы элементов запрета 7, соответствующие одноименным ребрам, но инцидентные разным вершинам, соединяются между собой. При этом соблюдается правило: выход распределителя, соответствующего вершине с меньшим номером, должен быть соединен с входом одноименного элемента запрета соответствуюшего вершине с большим номером.

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

748428 счетчики устанавливаются в исходное состояние.

Во втором такте в соответствии с матрицей инцидентности поступают сигналы на единичные входы триггеров 5 (ребер) б, которые устанавливаются в состояние "1". С единичных выходов триггеров б (ребер), инцидентных первой вершине, поступают сигналы на входы распределителя первой вершины. 1р

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

При поступлении си".íàëîâ на управляющие входы ключей 3 образуется35 электрический контакт между их полюсами.

В третьем такте поступает сигнал на вход опроса 15, который через схему коммутаций наборного поля 2 4р поступает на входы элемента И 1. Если возбужденные выходы распределителей соответствуют ребрам, образующим дерево, то срабатывает элемент И 1 и с его выхода подается сигнал в пос- 45 ледний счетчик 4.

В четвертом такте поступает сигнал на вход та <товых импульсов 14, кото рый подается на управляющий вход последнего распределителя 8 и входы эле-5р ментов И 10. При этом. возбуждается очередной по номеру из разрешенных выходов последнего распределителя 8.

Дальнейшая работа устройства протекает путем чередования третьего .и четвертого тактов до тех пор, пока не будет возбужден последний из разрешенных выходов последнего распределителя. Тогда-с управляющего выхода распределителя подается сигнал на разрешающий вход соответствую- бр щего элемента И 10. Очередной сигнал, поступающий на вход тактовых импульсов 14, проходит на вход N-4 -ro а через элемент И 10 на вход N-1-го распределителей и на вход N- 1 -го эле-, 65 мента задержки 12. Если выполняются условия образования дерева, то при поступлении сигнала на вход опро"а 15 сработает элемент И 1. В результате поступит сигнал на входы

-ro и N -1 -ro счетчиков. При этом возбуждается-очередной разрешенный выход в N -2-м распределителе и возбуждается младший иэ разрешенных (c учетом нового состояния и -2-го распределителя) выходов N -1 — го распределителя. Таким образом, перевод каждого распределителя в новое состояние осуществляется при поступлении сигнала на вход 14, если распределители с высшими номерами находятся в последних из разрешенных состояний.

Работа устройства завершается, если все распределители устанавливаются в последние иэ разрешенных состояний. Тогда при поступлении очередного сигнала на вход 14, срабатывают все элементы И 10. Сигналы с выходов элементов И 10 переводят распределители в исходное состояние, а сигнал с выхода первого элемента

И 10 является сигналом останова работы устройства. Показание N -"o счетчика 4 соответствует числу деревьев в графе. Показание N -1-го счетчика 4 соответствует числу подмножеств, в которых деревья имеют N -2 постоянных ребер. Показания 4 -2-го счетчика соответствуют числу подмножеств, в которых деревья имеют 8 -3 постоянных ребер и т. д;

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

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

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

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

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

748428

/7 /7 И /7

ЦНИИПИ Заказ 4241/37 Тираж 751 Подписное

Филиал ППП Патент, r, Ужгород, ул, Проектная,4 роса счетчиков и нулевые входы б триггеров (Ч -1)групп подключен к ны входу сброса устройства, единич-.

cî ные входы триггеров (N -1) груп и оединены с входами записи устройства, отличающееся тем чт то, с целью повышения точности, к в него введены элементы задержки, вторая группа элементов И, элементы запрета, второе и третье наборные поля и (И -1) распределителей, входы первого распределителя сое иены c единичными выходами триггеров первой группы, входы остальных распределителей подключены к выходам элементов з в запрета, первые входы которых соединены с единичными выходами тригге ров остальных групп, вторые входы элементов запрета подключены к выN -1 ходам второго наборного поля выхо ы

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

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

1. Авторское свидетельство СССР

Р 271906, кл. G 06 G 7/48, 1969.

2. Авторское свидетельство СССР

9 364939, кл. С 06 6 7/48, 1971.

3. Авторское свидетельство СССР

Р 329538, кл. G 06 G 7/48, 1970 (прототип).