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

 

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

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

Респубпни

О П И С А Н И Е (888l28

ИЗОБРЕТЕН ИЯ

К АВТОРСКОМУ СВИДЮТЕЛЬСТВУ (6l ) Дополнительное к авт. свид-ву (22) Заявлено 31.03.80 (21) 2901578/18-24 с присоединением заявки,йте (23) ПрЪ оритет

Опубликовано 07. 1 2. 81. Бюллетень М 45

Дата опубликования описания 09.1 2.81 (5I)M. Кл.

О 06 F 15/20

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

В. Н. Червяцов (71) Заявитель (54) УСТРОЙСТВО ДЛЯ ОПРЕДЕЛЕНИЯ ЧИСЛА

ДЕРЕВЬЕВ B ГРАФЕ

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

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

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

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

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

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

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

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

8881 28

1О

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

На чертеже представлена блок-схема устройства для определения числа деревьев в графе.

Устройство содержит блок 1 перебора сочетаний, первый блок регистров 2 1

2,... 2,, регистр 3, -второй блок регистров 4,1, 4 g ... 4л, первый 5, второй

6 коммутаторы, первую группу ключей

7,1, 7 g ... 7, первый элемент И 8, ключ 9, второй элемент И 10, первый и второй элементы ИЛИ 11, 12, элемент

13 запрета, наборное поле 14, триггер

15, блок 16 сравнения, генератор 17 импульсов и счетчик 18.

Топография графа задается на наборном поле 14 путем коммутации выходов поля, соответствующих в вершинам графа, и входов поля, соответствующих М ребрам графа.

Устройство для определения деревьев графа работает следующим образом.

При поступлении сигнала на вход генератора 17 генератор запускается и вырабатывает тактовые импульсы, которые поступают через коммутатор 5 на вход блока 1. На каждом такте блока перебора сочетаний возбуждает В-1 выход из М по программе С, (программа П 1). Сигналы с выходов блока 1 поступают на входы регистров 2 и запоминаются. С выходов блока регистров 2 сигналы поступают на входы группы ключей ребер 7, между выходами ключей при этом устанавливается электрический контакт. Если данный набор В- 1 ребер из М образует первое дерево, срабатывает элемент И 8 и переводит триггер 15 в единичное состояние. С единичного выхода триггера 15 сигнал Сравнение поступает на четвертый вход коммутатора 5 и на четвертый вход блока 16, коммутатор 5 подключает выход генератора

17 к третьему входу блока 16. Блок 16 осуществляет -сравнение-набора, записанного в первой группе регистров 2, с наборами, записанными во второй группе блока регистров 4. Поскольку все регистры 4 пока свободны, на выходе блока

l6 вырабатывается сигнал «Нет сравнения, который поступает через элемент

ИЛИ 11 на инверсный вход триггера

15 и на вход коммутатора 5. При этом триггер устанавливается в нулевое состояние и снимает сигнал Сравнение с входа блока сравнения, а коммутатор

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

В данном устройстве временные затра-. ты значительно меньше. Сокращение времени достигается за счет последовательного применения двух программ. По первой программе отыскивается дерево путем выбора В-1 ребер из М. После отыскания первого дерева независимые с ним деревья отыскиваются путем выбора В-1 ребер из М-В+ 1, при этом число выборов резко сокращается.

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

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

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

45 сочетаний соответственно, третий выход блока перебора сочетаний подключены к первому входу генератора импульсов, Второй вход которого является входом устройства, выход генератора импульсов подключен к первому входу первого коммуS0 татара, первый выход которого подключен к второму входу блока перебора сочетаний, второй выход первого коммутатора подключен к управляющему входу первого блока регистров, о т л и ч а ю щ е е55 с я тем, что, с целью расширения функциональных возможностей путем реализации дополнительной функции определения числа независимых деревьев графа, в не 5 888128 нератора 17 через коммутатор 5 ца входы блока регистров 2, содержимое блока регистров 2 через элемент 1 3 переписывается в регистр 3. По окончании записи в регистр 3 на его выходе формируется сигнал Занят", а на рабочих выходах формируются сигналы запрета, поступающие в блок 1.

Блок перебора сочетаний переключается на работу по программе С (про- fly

В-1 грамма П 2). Сигнал Занят" поступает на вход элемента 13, ключа 9, элемента И 10 и через элемент ИЛИ 12 на второй вход коммутатора 5. Под действием сигнала Занят" выходы блока ре- ls гистров 2 отключаются от входа регистра 3 и подключаются через ключ 9 и коммутатор 6 к входу блока регистров

4; выход генератора 17 через коммутатор 5 подключается к входу блока 1. При 30 поступлении сигналов от генератора блок

1 на каждом такте возбуждает В-1 выход из М-В + 1. Очередной набор В- 1 сигналов проверяется на условие образования дерева. Если набор сигналов обра- Формула зует дерево, то в отличие от рассмотренного выше данный набор записывается через ключ 9 и коммутатор 6 в блок 4.

По окончании записи набора в регистр 4 с выхода коммутатоРа 6 выдается сигнал 30 вый KbMMyTaTop, первую группу ключей, Занят" на вход элемента И 10 и через элемент ИЛИ 12 на второй вход коммутатора 5. При этом в счетчик 18 записывается единица, а блок перебора сочетаний продолжает работу по программе

П 2.

При завершении работы по программе

П2 с выхода блока 1 в регистр 3 выдается сигнал "Конец П 2, который сбрасывает регистр в исходное состояние, в результате чего блок перебора сочетаний переходит на работу по программе П 1.

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

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

Алгоритм отыскания независимых деревьев в графе с помощью известных устройств

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

ro коммутатора, первая группа выходов которого подключена к входам второго блока регистров соответственно, выходы которой подключены к первой группе входов блока сравнения соответственно, вто1 рой выход второго коммутатора подключен к вторым входам второго элемента ИЛИ и второго элемента И, выход которого подключен к входу счетчика, первая группа выходов первого блока регистров подключе2R на к втором7 входу блока сравнения, первлюй выход которого подключен к второму входу первого элемента ИЛИ и к третьему входу второго элемента ИЛИ, выход которого подключен к второму входу первого коммутатора, третий выход которого подключен к третьему входу блока сравнения, второй выход которого подключен к треть-ему входу первого коммутатора и третьему входу первого элемента ИЛИ, выход которого подключен к инверсному входу триггера, выход первого элемента И под1 ключен к прямому входу триггера, выход которого подключен к четвертому входу блока сравнения и четвертому входу первого коммутатора.

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

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

% 271 906, кл. G 06 G 7/48, 1 974.

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

No 329538, кл. G 06 G 7/48, 1 977. и

8111111 !И Дд аа 1872 / 14 1и а 748 Даи1аирнра

Ф14лиал ППП "Пат1пт", I . акгород, ул. Прог.кг14ая, 4