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

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

Цель изобретения - поБьшшиие точности определения количествекиой ры связанности графа,,

На. фиг о 1 Г1редстазлен.а функцис- нальная схема устройства; на фиг 2 - функциональная схема блоки сравне-- ния; на фиг. 3 - граф и его ): смежности.

Устройство СОД6ФЖНТ матрицу р;.зь ;в ром uxn триггеров , где п - ,ГШНЕ;. ный piasMep матрицы моде:- лируемого Г1)афа5 элементы И 2 нет. Ной матрицы элементов И, uepiiyio групн}/ элементов ИЛИ .3, э.пемент Pi. 4,, эле;-- менты И 5 второй матрицы :;лементов Ид элементы 6 задержки, формироват „7 импульсов э счетчики 8, блок 9 cpai нения, блок 10 отображения э элемс н- ты ИЛИ 11 второй ругл1ы,, элемент ИЛИ 1.2 третьей груп.пы,, вход 13 нуления устройства.

Блок 9 сравнения содерлгит лбф;}ь: 1-; элемент ИЛИ 4, элементы 5 заде ;-Ж - кИэ счетчик 16 с перзого ло iv -l- -i, узлы элементов И 17, элемекть: 8 сравнения, триггеры 19, второй элемент ИЛИ 20 5 элемент И 21.. эл1Эг.;елт НЕ 22, n+2-й узел элемент.:)в И 23, дешифратор 24„

Формирователь 7 импульсов лрел,- ставляет собой дифференциругс-шую .де- почку.

Блок 10 отобра:ке} ия со.лер7лит i световодов 5 кажды й н;з которых со;)т- ветствует номеру верпи}-1ы ;.рафа., 1:0 мисегментные инди.кат 0ры, на которых отображается MnHHMajTbiioe коли- честзо ребер, име.юше.е вершинами п графе индикатор 5 отобра:ка оций связанности графа.

Устройство работает следующим соразом.

На такте t. по сигналу на вход 13 происходит установка в Hyj:eBoe состоя 1ие триггеров 1, счетчиков 8,, счетчика 16, триггеров 9,

На такте t на установочные нхоi

р},1 триггеров 1 матрицы подается по-- тенцлал логической е диницы илг; Hyj.i}i. определяемый значениями соответст1-;у - ющих элементов матрицы смежггости исследуемог о .г рафа , Однов:оеменно ;;а тякте to определяется на.лмчие свя:;а:

- 1- r-

-

50

госуги первой вегллины го всеми ос- та..

Если триггеры 1 :фуппы н.аходятся и единичном с;ос 1Ч)яиии. то на выхо- элементов ИЛИ 3 - потенциал логи- ;еской единицы.., на выходе элемента

II4 - потеН1;иал лс гкчсской ед1 ницьи Ма третьем входе слска 10 отображе- i .7i появляется сиг нал 5 свидетельст- гующкй о том, что кгследуемый граф я :1яется свя:;аннр,в-, Если не все рип сры 1 грууп1ы, а только 1--й триггер 1 и.ах о ди т с я ; ег ,иничпом со стоя- п;и5 тогда сигт1а.п с его выхода по- г/гупает на соотие ству;01ций элемент ГиН 3, сигнал с которого поступает 1;;1. эт емепты И 2 1--й строки, Если 1 риггер 1 i -ч стрс. ки j-ro столбца :-1,;:тридь находится в ед,иничном состоянии, то сигнап с него поступает чурез соответствупшлй элемент И 2 на

;од i-TO э.ламе:;та ИЛИ 3, через ко- орь1Й сигнал пост л1ает па элемент I 4 и на вхо,ды эл(ь;ентов И 2 j-й ст-роки матрицы.

1 л;т;и граф связан то в результа- I e таких нереключ эний на выходе элемента И 4 имеется си1 1иал о том, что граф связан. В противном случае граф lie является связа П ;лгм.

В слул;;.е если граф связан, сигнал с вькод.а эламепта И 4 поступает на вход фсрмирователч / импульса с вы ;(Jдa которого с.иг тг.л в виде единич- г.ого импульса, lepss первый элемент 6 задержки пос:ту;:ает па входь: соот-- вс:тствугош,их элементов И 5 первого с толбца матрицы и тфуппы элементов п.. Если триггеры 1 группы находятся ;; ел,ипр1чпо состоянии 5 то сигналы L; выхода э,г.;е1че .1ггов И 5 первого столб- li..: матрицы г;с;ступа1от па счет1 ый вход (.: ;)О 1лзстст.вую1Цих счетчиков 8 „

С В1гхода первого .элемента 6 за- .:;ержки поступает па вход сле- л.пощего э.пе:г.1спгга 5 задержки г: далее а; ;ию;п1чны; образом опрашивает ся со- ;и1ржимое всс:х слсдуюи их Т15ИГ1-еров 1 по С 1 олбцам;,

Содержиг--:С1(; счетчиков 8 по(-;ле полного цикла опрос;; 1.:оотзетствует ко- лпчеству еди1гип го1:трочно в атрице смежности (количесттгу ребер ,нринад- лежащих кажд,ой вер;иино),

С выхода пост;ед: его элемента 6 задержки единичнь;й им;;ульс поступает :,-1 первый вход э; CMcirra ИЛИ )4, с .сда которого сп noci-упает на эле- ;.:ент 15 задержкр; и записывает единицу в счетчик 16. Сигналы с выходов счетчика 16 поразрядно поступают на первые входы соответствующих элементов И 17. На вторые входы элементов И 17 поступает сигнал с выхода пер- вого элемента 15 задержки.

С выходов элементов И 7 содержимое счетчика 16 поступает на первую группу входов первого элемента 18 сравнения. На вторую его группу вхо- дов поступает содержимое счетчика 8 соответствующее количеству ребер инцидентных первой вершине. При равенстве содержимого счетчика 8 и - 16 на выходе первого элемента 18 сравнения появляется сигнал логической единицы, который изменяет состояние первого триггера 19 на противоположное. Сигнал логической единицы с его нулевого выхода поступа- ет на первый вход первой группы блок 10 отображения и засвечивает первый светедиод, свидетельствующий о том, что минимальное количество ребер имеет первая вершина, и на первый вход элемента ИЛИ 20, с выхода которого он поступает на входы элементов И 23 на другие входы которых поразрядно поступает содержимое счетчика 16, и разрешает прохождение содержимого счетчика 16 на вход дешифратора 24

С вьсхода дешифратора 24 дешифрованное содержимое счетчика 16 поступает на вторую группу входов блока 10 отображения. На устройстве 10 отображения отображается содержимое счетчика 16 в десятичном коде, соответствующее минимальному количеству ребер, имеющих вершину в графе.

Сигнал с выхода элемента ИЛИ 20 поступает на вход элемента НЕ 22, с выхода которого он поступает на вход элемента И 21, на другой вход которого поступает единичный импульс с последнего элемента 15 задержки и запрещает его прохождение на вход элемента ИЛИ 14.

Если содержимое счетчика 16 не равно содержимому -первого счетчика 8, то на выходе первого элемента 18 сравнения отсутствует сигнал логической единицы и первый триггер 19 остается в исходном состоянии.

После прохождения единичным импульсом второго элемента 15 задерж- ки содержимое счетчика 16 сравнивается с содержимым второго счетчика 8, соответствуюш 1М количеству ребер инцидентных второй верпшне в графе.

5 О

Q

Q

,

5

Далее происходит сравнение содержимого счетчика 6 с содержимым счетчиков 8, соответствующим количеству ребер, инцидентных каждой вершине.

При совпадении содержимого счетчика 16 с содержимым хотя бы одного счетчика 8 после полного цикла опроса единичный импульс с выхода последнего элемента 15 задержки поступает на вход элемента И 21, на другой вход которого поступает сигнал логического нуля с выхода элемента НЕ 22,и прохождение на выход элемента И 21 единичного импульса запрещается. Блок 10 отображения отображает номера вершин, имеющих минимальное количество ребер в графе.

Устройство для определения параметров графа с четырьмя вершинами и матрицей смежности (фиг. 3) работает следующим образом.

На такте t по шине 13 происходит установка триггеров 1, счетчиков 8, счетчика 16 и триггеров 19 в нулевое состояние,

На такте t на установочные входы триггеров 1 матрицы передаются двоичные сигналы, определяемые значениями матрицы смежности исследуемого графа. Состояние первых триггеров матрицы смежности следующее: записывается -

II 1 t1 . mИ|. . Т И,

5 224 132

234

Т) I 11 , гр11П . тII 1 tl

«- -242 - 143

Одновременно на этом такте определяется наличие связанности первой вершины со всеми остальными. В данном случае все триггеры 1 группы находятся в единичном состоянии. На входы элементов ИЛИ 3 поступают с соответствующих триггеров 1 первой строки логические единицы. На выходе элементов ИЛИ 3, элемента И 4 появляется сигнал логической единицы, свидетельствующий о том, что исследуемый граф является связанным, и отображается по третьему входу блока 10 Этот сигнал поступает на вход формирователя 7 импульса, с выхода которого он в виде единичного импульса поступает через первый элемент 6 задержки на входы элементов И 5, в результате этого происходит запись содержимого Тл,л в счетчик 8 первой и второй строки (содержимое счетчика 8 первой строки становится равным 1, содержимое счетчика 8 второй строки - 1); содержимого Т, в счетчик 8 третьей строки (содержимое

счетчика 8 третьей строки с ; ановится равным 1); содержимого Т,,,.в счетчик 8 четвертой строки (содержимое счетчика 8 четвертой строки не изменяется и будет равным О, так как в записан О).

С вь;хода второго элемента 6 задержки первой групшз сигна,г1 в виде единичного импульса поступает на вторые входы третьих элементов И 5 каж- дои строки второго столбца, В результате этого происходит запись содержимого T,j в счетчик 8 первой и третьей строки (содержимое счетчика 8 первой строки становится равным 2 содержимое счетчика 8 третьей строки - 2); содержимог о в счетчи 8 второй строки (содержимое счетчика 8 второй строки становится равнь м 2); содержимого 1241. в счетчик 8 четвертой строки (содержимое счетчика 8 четвертой строки становится рав ньм 1).

с выхода третьего з.темента 6 зг.- держки единичный импульс поступает на входы третьих элементов И 5 кая:- дой строки трет7зего столбца, В ре-- зультз.те этого происходит запись содержимого Т - в счетчик 8 первой и четвертой строки (содержимое чика В первой строки становится равным 3, содержимое счетчика 8 вертой строки - 3); содержимого Tj24 в счетчик 8 второй строки (содержимое счетчика 8 второй строки становится равным 2, так как в T2J4 записан О); содержимого Т,,, - в счетчик третьей строки (содержимое счетчика 8 третьей строки становится равным 3),

Таким образом, во всех очетчиках 8 каждой строки подсчитывается количство единиц в каждой строке и они соответствуют количеству ребер,ин)1к- дентных каждой вершине.

В счетчике 8 первой строки записывается число в счетчике 3 второй строки - 2, в счетчике 8 третьей строки - 3, в счетчике 3 четвертой строки - 2,

Единичный импульс с выхода четвертого элемента 6 задержки поступает на вход элемента ИЛИ 14., с выхода которого он поступает на счетньгй вход счетчика 16 и записывает в И(2м 1. Содержимое счетчика 16 поразрядно поступает на первые входы со- ответствую1цих элементов И 17. На другой вход этих элементов И 17 ПС

ступает сигнал с выхода первого элемента 15 задержки. Содержимое счетчика, равное 1, поступает на пер- вь;й вход перЕ.ого элемента 8 срав- , на второй вход которого поступает содержимое счетчика 8 первой строки, равь:ое 3.

С выхода г ервого элемента 15 задержки единичный импульс поступает на вход второго элемента 15 задержки, С выхода второго элемента 15 задержки единичный импульс поступает на нход третьего элемента 15 задержки и на входы соответствующих элементов И 17„ Далее происходит сравнение содержимого счетчика 16, равного с содвржимь м счетчика В второй строки,равным 2 .

Единич 1ый импул1: С С выхода третьего элемента 15 задержки поступает на вход четвертого элемента 15 задержки и на входы соответствуюгщ х элемер тов И 17, На третьем элементе-- 18 сравнения проис5:одит сравнение содержимого счетчи1:а IS, равного , и содержимого счетчика 8 третьей строки, paBHoi o 3,

С выхода -четвер ого элемента 15 задержки единичный импульс поступает на вход пятого элемента 15 задержки и на в-ходы соответствуюищх элементов И 17, рагфешая сравнение содержимого счетчика 165 равного , и содержимого счетчика 8 четвертой строкИу равного 2.

Единичный импульс с выхода пятого элемента 15 зад(;ржки поступает Tia вход элемента И 21. На первый его вход поступает сигнш-т 1 с выхода элемента НЕ 22, разрешая прохождение единичного и пульса на выход элемента И 21 „ С элемента И 21 он поступает- ла. вход элемента ИЛИ 14 и с его вых1эда записывает 2 в счетчик 16. Дале в начинается второй цикл опроса и сравнение содержи- счетчика 16 с содержимым счетчи- кон 8,

С выхода первогт элемента 15 за- , сигь:ал разрешает сравнение на первом элементе 18 сравнения содержимого счетчика 16, равного 2, -и содержимого счетчика 8 первой строки, равного 3. Они не равны и на выходе первог-э элемента 18 сравнения присутствует сигнал О.

С выхода второго элемента 16 задержки сигнал разрешает сравнение содержимого счетчика 16, равного

2, и содержимого счетчика 8 второй строки, равного 2, на втором элементе 18 сравнения. Они равны, поэтому на выходе второго 18 сравнения ноявляется сигнал 1, Эточ сигнал изменяет состояние второго трип ера 19 на противоположное (записывается 1) ,

Сигнал с выхода второг о триггера 19 засвечивает второй светодиод блока 10 отображения и запрещает третий цикл опроса. Происходит опрос и сравнение содержимого счетчика 16 с содержкмым счетчика 2

третьей строки, не равно 3, то на

но так как вькоде третьего элемента 18 сравнения присутствуе сигнал О,

Происходит сравнение coдepжи ;oro счетчика 16 и содерлэгмого счетчика 8 четвертой строки,. Так как эти содержимые равньл, чстиертьш триггер 19 изменяет состояние иа противоиолож-- ное. Засвечивается четвертый светоДИОД.

с зькода пято; о элемента 15 задержки единичГ1Ь;й iiMHvjrhc поступает на вход элемента И 21 , на другой вход которого поступает сигнал О , запрещаю1ч,ий следуюишй цикл к сравнения. На этом работа устройства заканчиваете, Sia блоке 10 отображения светятся свето/тиод ,; соот- ветствуюп -1е второй и четвертой звр- шинаМэ и число 2, соответствующее минимальному ко.икчестзу ребер, свя- зыва;опдах ,.

Фор м у л а

обре

Устройство дпя опре;;. параметров графов, содорнашее группу из и триггеров, где п - лиией} Ы pa.Tr.iep матрицы смежности мoдeлиpye oгo г ра- фа, матрицу размером п х п триггеров, элемент И, первую матрицу размер п X п элементов И, первую группу из п элементов ИЛИ, формирователь импульсов,, п элементов задерж-си, груп пу из п элемег1тов И, вторую матрицу размером п х п элементов И, выход триггера i-ro столбца j-й строки (,, о дП, j-1J .,п) матрицы триггеров подключен к первому элеме - - та И 1-го столбца j -й С1роки первой матрипы элементов И и к первому входу элемента Г1 1-го столбца J--H строки второй -;агриц:л злеме;1тов И. выход элемента И столбца 1-й строки (, . . , первой матрицы элементов

0

5

Г,

.5

. 5

J

li г.. к i-м входам 1-го и 1- элементов ИЛИ первой группы, выход i-ro 3neN;eHTa И первой строки nepBOii матриц элементов И подключен к перво г входу i-ro элемента ИЛ1-1 nepBofi группы, выход k-ro (k , . . . ,п) триггера групг1Ы подключен к п- -1-му вход-у k-ro элемента ИЛИ первой группы и к первому входу k-ro элемента И Г руппы, выход которого подключен к k-му входу элемента И и к вторым входам элементов И k-й строки первой матрицы элеь ентов И, выход элемента И подключен к входу формирователя импульсов, выход которого гюдключен к входу нервого элe ;eнтa задержки, вход ш-го ( , . , , ,п) элеь1ента за- ,ер;кки подк.пючен к выходу (in-l)-ro элеь;епта задержки, з становочны вход тоиггера i-ro столбпа j-й строки матр1-л1ы тр; ггеров подключен к 1-му входу злемеьпгов 1 трит1Ы смежности гр}-гп1ы устройства, установочный рход i-ro триг гетча rpynniji гюдключен к входу э:1емс ггов ьштрицы смежности u-i-1-и устройства, входы ycTaiiOHKn р nyjib триггеров (aтpи- цы триггеров :. вход1 установки в nynij триггеров группы подключены к входу г.р.чалычой устаг.овки устройства, о т л ; а ю ц; е е с я теМ; ЧТО; с nc,:i.n ){ия точз-юсти оп- редс;тц|;ия количес твенпой меры свя- затп;ости Г| ао;г;, в устройство введе- П1:1 П --; с Ч тчиков, вторая т руппа из п- -го :.:;1С ; ::;;тл ИЛИ. третья группа пз п злс ;с;г:-ол liJBi, блок сравнения и блок о-:-обра: -:счпя 5 входы установки в пуль гчстчи}-. ов ; первый управляю- бло); срар;1епия подключены к входу качс лЫ СЙ установки устройства, Hi-ixc/i па;-;с;)ч; И груп- гг;, по;;кл;очен к перГ) входам первьк злс:.;оптов ИЛИ у-торой и третьей гругтп 5 ;1ыход ггорого элемента И rpyniHbi по;ц-:л;о-1.1еп к второму входу первог о элемента ИЛИ второй группы и к nej4rO rv вход,у второго ИЛИ трс 1 bcf; группы, выход р-го эле- :.К:Пт;1 . групп -:. де р 3. , , , ,П5 под- K :;:40 i к по)1;:ому пходу p-l-ro эле- ;е- :п. И/Л БТОГОЙ группы ; к первому

о з.-;с; СП 1 л ИЛИ третьей груп- п зхсд ::-г-о ИЛИ, , , , ri-i , пторой группы под- : :;;хо:-:у г-1-го элемента )1ЛИ }пп; -:- .:ход п-1-го зле е1:та и пруп;;ь: подключен к счет- .у псрвот о , выхоп

913

элемента И первого столбца -к ст-зеки второй матрицы элементои И подключен к второму входу j-ro элемента 1ПИ третьей группы, выход j-ro элв- мента ИЛИ третьей группы объедине; с выходами элементов И j-й с: роки столцов с второго по п™й второй матри:дь.1: элементов И и подключен к счетному входу j+l-ro счетчика, информационные выходы счетчикоБ с первого по п+1--й подключены соответственно к инфор1 1а ционным входам с первого по блока сравнения;, выход элемента И подключен к yпpaвляющe fy входу блока отображения э выход первого элв - мента задержки подключеп к второму входз первого элемента И Г|)уппы и к вторьпч входам элементов И первого столбца с второй по п-ную ;;троки

второй матрицы злемеп гов И; выход q-ro элемента задержки, где ,,,. п-I3 подключеп к второму входу q-ro элемента И .группы п к вторьпм входам элементов И q-1-го столбиа с первой

по строки второй матрицы эл;:;- ментов И, выход п-го элемента за- дерлжи подключен к второму входу п-го элемента И группы, к :вторым входам элементов И п-го столбпа с первой по п-ную строки второй : .1атэн- цы элементов И и к второму управл ио- щему входу блока сравнения, выходы первой группы блока сравнения подключены к одноименным информационным входам первой группы блока отобра;ке- НИЛ, выходы второй группы С)лока Cjia;;; нения подключены к информацконньгм входам второй группы блока сравнепия при этом блок сравнения сод.ержит п+2 узлов элементов И. п+1 элемент Сравнения, п+1 триггер, Д : ; - та ИЛИ, счетч1-1К, даш5- фра 1 о -1, э:1еь;; 1Г;

410

Hj элемент :, ii+l элемент задержки, причем в блоке сравнения первый уп- Р азляющий вход блока сравнения под- кл очен к входам уста.новки в нуль счетчпка и всех триггеров, второй управляющий вход блока сравнения подключен к перво1 гу входу первого элемета ИШ-1, S-информационный вход., где s 1 5. , „ 3 блока сравнения подклю- ч ен к первому входу элемента сравненияJ выход элемента И подключен к второму входу первого элемента , выход первого элемента ШИ подключен к счетному входу счетчика и к входу первого элемента задержкИ5 пькод v-ro элемента задержки, где v- l , , , „ ,п, подключет к первому вхо- лу vTO узла элемеп ;.-ов И и к входУ ,4-1-го элемента задержки выход п+

0 -f-1-го элеме п:та задержки подключен

первому П+1-ГО узла элементов зад,ержки и к лервом у входу элемента Hj ипформацисиньк выход счетчика подключен к вторым входам узлов элемен- 14)3 И с первого по п+2-Й5 выход s-го узла элсмептсв И подключен к второму входу з-гс элемента сравнения пьгход s-ro элемента сравнения подключен к информационному входу s-ro триггера,, выход s-ro триггера подключен к s-му входу второго элемента И. и к з-му выходу первой группы блока сравн ения, Вз1ход второго элемента И.)М подключен к второму входу п+ +2-ГО узла элемептэв И и к входу элемента НЕ 5 которого подключен к тз-горому входу К, выход n-i-2-го узла элементов И подключен к входу дешифратора, выходы дешиф- pa i opa подключены Р одноименным вы- ход.ам второй 1 рут:ь блока сравот 13

/6

Tlf

Zlh

3L

.dj

1в

/.9

-01

17

18

пшвпца

15

I к..(1

17

Т1/ 7Ь

-9

/

Изобретение относится к вычислительной технике и может быть использовано .для определения характеристик связанности графа, в частности для количественной оценки связанности графа. Цель изобретения повьшение точности определения количественной меры связанности графа. Поставленная цель достигается тем, что устро йство содержит матрицу размером пхп триггеров 1, где п - линейный размер матрицы смежности моделируемого графа, элементы И 2 первой матрицы элементов И, первую группу элементов ШБ- 3, элемент И 4, элементы И 5 второй матрицы элементов И, элементы 6 задержки,формирователь 7 импульсов, счетчики 8, блок 9 сравнения, блок 10 отображения, элементы ИЛИ 11 второй группы, элементы ИЛИ 12 третьей группы, вход 13 обнуления устройства. Устройство позволяет уменьшить вероятность ошибки при определении связанности для графов со значительным числом ребер и существенным разбросом количества связей между вершинами. 3 ил. 3 (Л со ГчЭ о оо

I f Г

тУ

е

Ь

.„.f.

18

;:

L

Л

УГ/

-О

(..

а д б

Фиг.З