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

(5(1 4 С 06 Р 1 5 / 20 ОПИСАНИЕ ИЗОБРЕТЕНИЯ ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССРПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ К А ВТОРСКОМУ СВИДЕТЕЛЬСТВУ(56) Авторское свидетельство СССР Ф 807836, кл. С 06 Р 15/20, 1980,Авторское свидетельство СССР У 716043, кл, С 06 Р 15/20 1980.(54) УСТРОЙСТВО ДЛЯ ИССЛЕДОВАНИЯГРАФОВ(57) Изобретение относится к областивычислительной техники и преднаэначено для определения в графе цикловдлиной 1,2 й (где И - количествовершин графа) и вершин, в них участвукицих. Изобретение позволяет расширить функциональные возможностиустройства эа счет определения наличия в графе циклов длиной 1( (К 1, й )и вершин графа, в них участвующих,Использование предлагаемого устройства исключает необходимость программного поиска циклов в графе, осуществление которого в приемлемое время оказывается невозможным ввиду высокой трудоемкости соответствующегоалгоритма. Устройство содержит матрицу 1 формирователей дуг, блок 21252791 унранлення, генератор 3 импульсов,Н х М тригг ров 4 и элементон И 5матрицы Формирователей дуг, первуюгруппу б нз М элементов ИЛИ, первую 7 и вторую 8 группы из Н элементов И, матрицу 9 Формирователей путей, включающую М х М элементов,Изобретение относится к вычислительной технике и может быть использовзно при исследовании графов.Цель изобретения - расширение функциональных возможностей устройства за счет определения наличия в графе циклов длиной К (К=1 М ) и вершин графа н них участвующих.В теории графов под циклом понимается некоторый путь, начальная и конечная вершины которого совпадают. линой цикла называется число дуг, входящих в него, В общем случае в графе могут бьггь циклы различной длины, Минимальная длина цикла равна единице (вершина имеет петлю), максимальная - М (гамильтонов цикл). Если це накладывается условие однократного вхождения дуги в цикл, то петля может считаться циклом длиной 1,2М, Информацию о наличии в графе циклон длиной К (К=1 М ) содержит дистанционная матрица К -го порядка 6,. Она представляет собой квадратную матрицу размером М х М, элементы которой есть "1" и "=", Наличие " на пересечении 1-и строки и т-го столбца свидетельствует о том, что из 1-й вершины в 1-ю нершину графа есть путь длиной К . Следовательно, нали-. чие на главной диагонали дистанционной матрицы н 1-й строке снидетельствует о наличии пути длиной К из 1-й вергины в цее саму, т,е, цикла длиной К, Тогда, Формир,гя дистанционные матрицы Р,66 м и анализируя диагоцачьные элементы указанных матриц можно определить наличие циклов длиной К и какие вершины в них входят. Очевидно, что матрица смежности графа представлякаждый из которых содержит триггер10 и перную 1 и вторую 2 группыэлементов И, вторую группу 13 изэлементов ИЛИ, элемент ИЛИ 14 (Н+1) -разрядный сдвигающий регистр 15,группу 6 М -разрядных сдвигающихрегистров. 2 ил. ет собой дистанционную матрицу первого порядка о,.Для нычисления элементов дистанционных матриц более высоких порядс5 кон С используется следующаярекуррентцая формула;С, = 9 С Д а , К =2,М, (1)Ч 1 где а - элемент матрицы смежностич10 графа9 - знак дизъюнкции;Л - знак конъюнкции,На фиг, 1 приведена структурнаясхема устройства для исследованияграфов; на фиг. 2 - структурная схема блока управления,Устройство для исследования графов содержит матрицу 1 формирователей дуг, блок 2 управления (распределитель импульсов), генератор 3импульсов, триггеры 4 матрицы формирователей дуг, элементы И 5 матрицы формирователей дуг, первую группу6 элементов ИЛИ, первую 7 и нторую 8 25группы элементов И, матрицу 9 формирователей птей, триггеры 1 О матрицыформирователей путей, первую 1 ивторую 12 группы элементов И матрицы формирователей путей, вторую 30гртпу 13 элементов ИЛИ, элементИЛИ 14, (Н+1)-разрядный сдвигающийрегистр 15, группу 16 М -разрядныхсдвигающих регистров, элемент ИЛИ 17блока управления (БУ), первый 18 .5 и второй 19 элементы И БУ, первый 20,второй 21, третий 22, четвертый 23М-разрядные кольцевые сдвигающиерегистры БУ, первый 24 и второй 25элементы задержки БУ, группу 26 40 элементов И БУ, группу 27 формирователей импульсов БУ, третий 28, четвертый 29, пятый 30, шестой 31,седьмой 32 и восьмой 33 элементы за 1252791держки БУ, группу 34 элементов задержки БУ, девятый элемент 35 задержки БУ, второй 36 и третий 37 выходы БУ, третью группу 38 выходов БУ, четвертый выход 39 БУ, вторую 5 группу 40 ныходов БУ, пятый выход 41 БУ, второй 42 и первый 43 входы БУ, четвертую 44 и первую 45 группы выходов БУ, первый 46 и шестой 47 выходы БУ, вход 48 запуска генератора импульсов, выход 49 генератора импульсов, вход 50 запрета генератора импульсов, вход 51 запуска устройства.Устройство работает следующим 15 образом.Первоначально в триггеры 10 матрицы 9 формиронателей путей и в триггеры 4 матрицы 1 формирователей дуг в виде матрицы смежности А заносится О исходная информация об исследуемом графе. При этом в единичное состояние устанавлинаются лишь те триггеры 1 О; и 4, (1) =1,И, где Н - количество вершин графа), для которых в 5 исследуемом графе есть дуга из вершины 1 н вершину 1. С поступлением на второй вход42 БУ пускового импульса с входа51 устройства нсе разряды первого 20,второго 21, третьего 22 и четвертого 23 Н -разрядных кольцевых сдвигающих регистров, а через первый выход46 БУ (И+1)-й разряд (8+1)-разрядного сдвигающего регистра 15 и И -еразряды группы 16 й -разрядных сдвигающих регистров устанавливаются внулевое состояние. Через интерваллвремени с определяемый параметрамипервого элемента 24 задержки БУ, появляется импульс записи номеров вершин, входящих в цикл, который, пройдя через элемент ИЛИ 17 БУ, выдаетсяна третий выход 37 БУ. Этот импульсоткрывает по первому входу элементыИ первой группы 7, на вторые входыкоторых поступает сигнал с единичныхвыходов соответствующих триггеров10, (1=1, й ) матрицы 9 формироватеЛей путей, Состояние этих триггерон 50переписывается н Н -е разряды группы 16 1 -разрядных сдвигающих регистров, при этом для любого 1(1"1, Ч )наличие единицы в Й -м разряде 1-го8-разрядного сдвигающего регистра со ответствует тому, что в исследуемомграфе 1-я вершина входит в циклдлиной один,Через ингервал времени, определяемый параметрами четвертого элемента 29 задержки БУ, И -е разрядыпервого 20 и четвертого 23 й -разрядных кольцевых сднигающих регистров БУ, первый разряд второго Иразрядного к; цевого сдвигающегорегистра 21 БУ и (8-1)-й разрядтретьего 11 -разрядного кольцевогосднигающего регистра 22 БУ устананлинаются в единичное состояние, ачерез интервал 7, определяемыйпараметрами пятого элемента 30задержки БУ, на втором выходе 36 БУпоявляется сигнал, который поступает на вход 48 запуска генератора 3импульсов,Генератор 3 импульсов начинаетвырабатывать импульсы с периодом Ткоторые с выхода 49 генератора 3поступают на первый вход 43 БУ. Снторого входа 42 БУ они поступаютн цепь сдвига третьего 8 -разрядногокольцевого сдвигающего регистра 22БУ и на вход третьего 28, шестого31, седьмого 32 и восьмого 33 элементов задержки БУ, на выходе которых по ним формируются сигналы через интервалы времени , , с, исоответственно, С поступлением первого импульса на первый вход 43 БУначинается цикл работы устройства поформированию значения элемента С ядистанционной матрицы второго порядка 1 , определяемого выражением (1). По первому импульсу генератора 3 импульсов единица из (8 - 1)-го разряда третьего М -разрядного кольцевого сдвигающего регистра 22 БУ сдвигается в й -й разряд. Пояг. ение сигнала на единичном выходе Й -го разряда указанного регистра осуществляют сдвиг единицы из Н -го разряда перного Н -разрядного кольцевого сдвигающего регистра 20 БУ н 1-й разряд. Высокий потенциал с единичного выхода 1-го разряда регистра 20 через первый выход первой группы И 45 вы" ходов БУ поступает на вторые входы первых элементов И 11 первой строки матрицы 9 формирователей путей, тем самым разрешая поступление содержимого триггеров 10 первой строки матрицы 9 формирователей путей (первой строки дистанционной матрицы о ) через вторую группу 13 элементов252 10 Г посту;Еленем второго импульса от генератора 3 импульсов единица 45 из М -го разряда третьего 1) -разрядного кольцевого сдвигающего регистра 22 БУ сдвигается в первый разряд. Состояние первого-разрядного кольцевого сдвигдюшего регистра 20 БУ не измецяетгя. По импульсу, выдаваемому черезосуществляется сдвиг единицы и первого разряда четвертого 8 -разрядного кольцевого сдвигаюшего регистра 23 БУ во второйразряд.55 При появлении ь)сокого потенциала нд единичном ыходе второго разряда укдзанцого регистра второй формироИИ цд перые ходы второй группы 8э)с мец" ов И,Через ицгервал времениопре -деляемый парам.трами седьмого элемента 32 задержки БУ, выдается им 5пульг, по кэ) ормг осушествляетсясдвиг единицы из-го разряда четверзого И -рЕзрядцого кольцевогогдвигаюш г. регистра 23 БУ н первыйрд )ряд. При и влеции высокого потцциала нд единичном выходе первогоразряда укццо.о регистра первыйфорровдтель группы 27 формирователей импл) ьо БУ вырабатывает си Гнахкоторый )сре: первый выход второй 15группы 40 выходов БУ поступает цагорыг )ходы элеыецтое И 5 первого"голб;Е матрицы 1 формирователей дуг,тем .мым ррешая поступление содержимого триггеров 4 первого столбцд матрцць) 1 рормировдтелей дуг(элемецтов а ) через первые входычсоответствуюших элементов И 5 и первую групп; 6 элементов ИЛИ ца вторыеходы втс)рой группы 8 элементов И, 25Вторая групп 8 элементов И иэлемент И 1 П 1 1) реализуют логическуюфуцкццк (1). В рассматриваемый моментвремени цд выходе элемента ИЛИ 147будет получено значение элемента С, З 0дистанционной матрицы о . Это значе 1ние заносится в (И+1)-й разряд (+1) -разрядного слвигаюшего регистра 15.Через интервал времениопре 16Лгляемь)й параметрами восьмого элемент 33 задержки БУ, выдается импульг, который через пятый выход41 БУ поступает ца вход сдвига (8+1)разрядного двигаюшего регистра 15.При этом значение полученного элеи нта Г сдвигатся иэ 1+1)-го разряда (8+1)-разрядного сдвигающегорегигтра 15 в Н -й разряд,791 втель группы 27 формирователей ими Еьсов Ьу вырабатывает сигнал, которь)й через второй выход второй группы 40 выходов БУ поступает на вторыеходы элементов И 5 второго столбцамдтрицы 1 формирователей дуг, тем,)мым разрешая поступление содержимого триггеров 4 второго столбцаматрицы 1 формирователей дуг черези) рвую группу 6 элементов ИЛИ наторые входы вг)рой группы 8 элеменИ, В рассматриваемый моментвреме)ьн ца вь)ходе третьего элементаИВ 14 будет получено значение элемента С, дистанционной матрицы о 7которое будет запомнено в (И+1)-разрядном сдвигаюшем регистре 15,При выработке гецерагором 3 импульсов третьего четвертого,)-го импульсов устройство работаетаналогично. После поступления навход сдвига (И+1)-разряде)оо сдвигаю)шего регистра 15 ) - го импульсасдвига, в нем будут записаны эле 7 7 7менты С , С С, (первая строка дистанционной матрицы 1 ),По 8 -му импульсу, выработанномугенератором 3 импульсов, после сдвига в- 1)-м разряде третьего Мразрядного кольцевого сдвигаюшегарегистра 22 БУ появляется единица,Высокий потенциал с единичного выхода (М)-го разряда укаэанного регистра поступает на первые входыгруппы 26 элементов И БУ, На вторыевходы указанной группы элементовпоступают потенциалы с единичныхвыходов первого 11 -разрядного кольцевого сдвигаю)цего регистра 20 БУ,Через интервал времениопределяемый параметрами шестого элемента31 задержки БУ на третьи входыгруппы 26 элементов И БУ поступаетсигнал. В рассматриваемый моментвремени на втором входе имеет высокий потенциал только первый элемент группы 26 элементов И БУ. В результате на его выходе формируетсяимпульс, который через первый выходчетвертой группы 14 выходов БУ сбрасывает в нулевое состояние триггеры 10 первой строки матрицы 9 формирователей путей, Этот же импульспоступает на вход перного элементагруппы 34 элементов задержки БУ.Через интервал времени ь опре)аделяемь)й параметрами укаэанного элемента задержки, импульс чере первый,1252791 ответствующих единичных выходон(Н +1) -разрядного сдвигаюшего регистра 5. Таким образом содержимое 10указанного регистра записывается втриггеры 10 первой строки матрицы 9формирователей путей, т.е, цикл поформированию первой строки дистанционной матрицы ца этом завершается, 5Следует отметить, что значения элементов первой строки дистанционнойматрицы меньшего ца единицу порядка(в данном случае в ) це сохраняются,поскольку в дальнейшем оци це используются.Аналогичным образом Формируются изапомицаются вторая, третьяМ-я строки дистацциоццой матрицы ОгС поступлением Н(Н - 1)+1 импулг,са 25в Н -м разряде первого Н в разряднокольцевого сдви гаюше го ре гистра 20 БУпоявляется единица, и через интервал времени с 7определяемый парамтрами второго элемента 25 задержки БУ, осуществляется сдвиг цз первого разряда второго Н -разрядногокольцевого сдвигаюшего регистра 21 БУво второй разряд,С поступлением от генератора 3импульсов М импульсов в матрице 9гФормирователей путей будет записанадистанционная матрица о . Теперьосуществляется запомггцацие вершин,входящих в цикл длиной 2,С этой целью сигнал с выхода третьего элемента 28 задержки БУ поступает на второй вход второго элементаИ 19 БУ, который в рассматриваемыймомент времени открыт по первомувходу высоким потенциалом с единичного выхода (Ц - 1)-го разряда третьег 4 М -разрядного кольцевого сдвигающего регистра 22 БУ, а по третьемувходу - высоким погенциалом с единичного выхода Н -го разряда первогоН-разрядного кольцевого сдвигающегорегистра 20 БУ. 35 г 3 рц поступлении импульса с номе 7ром М (М - 1) с выхода второго эле 1 с цта И 9 БУ на первый вход первогоэлемента И 18 БУ он чрез четвертыйвыхс 1 д 38 БУ передается на запреща юший вход 50 генератора 3 импульсови выработка импульсов прекращается.После записи в Н -е разрядгя группы16 М -разрядных сдвцгающих регистровэ:.с.1 ецт главной диагонали дистанционной матрицы 5 в указанных регистрах будет содержаться информация овершинах, входящих в циклы длинойодин два, , М . Работа устройствапо исследованию графа ца этои завер 50 шается,выход третьей группы 38 выходов БУпоступает ца вторые входы вторыхэлементов И 12 первой строки матрицы 9 формирователей путей, На первые входы вторых элементов И 12каждой строки матрицы 9 Формирователей путей поступают сцгцалы с совлг но, т, е. в рассматриваемый момс нтц мели содержимое М -х разрядовбудт пермешено в (Н - 1)-е разряды.Через ицтервавремени с , определя;г,.й параметрами девятого элемента 35задржиц БУ, этот же импульс черезэггс:монт ИЛИ 17 БУ выдается ца третийвыход 37 БУ. Этот импульс открываетпо второму входу элементы И первойгруппы 7, на первые входы которыхпоступают сигналы с единичных выхолов соответствующих триггеров 10, (1=1, М ) матрицы 9 формирователей путей, и состояние этих триггерсв переписывается в Н -е разряды группы 16 М -разрядных сдвигающих регистров, при этом для любого Е(1=1,М ) наличие единицы в М -м разряде 1-го М -разрядного сдвигаюшсго регистра соответствут тому, что в исследуемом графе 1-я вершина входит в цикл длицсй 2.Работа устройства по определению цомс ров вршиц, входягцих в циклы длиной триН, протекает анало 1 цчгго.С постугглцием от генератора 3 импульсов М (Н)+1 импульсов в - разряд второго М -разрядного копьявого двигающего регистра 21 БУ появляется единица и на второй вход црвого элемига И 18 БУ начицас 1 поступагь разрешагвщиц высокий цотццал. Формула изобретенияНа выходе второго элемента И 19 БУ появляется импульс, который через 55 шестой выход 47 БУ осуществляет сдвиг содержимого всех М -разрядных сдвиговых регистров группы 16 на разряд Устройство для исследования гра.Фов содержащее генератор импульсов, первую группу элементов ИП 1 первую и вторую группы элементов И, блок управлецгя матрицу Формирователей9 1252 дуг, причем блок управления содержит группу элементов задержки, а матрица формирователей дуг - триггеры и элементы И, выходы триггеров матрицы формирователей дуг соединены с первыми входами одноименных элементов И матрицы формиронателей дуг, выходы элементов И каждой строкиматрицы формирователей дуг подключены к входам соответствующих элемен тон ИЛИ первой группы, о т л и ч а - ю ш е е с я тем, что, с целью расширения,функциональных воэможностей устройства за счет определения наличия в графе циклов длиной К (К=114 15 где К - количество вершин н графе) и вершин графа в них участвующих, в устройство введены вторая группа элементов ИЛИ (8+1)-разрядный сдвигающий регистр, группа 11 -разрядных 10 сдвцгающих регистров, матрица формирователей путей, содержащая триггеры, первую и вторую группы элементов И, а блок управления дополнительно содержит элемент ИЛИ, первый и вт орой элементы И первый, второй, третий и четвертый М -разрядные сднигающие кольцевые регистры первый, второй, третий, четвертый, пятый, шестой, седьмой, восьмой девятый лементы 30 задержки, группы элементов И, группу формирователей импульсов, причем выходы элементов И 3 П первой группы соединены соответственно с первыми входами элементов И второй группы, выходы триггеров матрицы формирователей путей подключены к первым входам соответствующих элементов И первой группы матрицы формирователей путей выходы элемецтон И первой 40 группы каждого столбца матрицы формирователей путей соединены с одноименными входами соответствующих элементов ИЛИ второй группы, выходы которых подключены к первым входам 45 элементов И второй группы, выходы элементов И второй группы соединены с входами элемента ИЛИ соответственно выход элемента ИЛИ подключен к входу установки н 1 (И+1)-го раз ряда (1+1)-разрядного сдвигаюшего регистра, группа выходов которого соединена с первыми входами соответствующих элементов И второй группы каждого столГ;а матрицы формирователей 55 путей, выходы элементов И второйгруппы матрицы формиронателей путей подключены к входам установки в "1" 791 Оодноименных триггеров матрицы формирователяпутей выходы триггеров матрицы формирователей путей, расположенных на главной диагонали, подключены к первым входам одноименных элементов И первой группы, выходы которых соединены с входами устанонки н"1" 11 -го разряда соответствующего1 -разрядного сдвигающего регистрагруппы, входы установки в О" первого, второго, третьего и четвертогоМ-разрядных кольцевых сдвигающих регистров блока управления объединеныс входами первого, четвертого, пятогоэлементов задержки блока управленияи подключены к входам установки в "О"(9+1)-го разряда (14+1)-разрядногосдвигающего регистра, Н -х разрядов8-разрядных сдвигающих регистровгруппы и к входу запуска устройства,выход четвертого элемента задержкиблока управления подключен к входамустановки н 1 11 -го разряда первого И -разрядного кольцевого сдвигающего регистра блока управления, первого разряда второго 1 -разрядногокольцевого сдвигающего регистра блокауправления, (Н - 1)-го разряда третьего Н -разрядного кольцевого сдвигакц",сго регистра блока управления и11-го разряда четвертого 1 -разрядного кольцевого сдвигающего регистраблока управления, выход пятого элемента задержки блока управления подключен к входу запуска генератораимпульсов, выход которого подключенк входам третьего, шестого, седьмого и восьмого элементов задержкиблока управления и к нходу сдвигатретьего 1 -разрядного кольцевогосдвигающего регистра блока управления, выход восьмого элемента задержки блока управления подключенк входу сдвига (И+1)-го разрядногосдвигающего регистра выход (Н)-горазряда третьего 1 -разрядного кольцевого сдвигающего регистра блокауправления подключен к первым входамэлементов И группы блока управления и к первому входу второго элемента И блока управления, нторойвход которого подключен к выходутретьего элемента задержки блокауправления, единичный выход Й - горазряда третьего Н -разрядного кольцевого сдвигаюшего регистра блокауправления подключен к входу сдвига первого Н -разрядного кольцевого11 12 сдвигающего регистра блока управления, каждый выход группы выходов которого подключен к второму входу соответствующего элемента И группы блока управления и к вторым входам элементов И первой группы соответствующего столбца матрицы формирователей путей, выход шестого элемента задержки блока управления подключен к третьим входам элементов И группы блока управления, выходы которых подключены к входам соответствующих элементов задержки группы блока управпения и к входам установки в "О" триггеров соответствующего столбца матрицы формирователей путей, каждый вы од группы выходов элементов задержки группы блока управления подключен к вторым входам элементов И второй группы соответствующего столбца матрицы формирователей путей, выход седьмого элемента задержки блока управления подключен к входу сдвига четвертого 1 -разрядного кольцевого сдвигающего регистра блока управления, выходы каждого из разрядов которого соединены с входами одноименных формирователей импульсов группы блока управления, выход каждого формирователя импульсов группы блока управ 52791 12ления пс включен к вторым входам элементов И соответствуюшей строки матрицы формирователей дуг, единичныйвыход М -го разряда первого Н -разрядного кольцевого сдвигающего регистра блока управления подключенк входу второго элемента задержкиблока управления и к третьему входувторого элемента И блока управления, 10 выход которого соединен с входомдевятого элемента задержки блокауправления, г. первым входом первогоэлемента И блока управления и с входами сдвига группы И -разрядныхсдвигающих регистров, выходы первогои девятого элементов задержки блокауправления подключены к соответствующим входам элемента ИЛИ блока управления, выход которого подключен квторым входам элементов И первойгруппы, выход второго элемента задержки блока управления подключен квходу сдвига второго Ю -разрядногокольцевого сдвигающего регистра блод ка управления, выход Н -разрядакоторого соединен с вторым входом первого элемента И блокауправления, выход первого элемента 11 блока управления соединен свходом запрета генератора импульс,1 в