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

 

Изобретение отиосится к области вычислительной техники и предназначено для определения в графе циклов длиной 1,2,..., N (где N - количество вершин графа) и вершин, в них участвующих . Изобретение позволяет расширить функциональные возможности устройства за счет определения наличия в графе циклов длиной К (,N ) и вершин графа, в них участвуюптях. Использование предлагаемого устройства исключает необходимость программного поиска циклов в графе, осуществление которого в приемлемое время оказывается невозможным ввиду высокой трудоемкости соответствующего алгоритма. Устройство содержит матрицу I формирователей дуг, блок 2 st

СОЮЗ СОВЕТСКИХ

СОЦИАЛИСТИЧЕСНИХ

РЕСПУБЛИН

А1 (19) (И) (5)) 4 G 06 F 15/20

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

ЫЪ |." .;в

ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССР

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИЙ

К А BTOPCHOMY СВИДЕТЕЛЬСТВУ (21) 3845204/24-24 (22) 11.01.85 (46) 23,08.86, Бюл. 1(31 (72) В, А. Батраков, А. С. Омельченко, С. Л. Вилков, С. В. Назаров, В. И. Сущев и О. М. Береснев (53) 681.333(088.8) (56) Авторское свидетельство СССР

Ф 807836, кл. G 06 F 15/20, 1980 °

Авторское свидетельство СССР

Ф 716043, кл. С 06 F 15/20, 1980. (54) УСТРОЙСТВО ДЛЯ ИССЛЕДОВАНИЯ

ГРАФОВ (57) Изобретение относится к области вычислительной техники и предназначено для определения в графе циклов

1 2 .. ° N (где Ю вЂ” количество вершин графа) и вершин, в них участвующих. Изобретение позволяет расширить функциональные возможности устройства за счет определения наличия в графе циклов длиной K (K 1 и ) и вершин графа, в них участвующих.

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

1252791 уtTðëítIåíIIë, генератор 3 импульсов, К х М тригг| ров 4 и элементон И 5 матр|гцы формирователей дуг, первую группу б из М элементов ИЛИ, первую 7 и вторую 8 группы из II элементов И, матрицу 9 формирователей путей, включающую К x N элементов, Изобретение относится к вычислительной технике и может быть использовзнс при исследовании графов.

Цель изобретения — расширение функциональных возможностей устройства за счет определения наличия в графе циклов длиной K (k=1, М ) и вершин графа, н них участвующих.

В теории графов под циклом понимается некоторый путь, начальная и конечная вершины которого совпадают. Длиной цикла называется число дуг, входящих в него. В общем случае в графе могут бьггь циклы различной длины. Минимальная длина цикла равна единице (вершина имеет петлю), максимальная — М (гамильтонов цикл) .

Если Hp. накладывается условие однократного вхождения дуги в цикл, То петля может считаться циклом длиной 1,2, .. °, N, Информацию о наличии в графе циклов длиной h (K=I, N ) содержит дистанционная матрица К -го порядка 1,.

Она представляет собой квадратную матрицу размером М х К, элементы которой есть "I" и "=". Наличие "! на пересечении i-и строки и j-ro столбца свидетельствует о том, что иэ

i-й вершины в j-ю нершину графа есть путь длиной k . Следовательно, наличие "I на главной диагонали дистанционной матрицы н i-й строке снидетельствует о наличии пути длиной К из i é вер|сины в нее саму, т.е. цикла длиной К . Тогда, формир. я дистанцион ые матр "II »,, 6 г,..., н и анализируя диагональные элементы указанных матриц можно определить наличие циклов длиной К и какие вершины в них входят. Очевидно, что матрица смежности графа представлякаждый из которых содержит триггер

I0 и перную ll и вторую 12 группы элементов И, вторую группу 13 из элементов ИЛИ, элемент ИЛИ 14 (К+1)— разрядный сдвигающий регистр 15, группу 16 N -разрядных сдвигающих регистров. 2 ил. ет собой дистанционную матрицу первого порядка 5|.

Для нычисления элементов дистанционных матриц более высоких порядс

5 кон С" используется следующая

fJ рекуррентная формула:

С" =V С,"„ Ла„., К=2,И, (1) ч ||1 где а — элемент матрицы смежности

VI

10 графа> знак дизъюнкции;

Л вЂ” знак конъюнкции, На фиг, 1 приведена структурная схема устройства для исследования графов; на фиг. 2 — структурная схема блока управления, Устройство для исследования графов содержит матрицу 1 формирователей дуг, блок 2 управления (распре20 делитель импульсов), генератор 3 импульсов, триггеры 4 матрицы формирователей дуг, элементы И 5 матрицы формирователей дуг, первую группу

6 элементов ИЛИ, первую 7 и нторую 8

25 группы элементов И, матрицу 9 формирователей m тей, триггеры 10 матрицы формирователей путей, первую 1! и вторую 12 группы элементов И матрицы формирователей путей, вторую

30 гр нпу 13 элементов ИЛИ, элемент

ИЛИ 14, (К+1)-разрядный сдвигающий регистр 15, группу 16 М -разрядных сдвигающих регистров, элемент ИЛИ 17 блока управления (БУ), первый IS

35 и второй 19 элементы И БУ, первый 20, второй 21, третий 22, четвертый 23

М-разрядные кольцевые сдвигающие регистры БУ, первый 24 и второй 25 элементы задержки БУ, группу 2Ь

40 элементов И БУ, группу 27 формирователей импульсов БУ, третий 28, четвертый 29, пятый 30, шестой 31, седьмой 32 и восьмой 33 элементы за1252 791 держки БУ, группу 34 элементов задержки БУ, девятый элемент 35 задержки БУ, второй 36 и третий 37 выходы БУ, третью группу 38 выходов

БУ, четвертый выход 39 БУ, вторую 5 группу 40 ныходов БУ, пятый выход 41 bY, второй 42 и первый 43 входы БУ, четвертую 44 и первую 45 группы выходов БУ, первый 46 и шестой 47 выходы БУ, вход 48 запуска генератора импульсов, выход 49 генератора импульсов, вход 50 запрета генератора импульсов, вход 51 запуска устройства.

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

Первоначально в триггеры 10 матрицы 9 формиронателей путей и в триггеры 4 матрицы I формирователей дуг в виде матрицы смежности А заносится 20 исходная информация об исследуемом графе ° При этом в единичное состояние устананлинаются лишь те триггеры

10;; и 4, (i, j=l,È, где N — количество вершин графа), для которых в 2 исследуемом графе есть дуга из вершины i н вершину j.

С поступлением на второй вход

42 БУ пускового импульса с входа

5I устройства ace разряды первого 20, второго 21 третьего 22 и четвертого 23 N -разрядных кольцевых сдвигающих регистров, а через первый выход

46 БУ (11+1)-й разряд (И+1)-разрядного сдвигающего регистра 15 и H -е разряды группы 16 N -разрядных сдвигающих регистров устанавливаются в нулевое состояние. Через интервал

/ времени,, определяемый параметрами первого элемента 24 задержки Бу, появляется импульс записи номеров вершин, входящих в цикл, который, пройдя через элемент ИЛИ 17 БУ, выдается на третий выход 37 БУ ° Этот импульс открывает по первому входу элементы

И первой группы 7, на вторые входы которых поступает сигнал с единичных выходов соответствующих триггеров

10; (i=1, и ) матрицы 9 формировате Лей IIYTeA. Состояние этих триггерон50 переписывается н N -е разряды группы 16 И -разрядных сдвигающих регистров, при этом для любого i(i I И ) наличие единицы в Й -м разряде i-го

N-разрядного сдвигающего регистра со->> ответствует тому, что в исследуемом графе i-я вершина входит в цикл длиной один, Через ин гервал времени, определяемый параметрами четвертого элемента 29 задержки БУ, Я -е разряды первого 20 и четвертого 23 II-разрядных кольцевых сднигающих регистров БУ, первый разряд второго И разрядиoro к .-;ьцевого сдвигающего регистра 21 БУ и (N-I)-й разряд третьего И -разрядного кольцевого сднигающего регистра 22 БУ устананлинаются в единичное состояние, а через интервал 7, определяемый параметрами пятого элемента 30 задержки БУ, на втором выходе 36 БУ появляется сигнал, который поступает «а вход 48 запуска генератора 3 импульсов °

Генератор 3 импульсов начинает вырабатывать импульсы с периодом Т,, которые с выхода 49 генератора 3 поступают на первый вход 43 БУ. С нторого входа 42 БУ они поступают н цепь сдвига третьего H -разрядного кольце во го сдвигающе го регистра 22

БУ и на вход третьего 28, шестого

3l, седьмого 32 и восьмого 33 элементов задержки БУ, на выходе которых по ним формируются сигналы через интервалы времени,, -, и соответственно. С поступлением первого импульса на первый вход 43 БУ начинается цикл работы устройства по

1 формированию значения элемента С я дистанционной матрицы второго порядка, определяемого выражением (1) .

По первому импульсу генератора 3 импульсов единица из (N — 1)-го разряда третьего М -разрядного кольцевого сдвигающего регистра 22 БУ сдвигается в Й -й разряд. Пояг.-ение сигнала на единичном выходе N -го разряда указанного регистра осуществляют сдвиг единицы из Н -го разряда перного Н -разрядного кольцевого сдвигающего регистра 20 БУ н 1-й разряд.

Высокий потенциал с единичного выхода I-го разряда регистра 20 через первый выход первой группы И 45 вы" ходов БУ поступает на вторые входы первых элементов И 11 первой строки матрицы 9 формирователей путей, тем самым разрешая поступление содержимого триггеров 10 первой строки матрицы 9 формирователей путей (первой строки дистанционной матрицы 6< ) через вторую группу 13 элементов

1252

Г посту;1лением второго импульса от генератора 3 импульсон единица 45 из N -го разряда третьего N -разрядно го кольцевого сдви гающе го ре гистра 22 БУ сдвигается в первый разряд.

Состояние первого Й -разрядного кольцевого сдвигающего регистра 20 БУ не изме цяетгя. По импульсу, выдаваемому чере з <1, осуществляется сдвиг еди1нщы «1 первого разряда четнертого 11 -разрядного кольцевого сдвигающего регистра 23 БУ во второйразряд.

Прн поя в«енин Bb1сокого потенциала на единичном выходе второго разряда указанного регистра второй формироИ1!И нз 11<-рвы<- входы второй группы 8 з l e; le l l т о н И, Через ин гервач времени <,, опре— д< ляемый парам< трами седьмого элемента 32 задержки BY, ньщается им5

tlvJ1Lc по к этором" осуществляется сдвиг единицы из И вЂ” го разряда четнер1ого И -разрядного кольцевого гднигающ< г регистра 23 БУ н первый

pB1ряд. При 11< явлении высокого пот< нциала на единичном выходе первого ра эряда уха анно гo ре гистра первый ф»рм11равате1ь группы 27 формироватеJlpй импульгон BY вырабатывает сигнал, к»торый Icp<.1 первый выход второй 15 группы 40 выходов БУ поступает на вг»рыг . ходы элементов И 5 первого

< "г»лб:1;i матрицы l формирователей дуг, iBм < амым ра1решая поступление содержимого триггеров 4 первого столб- 20

11а матрицы I:формирователей дуг (элементов а ) через первые входы

VI соответствующих элементов И 5 и первую групп; 6 элементов ИЛИ на вторые

B <эды втпр<эй групг1ы 8 элементов И. 25

Вт»рая гpyIIIIB 8 элементов И и элемент 11эП! 14 реализуют логическую функцик (1) . В рассматриваемый момент времени на выходе элемента ИЛИ 14

2 будет получено значение элемента С,1 30 дистанционной матрицы о . 3To значе1 ние заносится н (N+1) и разряд (И+1)— разрядного сднигаю1<1его регистра 15.

Через интервал времени onpeId дгляемый параметрами восьмого элем<- 1т» 33 задержки БУ, выдается импульг, ко орый через пятый выход

41 БУ поступает на вход сдвига (N+1)разрядного <.двигающего регистра 15.

При этом значение полученного элемента Г„ сднигаэтся иэ (!<1+))-го разряда (й+l)-разрядного сднигающего регигтра 15 в 11 -й разряд.

791 в датель группы 2 7 формирователей ими lbcoB Ьу вырабатывает сигнал, кот 1рый через второй ныход второй группы 40 ныходов БУ поступает на вторые

1 ходы элементов И 5 второго столбца матрицы 1 формирователей дуг, тем <.мым разрешая поступление содержимого триггеров 4 второго столбца

b

;1< рвую группу 6 элементов ИЛИ на вторые входы нгорой группы 8 элемен: »п И, В рассматри1<аемь1й момент рремен<1 на выходе третьегo элемента

11%1 14 будет получено значение элемента С, дистанционной матрицы 5, которое будет запомнено в (!1+1)-разрядном сднигающем регистре 15.

При выработке генерагором 3 импульсов третьего> четвертого, М-ro импульсов устройство работает аналогично. После поступления на вход сдвига (И+1)-раэрядногп сдвигающего регистра 15 1

По !1 -му импульсу, выработанному генератором 3 импульсов, после сдвига в (К вЂ” 1)-м разряде третьего М разрядного кольцевого сдвигающега ре гистра 22 БУ появляется единица.

Высокий потенциал с единичного выхода (М-1)-го разряда укаэанного регистра поступает на первые входы группы 26 элементов И БУ. На вторые входы указанной группы элементов поступают потенциалы с единичных выходов первого М -разрядного кольцевого сдвигающего регистра 20 БУ.

Через интервал времени <, определяемый параметрами шестого элемента

31 задержки БУ, на третьи входы группы 26 элементов И БУ поступает сигнал. В рассматриваемый момент времени на втором входе имеет высокий потенциал только первый элемент группы 26 элементов И БУ. В результате íà его выходе формируется импульс, который через г1ерный выход четвертой группы 44 выходов БУ сбрасывает в нулевое состояние триггеры 10 первой строки матрицы 9 формирователей путей. Этот же импульс поступает на вход перного элемента группы 34 элементов задержки BY.

Через интервал времени ь опре<оу деляемь<й параметрами укаэанного элемента задержки, импульс чере первый, 1252791 ответствующих единичных выходон (к +1) -разрядн го сдвигакп33его регистра !5. Таким образом, содержимое 10 указанного регистра записывается в триггеры 10 первой строки матрицы 9 формирователей путей, т.е. цикл по формированию первой строки дистанционной матрицы «а этом завершается.

Следует отметить, что значения элементов первой строки дистанционной матрицы меньшего 33а единицу порядка (в данном случае S ) не сохраняются, поскольку в дальнейшем они не исполь- 20 зуются.

Аналогичным образом формируются и запоминаются вторая, третья,..., М-я строки дистанционной матрицы о

С поступлением Н„(N — 1)+1 импулг,са 25 в Н -м разряде первого Н вЂ разрядно кольцевого сдви гающе го ре гис rpa 20 БУ появляется единица, и через интерНаЛ ВРЕМЕНИ с7, ОПРЕДЕЛЯЕМЫЙ ПаРа метрами второ го элемента 25 э аде ржки БУ, осуществляется сдвиг из первого разряда второго Н -разрядного кольцевого сдвигаюшего регистра 21 БУ во второй разряд.

С поступлением от генератора 3 импульсов М импульсов в матрице 9

z формирователей путей будет записана дистанционная матрица 33 . Теперь

2 осуществляется эапомггнание вершин, входящих в цикл длиной 2.

С этой целью сигнал с выхода третьего элемента 28 задержки БУ поступает на второй вход второго элемента

И 19 БУ, который в рассматриваемый момент времени открыт по первому входу высоким потенциалом с единичного выхода (l4 — 1)-ro разряда третьеге !3l -разрядного кольцевого сдвигающего регистра 22 БУ, а по третьему входу — высоким потенциалом с единичного выхода Н -го разряда первого

Н-разрядного кольцевого сдвигающего регистра 20 БУ.

35 l3p3. поступлении импульса с номерс.м N (N — 1) с выхода второго эле7 мента И 19 БУ на первый вход первого элемента И 18 БУ он ч»рез четвертый вь3ход 38 БУ передается на запреща40 юший вход 50 генератора 3 импульсов и выработка импульсов прекращается.

После записи в Н -е разряды группы

l 6 1l -разрядных сдвигающих регистров э:.с:.Зе33т главной диагонали дистанционной матрицы с3 в указанных регистрах будет содержаться информация о верп3и33ах > входящих в циклы длиной один> два, ..., М . Работа устройства по исследованию графа на этом завергггается. выход третьей группы 38 выходов БУ поступает на вторь3е входы вторых элементов И 12 первой строки матрицы 9 формировате33ей3 путей. На первые входы вторых элементов И 12 каждой строки матрицы 9 формирователей путей поступают сигналы с сов ц но, т. е. в рассматриваемый момс нт н! ем»33и содержимое М -х разрядов будет пер»мешено в (N-1)-е разряды.

Через интерва 3 времени с, определя»;г .й параметрами девятого элемента 35 зад»ржкн БУ, этот же импульс через эвс:мент ИЛИ 17 БУ выдается на третий н3:.«3д 37 БУ. Этот импульс открывает по второму входу элементы И первой группы 7, на первые входы которых поступают сигналы с единичных выхолов соответствующих триггеров

10;, (i=l, Н ) матрицы 9 формирователей путей, и состояние этих триггеров переписывается в М -е разряды группы 16 Н -разрядных сдвигак33цих регистров, при этом для любого

i(i=1,Н ) наличие единиць3 в М -м разряде i-го М -разрядного сдвигаюш»гQ рс г Зстра соответстнус т тому, что 33 исследуемом графе 1 — я вершина входит в цикл длинс и 2.

Работа устройства по определению

33 3мс ров в»ршин, входягцих в циклы длиной три,...,Н, протекает аналоi l3ЧГ3о

С постуггл»нием от генератора 3

l3:3пу3:ьсов М (N-2)+! импульсов в

М-.l разряде второго Н -разрядного ког3ыгс>ного сдвигающ»l о регистра

21 БУ появляется единица и на второй вход первого элем»нга И 18 БУ начи33ас 3;òñ>»òóïà гь разр»ша>вещии высокий потенциал.

Ф о р м у л а и з о б р е т е н и я

На выходе второго элемента И 19 БУ появляется импульс, который через 5S шестой выход 47 БУ осуществляет сдвиг содержимого всех Н -разрядных сдвиговых регистров группы 16 на разряд

Устройство для исследования графов, содержащее генератор импульсов, первую группу элементов И П1> первую и вторую группы элементов И, блок управления, матрицу формирователей

9 1252 дуг, причем блок управления содержит группу элементов задержки, а матрица формирователей дуг — триггеры и элементы И, выходы триггеров матрицы формирователей дуг соединены с первыми входами одноименных элементов И матрицы формиронателей дуг, выходы элементов И каждой строки матрицы формирователей дуг подключены к входам соответствующих элемен- 10 тон ИЛИ первой группы, о т л и ч а— ю щ е е с я тем, что, с целью расширения,функциональных воэможностей устройства за счет определения наличия в графе циклов длиной K (K=1,N> 15 где k — количество вершин н графе) и вершин графа> в них участвующих, в устройство введены вторая группа элементов ИЛИ, (Й+1)-разрядный сдвигающий регистр, группа N -разрядных 1о сдвигающих регистров, матрица формирователей путей, содержащая триггеры, первую и вторую группы элементов И, а блок управления дополнительно содержит элемент ИЛИ, первый и нт 1рой элементы И, первый, второй, T ðåòèé и четвертый М -разрядные сднигающие кольцевые регистры, первый, второй, третий, четвертый, пятый, шестой, седьмой, восьмой, девятый >лементы 30 задержки, группы элементов И, группу формирователей импульсов, причем выходы элементов HJIH первой группы соединены соответственно с первыми входами элементов И второй группы, выходы триггеров матрицы формирователей путей подключены к первым входам соответствующих элементов И первой группы матрицы формирователей путей> выходы элементов И первой 40 группы каждого столбца матрицы формирователей путей соединены с одноименными входами соответствующих элементов ИЛИ вто,ой группы, выходы которых подключены к первым входам 45 элементов И второй группы, выходы элементов И второй группы соединены с входами элемента ИЛИ соответственно, выход элемента ИЛИ подключен к входу установки н "1 (Й+1) — го раз- s0 ряда (N+1)-разрядного сдвигающего регистра, группа выходов которого соединена с первыми входами соответствующих элементов И второй группы каждого столГца матрицы формирователей 55 путей, выходы элементов И второй группы матрицы формиронателей путей подключены к входам установки в "1"

791 1О одноименных триггеров матрицы формирователя путей, выходы триггеров матрицы формирователей путей, расположенных на главной диагонали, подключены к первым входам одноименных зле\ ментов И первой группы, выходы которых соединены с входами устанонки н

"1" Й -го разряда соответствующего

Й -разрядного сдвигающего регистра группы, входы установки в О" первого, второго, третьего и четвертого

Й-разрядных кольцевых сдвигающих регистров блока управления объединены с входами первого, четвертого, пятого элементов задержки блока управления и подключены к входам установки в "О" (N+1)-го разряда (Й+1)-разрядного сднигающего регистра, N -х разрядов

Й-разрядных сдвигающих регистров группы и к входу запуска устройства, выход четвертого элемента задержки блока управления подключен к входам установки н 1 Й -го разряда первого Й -разрядного кольцевого сдвигающего регистра блока управления, первого разряда второго Й -разрядного кольцевого сдвигающего регистра блока упРавления, (Й вЂ” 1)-го разряда третьего N -разрядного кольцевого сдвигакп",его регистра блока управления и

М-го разряда четвертого Й -разрядного кольцевого сдвигающего регистра блока управления, выход пятого элемента задержки блока управления подключен к входу запуска генератора импульсов, выход которого подключен к входам третьего, шестого, седьмого и восьмого элементов задержки блока управления и к нходу сдвига третьего Й -разрядного кольцевого сдвигающего регистра блока управления, выход восьмого элемента задержки блока управления подключен к входу сдвига (Й+1)-го разрядного сдвигающего регистра, выход (hJ-1)-ro разряда третьего N -разрядного кольцевого сдвигающего регистра блока управления подключен к первым входам элементов И группы блока управления и к первому входу второго элемента И блока управления, нторой вход которого подключен к выходу третьего элемента задержки блока управления, единичный выход N — го разряда третьего Й -разрядного кольцевого сдвигающего регистра блока управления полкпючен к входу сдвига первого N -разрядного кольцевого

11 12 сдвигающего регистра блока управления, каждый выход группы выходов которого подключен к второму входу соответствующего элемента И группы блока управления и к вторым входам элементов И первой группы соответствующего столбца матрицы формирователей путей, выход шестого элемента задержки блока управления подключен к третьим входам элементов И группы блока управления, выходы которых подключены к входам соответствующих элементов задержки группы блока управпения и к входам установки в "О" триггерон соответствующего столбца матрицы формирователей путей, каждый ны. од группы выходов элементов задержки группы блока управления подключен к вторым входам элементов И второй группы соответствующего столбца матрицы формирователей путей, выход седьмого элемента задержки блока управления подключен к входу сдвига четвер1ого )1 -разрядного кольцевого сднигающего регистра блока управления, выходы каждого из разрядов которого соединены с входами одноименных формирователей импульсон группы блока управления, выход каждого формирователя импульсов группы блока управ5279) ) 2 леиия пс ..;,лючеtt к вторым входам элементов И с-оответствуюшей строки матрицы формирователей дуг, единичный выход )) -го разряда первого N -pagряцного кольцевоro сднигающего ре5 гистра блока управления подключен к нходу второго элемента задержки блока управления и к третьему входу второго элемента И блока управления, ip выход которого соединен с входом де нято го элемента задержки блока управления, с первым входом первого . элемента И блока управления и с входами сдвига группы N -разрядных сднигающих регистров, выходы первоro и девятого элементов задержки блока управления подключены к соответствующим входам элемента ИЛИ блока управления, выход которого подключен к вторым входам элементон И первой группы, выход второго элемента задержки блока управления подключен к входу сдвига второго М -разрядного кольцевого сднигающего регистра блоg5 ка управления, выход Н -разряда которого соединен с вторым вхо дом первого элемента И блока управления, выход первого элемента

1) блока 5правления соединен с

Bxo:1oM запрета генератора импульсс и.