Устройство для определения числа деревьев в графе Советский патент 1981 года по МПК G06F15/173 

(54) УСТРОЙСТВО ДЛЯ ОПРЕДЕЛЕНИЯ ЧИСЛА ДЕРЕВЬЕВ В ГРАФЕ

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

..систем, отображаемых графами.

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

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

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

10 деревьев графа.

Цель изобретения - расщирение функциональных возможностей путем реализации дополнительной функции определения

15 числа независиклых деревьев графа.

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

го группу ключей, первый элемент И, регистр, наборное поле, генератор импульсов и счетчик ,причем первая группа выходов блока перебора сочетаний подключена к 38 группе информационных входов первого блока регистров соответственно, выходы которого подключены к входам ключей первой группы, выходы которых подключены к входам наборного поля, выходы которого подключены к входам первого эле мента И, второй выход блока перебора соче таний подключен к первому вхоцу регистра, первая группавыкоцов регистра поцключена к первой группе входов блока переборасо- четаний соответственно, третий выход блока перебора сочетаний подключен к первому входу генератора импульсов, вто рой вход которого является входом устро ства, выход генератора импульсов подклю чен к первому входу первого коммутатора, первый выход которого подключен, к второму входу блока перебора сочетаний, второй выход первого коммутатора подключен к управляющему входу первого блока регистров, введены второй блок регистров, второй коммутатор, ключ, триг гер, блок сравнения, второй элемент И, два элемента ИЛИ и элемент запрета, причем второй выход регистра подключен к первым входам элемента ИЛИ, второго элемента И, ключа и к инверсному входу элемента запрета, второй выход первого блока регистров подключен к второму входу ключа и прямому выходу элемента запрета, выход которого подключен к второму входу регистра, выход ключа подключен к входу второго коммутатора, первая группа выходов которого подключена к входам второго бпожа регистров соответственно, выходы которой подключены к первым входам блока сравнения соответственно, второй выход второго коммута тора подключен к вторым входам второго элемента ИЛИ и второго элемента И, выхо которого подключен к входу счетчика, первая группа выходов первой группы регистров подключена к второму входу блока сравнения, первый выход которого подключен к второму входу первого элемента ИЛИ и третьему входу второго элемента ИЛИ, выход которого подключен к второму входу первого коммутатора, третий выход которого подключен к третьему входу блока сравнения, второй выход которого подключен к третьему входу первого коммутатора и третьему входу первого элемента ИЛИ, выход кото рого подключен к инверсному входу триг гера, выход первого элемента И подключен к прямому входу триггера, выход которого подключен к четвертому входу блока сравнения и четвертому входу первого коммутатора. 8.4 На чертеже представлена блок-схема стройства для определения числа деревьев в графе. Устройство содержит блок 1 перебора сочетаний, первый блок регистров 2 , 2. ,...2 , регистр 3, -второй блок регистров 4 , 42. 4д , первый 5, второй 6 коммутаторы, первую группу ключей 1 , , 1 2 ... 7/д, первый элемент И 8, ключ 9, второй элемент И Ю, первый и второй элементы ИЛИ 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 пока свободны, на выходе блока 16 вырабатывается сигнал Нет сравнения, который поступает через элемент ИЛИ 11 на инверсный вход триггера 15 и на вход коммутатора 5, При этом триггер устанавливается в нулевое состояние и снимает сигнал Сравнение с входа блока сравнения, а коммутатор 5 подключает выход генератора к входу первой группы регистров 2, Под действием сигналов, поступающих с выхода ге- 58 нератора 17 через коммутатор 5 на входы блока регистров 2, содержимое блока регистров 2 через элемент 13 переписывается в регистр 3. По окончании записи в регистр 3 на его выходе формируется сигнал Занят, а на рабочих выходах формируются сигналы запрета, поступающие в блок 1. Блок перебора сочетаний переключается на работу по программе . (программа П 2). Сигнал Занят. поступает на вход элемента 13, ключа 9, элемента И 10 и через элемент ИЛИ 12 на второй вход коммутатора 5. Под действием сигнала Занят выходы блока регистров 2 отключаются от входа регистра 3 и подключаются через ключ 9 и коммутатор 6 к входу блока регистров 4; выход генератора 17 через коммутатор 5 подключается к входу блока 1. При поступлении сигналов от генератора блок 1 на каждом такте возбуждает В -1 выход из М-В+ 1. Очередной набор В-1 сигналов проверяется на условие образования дерева. Если набор сигналов образует дерево, то в отличие от рассмотренного выше данный набор записывается через ключ 9 и коммутатор 6 в блок 4, По окончании записи набора в регистр «4 с выхода коммутатора 6 выдается сигнал Занят на вход элемента И 1О и через элемент ИЛИ 12 на второй вход коммутатора 5. При этом в счетчик 18 записывается единица, а блок перебора сочетаний продолжает работу по программе П2. При завершении работы по программе П 2 с выхода блока 1 в регистр 3 выдает ся сигнал Конец П 2, который сбрасывает регистр в исходное состояние, в результате чего блок перебора сочетаний переходит на работу по программе П 1. По окончании программы П 1 с выхода блоки перебора сочетаний в генератор выдается сигнал Конец П 1, который останавливает генератор. На этом работа устройства завершается. Содержимое счетчика 18 указывает число попарно независимых деревьев. В известных устройствах анализ графа ограничивается либо определением числа деревьев, либо определением числа деревь ев, образованных с участием каждого отдельного ребра. В данном устройстве реа лизована возможность определения числа пар независимых деревьев в графе, что повышает полноту и точность анализа. Алгоритм отыскания независимых деревь ев в графе с помощью известных устройств 28 сводится к определению всех деревьев в графе, а затем сравнение деревьев между собой, такой алгоритм требует больших затрат времени. В данном устройстве временные затра-. ты значительно меньше. Сокращение времени достигается за счет последовательного применения двух программ. По первой программе отыскивается дерево путем выбора В-1 ребер из М. После отыскания первого дерева независимые с ним деревья отыскиваются путем выбора В-1 ребер из М - В + 1, при этом число выборов резко сокращается. Для того, чтобы исключить появление одинаковых наборов, полученных при обращении к первой и второй программам, в устройстве предусмотрена специальная проверка набора в блоке сравнения. Это в свою очередь сокращает количество тактов работы устройства для полного решения задачи. Формула изoбpeтeнияQ Устройство для определения числа деревьев в графе, содержащее первый блок регистров, блок перебора сочетаний, первый коммутатор, первую группу ключей, первый элемент И, регистр, наборное поле, генератор импульсов и счетчик, причем первая группа выходов блока перебо- ра сочетаний подключена к группе информационных входов регистров первого блока регистров соответственно, выходьх которого подключены к входам ключей первой группы, выходы которых подключены к входам наборного поля, выходы которого подключены к входам первого элемента И, второй выход блока перебора сочетаний подключен к первому входу регистра, первая группа выходов регистра подключена к первой группе входов блока перебора сочетаний соответственно, третий выход блока перебора сочетаний подключены к первому щрду генератора импульсов, второй вход которого является входом устройства, выход генератора импульсов подключен к первому входу первого коммутатора, первый выход которого подключен к второму входу блока перебора сочетаний, второй выход первого коммутатора ПОДКЛЮЧИ к управляющему входу первого блока регистров, отличающеес я тем, что, с целью расширения функциональных возможностей путем реализации дополнительной функции определения числа независимых деревьев графа, в не 78 го введены блок регистров, второй коммутатор, ключ, триггер, блок с;равнения, второй элемент И, два элемента ИЛИ и элемент запрета, причем второй выход регистра подключен к первым входам элементов ИЛИ, второго элемента И, ключа и к инверсному входу элемента запрета, второй выход первого блока регистров подключен к второму входу ключа и прямому входу элемента запрета, выход которого подключен к второму входу регистра, выход ключа подключен к входу второго коммутатора, первая группа выходов которого подключена к входам второго блока регистров соответственно, выходь которой подключены к первой группе входов блока сравнения соответственно, второй выход BTOjaoro коммутатора подключен к вторым входам второго элемента ИЛИ и второгхэ элемента И, выход которого подключен к входу счетчика, первая группа выходов первого блока регистров подключе8,и на к второму входу блока сравнения, первый выход которого подключен к второму входу первого элемента ИЛИ и к третьему входу второго элемента ИЛИ, выход которого подключен к второму входу первого коммутатора, третий выход которого подключен к третьему входу блока сравнения, второй выход которого подключен к третьему входу первого коммутатора и третьему входу первого элемента ИЛИ, выход которого подключен к инверсному входу триггера, выход первого элемента И подключен к прямому входу триггера, выход которого подключен к четвертому входу блока сравнения и четвертому входу первого коммутатора. Источники информации, принятые во внимание при экспертизе 1.Авторское свидетельство СССР № 271906 , кл. Q 06 Q 7/48, 1974. 2,Авторское свидетельство СССР № 329538, кл. G 06 & 7/48, 1977.