Пзобретеиие относится к области вычислительной техники и может быть нсиользовано для определения характеристик связности графа, у которого вероятность существования ребер и вершин отлична от единицы.
Известны устройства для определения характеристик связности графа, содержащие схему «И, запоминающие триггеры верщии, управляемые ключевые схемы, которые управляются запоминающими триггерами вершин, запомииаюшие триггеры ребер, управляемые ключевые схемы, которые входами управления подсоединены к выходам запоминающих триггеров ребер и соединены собой через управляемые ключевые схемы ипциндентных им вершин в схему, отображаюи1ую граф. Подавая на одну из вершин импульс проверки проводимости, исследуемые характеристики связности графа онределяют наличием электрической проводимости между задаппой группой вершин, определяемой схемой «П.
Недостатком таких устройств является то. что характеристики связности могут быть rioлучены только для фиксированного числа верщин.
Цель данного изобретения заключается в определении характеристик связности, присутствующих в данном розыгрыше вершии, число которых иеременно.
Эта цель достигается путем опреде.чения связности всех вершин; отсутствующие верН1ИНЫ имитируют подключением нулевых выходов запоминающих триггеров вершин на
вход схемы «И через схему «НЛП, а иоиск вершины, на которую необходимо подать сигнал проверки, осунгествляется подачей сипала на последовательно включенные ключи, уиравляемые нулевыми и единичными выходами запоминающих триггеров вершг.н.
Схема описываемого устройства изображена на чертеже.
cтpol cтвo содержит шину / ироверки нроводимости; шину 2 установки триггеров в нулевое положение, шины .3 результатов розыгрьипа вершип, нлпны 4 результатов розыгрыша ребер, шину 5 сигнала отсутствия вершин в данном розыгрьпие. схемы «ПЛП 6. 1иину 7
съема результага, схему «li 8, шину 9 опроса результата, ключи 10, 11 передачи сигнала ироверки проводимостп, запоминающие триггеры 12 вершин, управляемые ключевые схемы 13 вершин, запомипающие триггеры 14 ребер, управляемые ключевые схемы 15 ребер, ключ 16 сьема результата; входы 17 и вых1)ды 18 управляемых ключевых схем /5 соединены с выходами 19 уиравляед ых ключевых схем /,) в схему, отображающую граф; входы
пни на них праилякмних гигналон coc;i,iiiic bi с ,;, хода ми 19.
абога устроисПК мроисход ; по гакт;).; /1, /2. .:-;, /:. В такте t по ипшс 2 псхтупаст сигпал. которы стапавливает и iiy.iCBoe положспис трштеры 12 и 14. В такте /2 по нал; 3 поступают результаты р()зыгр1.11па стояшп; вершин, а по шппам 4 рез . еоетояиий ребер, Koi4))i,ie eooiiK «сино поетукпот па входы Tpnii-epoi 1 Триперы фиксируют iiojiyieiuibie результаты розьпрыша. Состояние «1 заполшпаюших триперов 12 1: 1.4 означает нр 1еу;ет1зпе соотBCTCTByiOHuix вершин и ребер в даппол; розыгрь:ше. Триггеры 12 управляют унраиляе.и,р,п ключевыми схемами 13 вернпш, а триггеры 14 - управляемыми ключевыми схемами 15 ребер. 1-ели вернпп-а нриеутствует в розыгрь ше, eждy выходами 19 и входами 20 управлиемоГ{ ключево ехе.мы верппшы. образуется элсктричес И11 ;онтакт. СоответегБеино входами /7 и выходами IS унра; ляем1лх ключевых схем 15 нрисутствую1дих )ебер образуется -л1ектр1Н1ее1 И 1 1 оитакг. В такте /,, ио И1Нне / иодастея еигна. нровер1 и ирд)водил;остн, который иост)Т1ает на ключи 10 и 11, соотвегетвуюи1ие нервоГ верипше. lie;: данная вершииа присутствует в розыгр1лп1е, то триггер 12 находится в единичном иоложеинн и едииич1н 1м )M открывает к.иоч //, через Kt)TO|) .i ироверки ирог одимости иостуиает иа вход 20 нерв( верншиы. В нротивиом случае иу,1евьь ; выходо.м т)иггер; 12 открывается клк:1Ч 10 нервеи ; верииинл, и еигиа, ироверки проводимости ностуиает на ключи 10 и // lipopoii iiCpiHiiiii,, и так до тех нор, че будет об11а|)ужеиа нрисутству1ои1ая вершина. Если сигнал проверки нрО1 Одимости пройдет все ключи и не обнаружит ии одпой присутствующей вери1ины, то сигнал об поступает ио шине 5 и исгидтания заканчиваются. Проверка связности ирисутств чоииих вернпш схемой «И 8 оиределяетея как eBH3i OCTij всех , но а схему «И 8 ноетхчипот сигналы с иулевых выходов триггеров 12 отсутствующих через схемы «ИЛИ.--;- 6. Таким образом, отсхтствукяиие вернппкл ечитаются как 6, ирисутствукидими и связ)п.1мн
( ироие;);; иро-юдимоети lui вход 20 rsepHiHHbi, | оторая обиару/кена нри номощн ключ(Г| / н //, а чере:, ч1рав,1яелП)е K,iio4eBi)ie ехемы /о всрииш и уиранляемьк: ;;;i 04CBb e елем:л 15 ребер, меичду входалш li выходами; -иггорых слчиествхеч коитакт, иоет -нает иа isce 15ходы 20 вершин, связаин1)1е с обпа|)()й iie HiiHHOi i. Со иход.ов 20 веринщ еи1Ч1ал; 1 )т через ехему «ИЛИ 6 иа
г; ход ехе..;ь « i 8. .1и irs и)ис тствуюни1Х ег)1иии хоти 6i)i одна но связана с остал)ИЬ:1и, то lia входе схел;ы «И, с;)ответств чощем той ьери.н1ие, С11гиала не будет. В с.пчае вязиости всех ирисутствуклинх вергиин и.а ;ех входах схемы «II- 8 .т еи:Ч1ал л. Схоla «II срабс/гает li откроет 16. В такте i 9 ност.нает сигнал оироса резу.чьата нснытания иа ключ 16. Если все ирисутTBVKHHHe вепннпН) евязаиы, ключ 16 открь;ается и иа ин1ие 7 иоявитея eiirna/.
.устройство для оиределе Н1я характсрг-етик
С15ЯЗИОСТН еро;-:тиоети01-о графа, соде1)жаи1ее заи()А:ниа:он1ие триыеры, унра1)Ляемые ключевые ехе.мы, ivOTOpbiC входа.ми уиравлення ио.тсоедииеиы { Илходал заиомииаюн1их три14сров и соединень между еобой в схс.му, отображаюи1у1о граф, ннну нрове)кн нроводнмоетн, ехему «И, схемы «ПЛИ, кл1(Ч )езу.1ьтата, отличающессл тел;, ч;ч), е целью |))1 функнноиа.:1ьи;;Н В().М()жиоетей уст 10|1ства, в не.м нулевые 1Я,1ходы : аиомииа ощнх трн14е }0в веринин rp;uj)a 1;(.1Д;чЛючен1 1 к ехе.;е «П через схс.мг, «ПЛП, шина нрове|)ки ироводи.мостп нодключеиа к входа.м к,1ючей но чнеду вернн)н графа, нриче:а входы уир.авления одинх к,тючей соединеунл с нулевы.ми выходами запоминающих три1Черов вери ии, а выход ключа нредыд щей вер1иииы соедииеи с входом ключа иоследу1ои.ей вершины, входы же уиравления других ключей соединены с едииичиыми В1з1ходами зaиo инaю иих триггеров веруиии, а вьиходь этих ключей нодключеиы иа входы иIpaвляe :ыx ключевых ехем соответе;ч чонд х вернлин и на свободиые )Д,1 соот1;отс ч; joHiiix схем «ИЛ1Ь.
