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

упрлнления, генератор 3 импульсов, N X N триггерон 4 и элементов И 5 матрицы формирователей дуг, первую группу 6 из N элементов И.ГТИ, первую 7 н вторую 8 группы из U элементов И, матрицу 9 формирователей путей, гжлючающую fJ X N элементов.

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

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

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

о порядка Ь.

Она представляет собой квадратную матрицу размером N х N, элементы которой есть 1 и

Наличие 1 на

пересечении i-ti строки и j-ro столбца свидетельствует о том, что из i-й вершинь в j-ю вершину графа есть путь длиной k . Следовательно, наличие I на главной диагонали дистанционной матрицы в i-й строке свидетельствует о наличии пути длиной k из i-й вершины в нее саму, т.е. цикла длиной К, Тогда, формируя дистанционные матрицы ,Sj,...,Sf, и анализируя лиагональнь1е элементы указаннт.гх матриц можно определить наличия цик-гюв длиной К и какие вер- гпины в них входят. Очевидно, что матрица смежности графя представлякаждый из которых содержит триггер 10 и первую 11 и вторую 12 группы элементов И, вторую группу 13 из N элементов ИЛИ, элемент ИЛИ 1А (N-t-1)- разрядный сдвигающий регистр 15, группу 16 N -разрядных сдвигающих регистров. 2 ил.

ет собой дистанционную матрицу первого порядка Б,.

Для вычисления элементов дистанционных матриц более высоких поряд- ков С- используется следующая рекуррентная формула:

ч - v vj . к-гТм, (I)

где - элемент матрицы смежности графа;

V - знак дизъюнкции; Л - знак конъюнкции. На фиг. 1 приведена структурная схема устройства для исследования графов; на фиг. 2 - структурная схема блока управления.

Устройство для исследования графов содержит матрицу 1 формирователей дуг, блок 2 управления (распределитель импульсов), генератор 3 импульсов, триггеры 4 матрицы формирователей дуг, элементы И 5 матрицы формирователей дуг, первую группу 6 элементов ИЛИ, первую 7 и вторую 8 группы элементов И, матрицу 9 формирователей путей, триггеры 10 матрицы формирователей путей, первую 11 и вторую 12 группы элементов И матрицы формирователей путей, вторую rpvnny 13 элементов ИЛИ, элемент ИЛИ 14, ()-разрядный сдвигающий регистр 15, группу 16 N -разрядных сдвигающих регистров, элемент ИЛИ 17 блока управления (БУ), первый 18

и второй 19 элементы И БУ, первый 20, второй 21, третий 22, четвертый 23 N-разрядные кольцевые сдвигающие регистры БУ, первый 24 и второй 25 элементы задержки БУ, группу 26

элементов И БУ, группу 27 формирователей импульсов БУ, третий 28, четвертый 29, пятый 30, шестой 31, седьмой 32 и восьмой 33 элементы за

312

держки БУ, группу ЗА элементов задержки БУ, девятый элемент 35 задержки БУ, второй 36 и третий 37 выходы БУ, третью группу 38 выходов БУ, четвертый выход 39 БУ, вторую группу 40 выходов БУ, пятый выход 41 БУ, второй 42 и первый 43 входы БУ, четвертую 44 и первую 45 группы выходов БУ, первый 46 и тестой 47 выходы БУ, вход 48 запуска генератора импульсов, выход 49 генератора импульсов, вход 50 запрета генератора импульсов, вход 51 запуска устройства.

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

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

10;,

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

С поступлением на второй вход 42 БУ пускового импульса с входа 51 устройства все разряды первого второго 21, третьего 22 и четвертого 23 N -разрядных кольцевых сдвигающих регистров, а через первый выход 46 БУ ()-й разряд (N-i-1 )-разрядного сдвигающего регистра 15 и N -е разряды группы 16 N -разрядных сдвигающих регистров устанавливаются в нулевое состояние. Через интервал времени с, , определяемый параметрами первого элемента 24 задержки БУ, появляется импульс записи номеров вершин, входящих в цикл, который, пройдя через элемент ИЛИ 17 БУ, выдается на третий выход 37 БУ. Этот импульс открывает по первому входу элементы И первой группы 7, на вторые входы которых поступает сигнал с единичных выходов соответствующих триггеров

10

(, N ) матрицы 9 формирователей путей. Состояние этих триггеров первый выход первой группы И 45 выпереписывается в N -е разряды группы 16 N -разрядных сдвигающих регист- ров, при этом для любого i(,N ) наличие единицы в N-м разряде i-ro

N-разрядного сдвигающего регистра со-55мого триггеров 10 первой строки матответствует тому, что в исследуемомрицы 9 формирователей путей (первой

графе i-я вершина входит в циклстроки дистанционной матрицы S, )

длиной один.через вторую группу 13 элементов

0

5

0

Через интервал времени Т , определяемый параметрами четвертого элемента 29 задержки БУ, N-е разряды первого 20 и четвертого 23 N-разрядных кольцевых сдвигающих регистров БУ, первый разряд второго N - разряд)1 ого КС.ьцевого сдвигающего регистра 21 БУ и (N-l)-й разряд третьего N -разрядного кольцевого сдвигающего регистра 22 БУ устанавливаются в единичное состояние, а через интервал Tj , определяемый параметрами пятого элемента 30 задержки БУ, на втором выходе 36 БУ появляется сигнал, который поступает на вход 48 запуска генератора 3 импульсов I

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

5 БУ и на вход третьего 28, шестого 31, седьмого 32 и восьмого 33 элементов задержки БУ, на выходе которых по ним формируются сигналы через интерва,пы времени - , iT, с- и Tj

0 соответственно. С поступлением первого импульса на первый вход 43 БУ начинается цикл работы устройства по формированию значения элемента С„ дистанционной матрицы второго по рядка 8 , определяемого выражением (1).

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

ходов БУ поступает на вторые входы первых элементов И 11 первой строки матрицы 9 формирователей путей, тем самым разрешая поступление содержи$1232

НИИ ия первые HXOAFJ второй группы 8 племеитов И,

Через иигерпап времени

определяемый параметрами седьмого лe.- мента 32 задержки Г)У, вьщается им- пульс, по которому осушествляется сдвиг единицы из N -го разряда чет- nepioro N -разрядного кольцевого сдвигающего регистра 23 БУ в первый разряд. При появлении высокого по- тсициала на единичном выходе первого разряда указанного рег истра первый фсфмироватспь группы 21 формирователей и(пум1ьсон БУ вырабатывает сигнал который через первый выход второй групга 1 40 выходов БУ поступает па игорыс нхо;;ы элементов И 5 первого столбца матрицы I формирователей дуг тем самым разрешая поступление содержимого триггеров 4 первого столб- ца матрицы I формирователей дуг (элементов ау ) через первые входы соответствующих элементов И 5 и первую группу 6 элементов ШТО на вторые входы второй группы 8 элементов Н.

Втг)рая r jyiuia 8 элементов И и элемент И.Ш1 4 реализуют логическую функцию (1). В рассматриваемый момен времени на выходе элемента ИЛИ 14 будет получено значение элемента С,, диста(ционной матрицы Sj . Это значение заносится в ( разряд (N-t-1) разрядиог о сдвигающего регистра 15.

ерез интервал времени ,j, определяемый параметрами восьмого эле- меята 33 задержки БУ, вьщается импульс, который через пятый выход 41 БУ поступает на вход сдвига (N+1) разрядного сдБигающего регистра 15. При этом значение получеиного эле- мента С,, сдвигается из (N + )-ro разряда (N+I)-разрядного сдвигающего регистра 15 в N -и разряд.

С поступлением второго импульса от генератора 3 импульсов единица из N -I o разряда третьего N -разрядного кольцевого сдвигающего регистра 22 БУ сдвигается в первый разряд. Сосголпие первого N -разрядного кольцевого сдвиг ающего регистра 20 БУ не изменяется. По импульсу, вьщавае- мому через L; , осуществляется сдвиг единицы И1 первого разряда четвертого N -разрядного кольцевого сдвигающего регистра 23 БУ во второйразряд При Появлении высокого потенциала на едт1ничном ныходе второго разряда указанного регистра второй формиро7916

ватель rpynm i 27 формирователей ИМПУЛЬСОВ БУ вырабатывает сигнал, который через второй выход второй групы 40 выходов БУ поступает на вторы 11ХОД1.1 элементов Н 5 второго столбца матрицы 1 формирователей Дуг, тем cr .Nu.iM разрешая поступление содержимого триггеров 4 второго столбца матрицы 1 формирователей дуг через первую группу 6 элементов ИЛИ на вторые входы Biopoii группы 8 злемен :оп И. Р рассматриваемый момент времени на выходе третьего элемента 1иШ 14 будет получено значение элемента С, дистанционной матрицы Fj , которое будет запомнено в ()-pa3 рядном сдвигающем регистре 15.

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

По N -му импульсу, выработаиному генератором 3 импульсов, после сдвига в (N-l)-M разряде третьего N - разрядного кольцевого сдвигающего регистра 22 БУ появляется единица. Высокий потенциал с единичного выхода (Ч-1)го разряда указанного регистра поступает на первые входы группы 26 элементов И БУ. На вторые входы указанной группы элементов поступают потенциалы с единичных выходов первого N -разрядного кольцевого сдвигающего регистра 20 БУ. Через интервал времени t , определяемый параметрами шестого элемента 31 задержки БУ, на третьи входы группы 26 элементов И БУ поступает сигнал. В рассматриваемый момент времени на втором входе имеет высокий потенциал только первый элемент группы 26 элементов И БУ. В результате на его выходе формируется импульс, который через цервый выход четвертой группы 44 выходов БУ сбрасывает в нулевое состояние триггеры 10 первой строки матрицы 9 формирователей путей. Этот же импульс поступает на вход первого элемента группы 34 элементов задержки БУ.

Через интервал времени г,, определяемый параметрами указанного элемента задержки, импульс через первы

7

выход групггы 38 В1 1ходов КУ поступает на вторые входы нторвлх элементов И 12 первой строки матри- 9 формирователей путей, fla первые входы вторых элементов И 12 каждой строки матрицы 9 формирователей путей поступают сигналы с соответствующих единичных выходов () -разрядного сдвигающего регистра 15, Таким образом, содержимое указанного регистра записывается в триггеры 10 первой строки матрицы 9 формирователей путей, т.е. цикл по формированию первой строки дистанционной матрицы на этом завершается. Следует отметить, что значения элементов первой строки дистанционной матрицы меньшег о на единицу порядка (в данном случае 8, ) не сохраняются поскольку Б дальнейшем они не исполь зуются,

Аналогичным образом форг-гируются и запоминаются вторая, третья,,,., N-я строки дистанционной матрицы , С поступлением N(N-1)+ импульса в N -м разряде первого N -разрядного кольцевого сдвигающего регистра 20 БУ появляется единица, и через интер- рал времени с 2 , определяемый параметрами второго элемента 25 задерж- ки БУ, осуществляется сдвиг из первого разряда второго N -разрядного кольцевого сдвигающего регистра 21 БУ во второй разряд.

С поступлением от генератора 3 импульсов N импульсов в матрице 9 формирователей путей будет записана дистанционная матрица S- , Теперь осуществляется запоминание вершин, входящих в цикл длиной 2.

С этой целью сигнал с выхода третьего элемента 28 задержки БУ поступает на второй вход второго элемента И 19 БУ, который в рассматривае1 1й момент времени открыт по первому входу высоким потенциалом с единичного выхода (W-l)-ro разряда третьего N -разрядного кольцевого сдвигающего регистра 22 БУ, а по третьему входу - высоким потенциалом с единичного выхода N -го разряда первого -разрядного кольцевого сдвигающего регистра 20 БУ,

На выходе второго элемента И 19 БУ Устройство для исследования грапоявляется импульс, который через 55.фов, содержащее генератор импульсов,

шестой выход 47 БУ осуществляет сдвигпервую группу элементов ШШ, первую

содержимого всех N -разрядных сдви- и вторую группы элементов И, блок

говых регистров группы 16 на разрядуправления, матрицу форм 1ропателей

j 10 15 0

5 0

0

5

0

791Н

ВЖ ВО, т, о, в рассматриваемый м 1мент яремсии содержимое N -х разрядов будет перемещено в (-l)-e разряды. Через интервач времени Г , определя- гггь й параметраьш девятого элемента 35 за;;ержки БУ, этот же импульс через эпемпнт ИЛИ 17 БУ выдается на третий в.;х()д 37 БУ. Этот импульс открывает по второму входу элементы Ч первой rpynni.i 7, на первые входы которых поступают сигналы с единичных вы- соответствуюЕДИх триггеров 10;; (i l, N) матрицы 9 формирователей путей, и состояние этих триггеров переписывается в N -е разряды группы 16 N -разрядных сдвигающих регистров, при этом для любого i(,N ) наличие единицы в N -м разряде i-ro fj -разрядного сдвигаю- шего регистра соответствует TONry, ч 1-о п исследуемом графе i-я вершина входит в цикл длиншЧ 2,

Работа устройства по определению } OMt-poB вершин, входящих в циклы длиной три,.,,,N, протекает аналогично ,

С поступлением от генератора 3 импу.кьсов N(N-2)-t-l импульсов в N-1 разряде второго N -разрядного кольперого сдвигающего регистра 21 БУ появляется единица и на второй вход первого элемента И 18 БУ начи- наг.г поступать разрешающий высокий потенциал,

iTpi поступлении импульса с номером N (N-) с выхода второго элемента И 19 БУ на первый вход первого элемента И 18 БУ он через четвертый выход 38 БУ передается на запрещающий вход 50 генератора 3 импульсов и выработка импульсов прекращается. После записи в N -е разряды групшл 16 N -разрядных сдвигающих регистров элемент главной диагонали дистанционной матрицы 5 в указанных регистрах будет содержаться информация о вершинах, входящих в циклы длиной один, два, ..,, N . Работа устройства по исследованию графа на этом завер- щастся,

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

дуг, причем блок управления содержит группу элементов задержки, а матрица формирователей дуг - триггеры и элементы И, выходы триггеров матрицы формирователей дуг соединены с первыми входами одноименных элементов И матрицы формирователей дуг, выходы элементов И каждой строки матрицы формирователей дуг подключены к входам соответствующих элемен- тов ИЛИ первой группы, отличающееся тем, что, с целью расширения .функциональных возможностей устройства за счет определения наличия в графе циклов длиной К (,М, где k - количество вершин в графе) и вершин графа, в них участвующих, в устройство введены вторая группа элементов ИЛИ, (N+1)-разрядный сдвигающий регистр, группа N -разрядных сдв:1гающих регистров, матрица формирователей путей, содержащая триггеры первую и вторую группы элементов И, а блок управления дополнительно содержит элемент ИЛИ, первый и второй элементы И, первый, второй, третий и четвертый N -разрядные сдвигающие кольцевые регистры, первый, второй, третий, четвертый, пятый, шестой, седьмой, восьмой, девятый элементы задержки, группы элементов И, группу формирователей импульсов, причем выходы элементов ИЛИ nepsoii группы соединены соответственно с первыми входами элементов И второй группы, выходы триггеров матрущы формирова- гелей путей подключены к первым входам соответствующих элементов И первой группы матрицы формирователей путей, выходы элементов И первой группы каждого столбца матрицы формирователей путей соединены с одноименными входами соответствующих элементов ИЛИ втoJ)Oй группы, выходы которых подключены к первым входам элементов И второй группы, выходы элементов И второй группы соединены с входами элемента ИЛИ соответственно, выход элемента Ш1И подключен к входу установки в 1 (N+l)-ro раз-

ряда (N-t-l )-разрядного сдвигающего регистра, группа выходов которого соединена с первыми входами соответствующих элементов И второй группы каждого cтoлf ,a матрицы формирователе путей, выходы элементов И второй группы матрицы формирователей путей подключены к входам установки в 1

25

j О1520, 30 35 4045 50

й 55

5279110

одноименных триггеров матрицы форми- ранателя путей, выходы триггеров матрицы формирователей путей, расположенных на главной диагонали, подключены к первым входам одноимен1П)1х элементов И первой группы, выходы которых соединены с входами установки в 1 N -го разряда соответствующего N-разрядного сдвигающего регистра группы, входы установки в О первого, второго, третьего и четвертого N-разрядных кольцевых сдвигающих регистров блока управления объединены с входами первого, четвертого, пятого элементов задержки блока управления и подключены к входам установки в О ( 1)-го разряда (N + 1 )-разрядного сдвигающего регистра, N -х разрядов N-разрядных сдвигающих регистров группы и к входу запуска устройства, выход четвертого элемента задержки блока управления подключен к входам установки в 1 N го разряда первого М -разрядного кольцевого сдвигающего регистра блока управления, первого разряда второго N -разрядного кольцевого сдвигаюп1его регистра блока управления, (N-l)-ro разряда третьего N -разрядного кольцевого сдвига- юг;его регистра блока управления и N-ro разряда четвертого N -разрядного кольцевого сдвигающего регистра блока управления, выход пятого элемента задержки блока управления подключен к входу запуска генератора импульсов, выход которого подключен к входам третьего, шестого, седьмого и восьмого элементов задержки блока управления и к входу сдвига третьего N -разрядного кольцевого сдвигающего регистра блока управления, выход восьмого элемента задержки блока управления подключен к входу сдвига (N-t-l)-ro разрядного сдвигающего регистра, выход (M-l)-ro разряда третьего N -разрядного кольцевого сдвигающего регистра блока управления подключен к первым входам элементов И группы блока управления и к первому входу второго элемента И блока управления, второй вход которого подключен к выходу третьего элемента задержки блока управления, единичный выход N -го разряда третьего N -разрядного кольцевого сдвигающего регистра блока управления подключен к входу сдвига первого М -разрядного кольцевого

сдвигающего регистра блока управления, каждый выход группы выходов которого подключен к второму входу соответствующего элемента И группы блока управления и к вторым входам элементов И первой группы соответствующего столбца матрицы форм1тро- вателей путей, выход шестого элемента задержки блока управления подключен к третьим входам элементов И группы блока управления, выходы которых подключены к входам соотпет- ствующих элементов задержки группы блока управления и к входам установки в О триггеров соответствующего столбца матрицы формирователей путей, каждый выход группы выходов элементов задержки группы блока управления подключен к вторым входам элементов И второй группы соответствующего столбца матрицы формирователей путей, выход седьмого элемента задержки блока управления подключен к входу сдвига четвср- 10ГО N -разрядного кольцевого сдвигающего регистра блока управления, выходы каждого из разрядов которого соединены с входами одноименных фор шрователей импульсов группы блока управления, выход каждого формирователя импульсов группы блока управ1252791

12

ления полключеи к пторьгм входам элементов И соответствуюшей строки матрицы фop c poвaтeлeй дуг, единичный пыход N -го разряда первого N -разрядного кольцевого сдвигающего регистра блока управления подключен к входу второго элемента задержки блока управления и к третьему входу второго элемента И блока управления, выход которого соединен с входом девятого элемента задержки блока управления, с первым входом первого элемента И блока управления и с входами сдЕига группы W -разрядных сдвигающих регистров, выходы первого и девятого элементов задержки блока управления подключе1гы к соответствующим входам элемента ИЛ1 блока управления, выход которого подключен к вторым входам элементов И первой группы, выход второго элемента задержки блока управления подключен к входу сдвига второго N -разрядного кольцевого сдвигающего регистра блока управления, выход N -разряда которого соединен с вторым вхо - дом первог о элемента И блока управления выход первого элемента И блока управления соединен с вхо лом злпрета генератора импуль0(111 .

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