УСТРОЙСТВО для Советский патент 1972 года по МПК G06G7/48 

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

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

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

Предложенное устройство отличается тем, что в нем ед1ип1чный выход каждого запоминающего триггера подключен к первому входу соответствуклцего ключа, выход каждого ключа - ко входу соответствующего счегчика, а выход схемы «И через схему «ИГ. - ко всем вторым входам ключей.

дельного ребра, одновременно с онределением оби1,его числа деревьев этого графа.

Схема устройства изображена на чертеже. Устройство содержит блок / иеребора сочетаний, зано.мииаклцие триггеры 2, унравляемые ключев1;1е схемы 3, схему «И 4, схему «ИЕ 5, шипу 6 установки устройства в исходное состояние, командную тину 7, HiHiiy 8 проверки проводимости, ключи 9, счетчики 10

чис.к деревьев, образованных с участ11ем cooi 1зетствуюи.1его ребра, и счетчик I числа дс-рсвьев ipa(|)a.

Входы уирав. 51емых клк кмплх схем соединены между собой в схему, отображаюи.ую

гра().

Работа устро1 к-1Т а основана на том, что проверяется связпо(ть все:-: Л вери1ии графа при сочегаииях из .Д1 ребер графа ио (;V-- 1) ребер, так как связный гра(1), содержании Л вер1иии и (Л-1) ребер, является де 1евом. Устройство работает ио тактам /I, /9, /3. В такте ti но шине 6 иостуиает сигнал установкн трнггеров в нулевое ноложеиие. 1элок иеребора сочетаний образует иослсдовательность всевозможных сочетаний из Л но (Л-I), где Л1 - число ребер графа, а уУ--ч1 сло 1 ершин. В каждом такте /о а выходе блока перебора сочетапий появляется одно из сочетаиий С , которое поступает