Устройство для определения характеристик связности вероятностного графа

ЗО46О4

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

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

Рос>публик

Зависимое от авт. свиде "ельства X

Заявлено 14.VI 1.1969 (Ло 13484271 18-24) .ЧП1х О 06 > 7 48 с присоедине!шем заявки X.—

Приоритет

Комитет по делам ттзобретет>ий и открытий при Совете Министров

СССР

Оп бл !ковано 25.V.1971. т) !Олг!Оте.lh ¹ 17

УДК 681.333,001.57 (088.8) . 1,3Til О!!3 0,10! .Овани5! 0!Illci! Il!i 5! 28. » 1. 1 9 I 1

Авторы и:- с бр стен и я

А. Н. Чаплиц, В. В, Епихин и В. И. Ян

3 а яьитсль

УСТРОЙСТВО ДЛЯ ОПРЕДЕЛЕНИЯ ХАРАКТЕРИСТИК

СВЯЗНОСТИ ВЕРОЯТНОСТНОГО ГРАФА

11зобретение относится к области вы !ислитсльной техники и может быть использОвано для определения характеристик связности графа, у которого вероятность существования ребер и вершин orëè-Зна от единицы.

Известны устройства для определения ха рактеристик связности графа, содержащие схему «И», запоминающие триггеры вершин. управляемые ключевые схемы, которые управляются запоминающими триггерами вершин, запоминающие триггеры ребер, управляемые ключевые схемы, которые входами управления подсоединены к выходам запоминающих триггеров ребер и соединены между собой через управ Iÿåìûå ключевые схемы инцинденT ных им вершин в схему, отобража!ощую граф.

Подавая на одну из вершин импульс проверки проводимости. исследуемые характеристики связности графа определяют пали 3ие)i электрической прово IH)!oñòè между заданной группой вершин, определяемой схемой «11», Недостатко3! аких устройстВ явля Tc5! То, что xHp iKTcрисгики сВЯзиости !могут быть li;)лучены только для фиксированного шсла вершин.

Цель даш!ого изобретения заклю гнется в определении характеристик связности, присуTствующих в данном розыгрыше вершин, шсло которы: переменно

Эта цель достигается путем Опредслеш!я связности всеx вершин; отсутствующие вершины имитиру!OT подкл)очение>м нулевых выходов запоминающих триггеров верн!ни на вход схемы «11» через схему «11>111», а поиск вершины, на которую необходимо подать сигнал проверки, осуществляется подачей сип3ала на последовательно включенные ключи, управляемые нулеBBIx! II и единичными Bblxo10 дами запоминающих трип.еров вершин.

Сыма опись>ваемого устройства изображена на чертеже.

Устройство содержит шину 1 проверки про15 водимости; шину 2 уcTBíoBêè Tplil lcp013 в нулевое. положение, шинн! 8 результатов розыгрыша вершин, шины -1 результатов розыгрыша ребер, шину 5 сигнала отсутствия вершин ! !! н > o >! р 0 з> ь! !) ы и е с к с ) l i>1 « I I 1 1 1» () и н н 3 х

20 съема результага, C. åìó «11» 8, шину 9 опроса результата, клю н! 10, 11 передачи сипьала проверки проводимости, запоминающие триггеры 12 вершин, управляемые кл!очень!е схсмы 18 вершин, запоминающие триггеры 14 рс25 бер, управляемые клю !ВBhlc схемы 15 ребер, l,) c hc)!;! pcB3,!ьт;i r,l; Hxo:lhl 1> и Bhlxoды 18 управляемыx ключевы схем 15 соединены с выходами 19 управляемых ключевых схем !8 в схсх!1, отобра)кающу о граф; входы

30 ь) > прав. яе .>! ь.. кл!0>!евы\- cxcxi 18 и pl! пали

3046И I!I!I 11<1 IIИК l ll j),, )B(1 II(7!1(!!> (!I IT

С и; (КОЛЯ)!И (((I с)б()тc! 3 с I <7(7)!c I 1)c) II,)0!I(0,)!! I по 1 ;)кгl T),;

1;, )z, 1.. LI тлктс <, II<7 tjl)!lie 2 п()стуlic)t. г

CÈÃ11Я,1, КОТОP >11! t 1 cl!! сlБЛИ Вc)ÑÒ B il i, i B<)L 110.10)К; И ИС TP !I I I.C()BI 12 i ((. (> Tc) К ГС (> па >1 ) пост ил ют p< 3,.(ьтл Гы р0.3 ы(pi ии )

СТ05! Ппп BCP jkjl! II с) IIO LLI !I II<)rhj -(Рс.)Х i))1 1 L -I Г<)<."Т() si l!E!:I pCб(p, к(7 Г()р l>i(. <Г(7(7 Г)301 i I—

Бенно п()ступ())(71 па Рко.(l>I триггср0<3 (2) II l <. 10

Триг) еры фиксируют !П)лу li. !111 рса, !I гяг„ р03!я f) ыша. Сос Т0Н пис <<1 »,3 Био)>ll!B с! В)пlи.", TpkI3I cðoB 12 и (4 î 31! Icicò прис3: ст!)ис î(71 ()стет)33 юи(ик Вершин и ребер В . (лнпоы р )аыI p!>:Ш(. 1 (7j(1 1 Cp i>l (2 7, !I J) <) БЛ 5! ЮТ и;) <) I3, )ii! 3(Ы.,! )И В< Р )И <И)i а I P;I t CP f,l

1>(— Ы11)pc)BËßÑÛÛ >!I! к;1 ю

;) 0ñð . 17 (3311! Б<>р и;((!Н(л 11 p f1ci "i c I 1)ыс! Б;,)03ьп р ы—

".>.0, (c! iI (9 и В.,О 1c) 11 II 2< ) < к рл !3ляс. lои к.по (е130!1 Г. (. ыы БсpJi! <70()<)33 (.. Гс5{ 20 эг!с кт(ll <)сски и коп1 я I.т. С 001 )30. Г Беппо

Б.;ОДЯ1)11 ((П ВЫКОДЯЫ(1 (8 i lij)c)B,!5Г к.. и! конт<11(т. !3 Г:<7(тп, 25 который пост3 н<)ст и;7 клю!» (О !i (1, Г()о: Всг(I BQ .< ШИЕ (Cpн<)П LSCpJ<(j!!jC. СЛ(),TI! I < i )) (2 It()X(7:(и ГГЯ B С.(и(:»(по il ИО !0)!(L il!Ill 11 C (1;—

Ill()! I!1)l i>i )3 ы > Одо)) открыла(т к i !0 1(, )сpc.3 30

КОтвряй <П)ГН )Л;)рО )CBКИ !t pots(7;(1<»ОСГИ И()Г), I1ЯL "T. ::I ) 13. ;Од 10 )lсрБО)I isСp)1!ilili>I, Б ирOT))BI!())Ы

С Л > <) с i I I X, !" 13!)I Л 13 I >r к О, 10 3) I J) I I I I C f) Я l 2 <71 к (7 В(в

В ЯЕТГ5! 1(, iOH !<> I!L O l)i) I: !)СP:jj l! Il i)l, I I (П Г! I<),1 П РОВСP Кп ИР0 130 Пп 3)ОС ! I ПОСТЫ! i с! Т !1;) КЛ)(7 Ii (C) Ii 3.) ((i!c(7(7<7!! Б Р ПП;Il>l, ТЯК 10 ГС., II

Если сигнал прс)Верки про)3<)ди 3)осгп и рои:ic

Всс l(, 1!О I H и п . Обил ру)кит 1111 0.. (I!0É 1(p(fc 7 Tc113< )ОГЦСИ ВСРШИН(Я, TO Сп! Пл,(00 ЭТ(! .i! ИОСTVIIcr- с<0

B1 П 0 Ш И Н С Л И И С I I Ы Т Л! 111Я 3 i) К Я (i (И В cj 10 1 < ")! .

ПРОВСР к<1 cB5(3i!0cT!f пРис > тс1 B ), юп(и. <. BBP!lljlli

cxcj>(oII «И» 8 Опре, Tc, IHc1 ñÿ как ГБя ifocTB

I3CC>- 3< 7!ll I !I() . 1 сигна lii с Ii)лсвык Выкодов тр 1< г pOB 12 ог- 45 с < TcTl33 ю)п)(к ))ср(п:(п Icpc3 <. кс>II)I «11. J I I»

Т<3 КП М Îi) Pci 3071, (7)с>< )С! 1)С)ОП(И Е 130 P!!i!! Ji >i Г" ИТл К)ТСH КЛ и 01>! Рllс< ТCГВУЮI".(I,I II I I Г))Я )н!): 3)!I

Си! Иял J)0!)Oj) !! I!pi) so, ()I%:OOTE пос)" )ас) и;I

13 >;<7.(О (3 >Pl! I!! Il 1>I, I.OÒÎJ) c)H ()()! 1 <1 (7, ii(C!1

")ОП(II j I It) I< !I l)) 1! (, <) I ()C 3, II j)<)IS,iH(7)I>!i.

I l >)i<.. и<>!(Г> Гс I.l 7 ) !>< Pil! Ifli J! 3.: IPBIS)!5I< i! I)i

f)i ()(. p, > с i!(.сi Б-"-)да- I!I

I3!>I,0,1;;. ) . К,,I 0()I><7! i Ы(i!LГ1В, ЕТ КОИ 1 <1Кт, ПОГ! ,1crс 1 lл 1)Г(i:, <7 (Ы >О 1)ср!0(!11 ГВЧЗ():п)ыс с (7(7I I Я f)3 H((

Г(l! II;), ;r и(к"! 311;.)1<71 !Ср(3 ск r)13 «11< 1(1» 0 и..

l>. (7 Ч (.".<". !>1 "1!» A. J)Ñ,!!I И 3 П рпс CTB7 < И. l:!: .,)1 0> () I i!;I I! 1351 > )11 ci (О\T 1, Ьli i>

j>! I:, т<) пл 13;Од XC i:<>< <<11», L()ОТБСТГ((3i i01!(. )

-,ТО I !)С!) !II I I II<, СП! П Я.) с) П(. (73 С) . (>) Се(Г I » (.

ГБЯЗКОСТИ 13ССХ I! РИС ГТС1 Б> )()II(I)X BCDL(ih!1 а

); СК <3 ()д(! < . . .<. 1:>I :11 С> ()33,(,") (:,":, я, I. я С с Jcj «(Ь ГРЯ()отc!Lт п 0I!(j)0cò клю: (() Б <акте . ; ПО:Ш,*ИС и 1(С! (Пает Сиги<)Г! О(!РОСа РСЭУЛ i c)Òс1 Ifi:!1ÛТя Ji1! 51 I! << i(,1!0<: 7 6. I;СЛ11 BCC. И рИС< Т

C"т 3 i, 7 I I I, I I С 13 C !) 1 1 1 1 I J I >I ()3 5 ) 3 Я 1 l 1, К Г! )(7 .: )) (7 (> " К (7 (,, .

li< .СГС5! II !Icl It!I!)C 7 !!t)HBE!TC)I ГИ: Ii,), !.

I j J) (, (:i! C I 1!:3 0 б f) с I (. Il 11 51

) CTР0ЙГТ130 ДЛ и 0 I j)(;(Г.(CII)151 >;;! (1<)i>ТСРИС I I)i

C j35I3I!t7C! jI I3Cj)0Я Г .100 ГНО! 0 1 Р С)ф

> c) l:0,! II II ci .(r!!r,;It 1 f) II) (. PI>!, !1Р Я!3Л51 С. )Ь(Е> КЛ К)Ii (. (3I f)l, i!O i i) j)!> i -)- Од с >1(3 П р а В ICI) l!H llс).(i 0i., (К!: Il!>I 1(I)B>>O:< ) 31;3Я)i0. i! П па)ОП(»; ТРИ) I C

j) 0i3 lJ ГОС>QII II BП Ы Ы()К (Ы Сооой IS Г> < 1 i, ОТОб р j) k!C < ) I (7 l! (r, ю г р < (f ) 1 I I 1 i, 1 1 B О и C f 7 (J f к f ) О В < 7 -J 1 I— мос !и, ске3!3 «II», Гксы:! «11, 111», к II<7 I с1с)1; рс33 . I I T<)Tß, ()7)л <Я)<<« «) «(<)<".Гс) т Ы,:I 0. Г и<.;1 I>«7

i) iа(iIliI(7LI1ii>l ф > Ill) ; 13t) 1<7>КПОГ Г<. r! i СТРО!!СТ(3 ), и Iii. <>1 ПС IC(3)>1(В)ЯКО,())):3<) I I<73) II:I«â€”

«!!) ((I X Тpi! i I L>p 013 13 p! Li l! Il 1 ()с<(1)л по;(:<.! к) )(пи>! i;

Г ;(ыс <11» )срс3 .". Lыы «1(;11 Ь, ип:и.) Iipo!30(7—

r(t3O(30 1 J! <><()Г(» f)0 j fi j!0,. (7 (sl if 7,, j)t 7 lLй Во и(ел. Верши) графа, при 1(. ы ))ко.lû nf !!3 Л C и И Я 0;(П И К и,! 10 I C I С 0 С Д i I I I C П 1>I С ) I \ Ë C Б Ьl—

:i! jI 1)ЬI::Ода Ыи 3 Я!10 i!11110101ПИ; 1 р и ГГL p013 13L p— пп;н> а Выхс)д клю i<1 предыдущси вершины сосди:)сн с B.(010 клю

ДИНСИ i>I С С;! II!IH I II!>I i! И ВЬ! О, (а ЫИ 3 Я П (7. <(((На 10 ,.I((I) ТРИ) Сr)0 3 ВС))И!ИП, Я (31>(ХОДЫ ЭТИ. КЛ!О IЕI;, ИО (1 < 0 :С)П><»cl 3" 0 (11 СI! f)<)13 15!С)> К К «О" Е13Ы<

c

l3 ;и, I, <7(7 ГВСТ, Гli, )< >п)1)к СкС\! 11, I I I».

Составi:: елв В. К. Озерин

Редактор Б. С. Нанкииа Гекреи А. А. Кагиыгииикова Кор ск-.;!; T. А. Китаева

Закал 178;) 6 Или. Л 4! Гиратк 473 Полиис; оi

Ц11ИИГ1И Когиитета по делам изобрегеиий и огкрып, и ири Сове с Ми гисгров СССР

Москва, уК-35, Ра1гиская иай., д. 4 Б

1 ипо!раг иии пp. Сии\ I:овд, 2