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

ОПИСАНИЕИЗОБРЕТЕНИЯХ АВТОРСКОМУ СВИДИТЕЛЬСТВУ Союз Советских Социалистических Республик(22) Заявлено 220379 (21) 2738974/18-24 с присоединением заявки Йо С 06 Г 15/20 Государственный комитет.СССР по делам изобретениЯ и открытийДата опубликования описания 230281,у ФУЕХр ц,Институт электродинамики АН УкраинскОй ССР . ОтЯ(54) УСТРОЙСТВО ДЛЯ ИССЛЕДОВАНИЯ ГРАФОВ Изобретение относится к вычислительной технике и является усовершенствованием известного устройства. По основному авт. св, Р 643880 известно устройство, содержащее модели нершин, соединенные между собой согласно топологии исследуемого графа, регистр, вход и первый выход которого подключены к первому выходу 1 О и входу блока управления, второй, третий и четвертый выходы которого соединены соответственно с первым, вторым и третьим нходами моделейвершин, информационные ныходы ре гистра соединены с первыми входами элементов И группы, второй вход каждого из которых подключен к первому ныходу соответствующей модели вершины, выходы элементов И 20 группы подключены соответственнок четвертым входам моделей вершин, кажцая из которых содержит первый триггер, первый элемент ИЛИ, первыйэлемент И, второй триггер, первый 25 и второй формирователи импульсов,второй, третий, четвертый, пятыйи шестой элемент И, второй элемент ИЛИ, элемент НЕ, счетчик импульсов, блок индикации, причем четвертый ЗО Ж вход модели вершины графа соединен с первыми входами первого и второго элементов И, вторые входы которых подключены к первому и второму входам модели вершиныграфа, выходы первого и второго элементов И соединены соответственно с первыми входами первого и второго элементов ИЛИ, выходы которых подключены к единичным входам первого и второго триггеров, единичный выход первого триггера подключен, к первому входу четвертого элемента И и к входу первого формирователя импульсов, выход которого соединен с вторым входом модели вершины графа и с первым входом третьего элемента И, второй вход которого подключен к нулевому выходу первого триггера, третий вход третьего элемента И соединен с вторым входом второго элемента И и с первым входом модели вершины графа, выход третьего элемента И соединен с вторым входом второго элемента ИЛИ, единичный выход второго триггера подключен к входу формирователя 1 импульсов, к первому входу шестого элемента И и к второму входу четвертого элемента И, выход которого соединен с первымвходом пятого элемента И и черезэлемент НЕ подключен к первомувыходу модели вершины графа, третийвход которой соединен с вторымвходом пятого элемента И, выход которого подключен к входу счетчика,импульсов, выход которого соединенс блоком индикации, .выход второгоформирователя импульсов подключен ктретьему выходу модели вершины графа и к второму входу шестого элемента И, третий вход которого соеди-нен с вторым входом первого элемента И и с вторым входом модели вершины графа, выход шестого элементаИ подключен к второму входу первогоэлемента ИЛИ (1),Указанное устройство позволяетвыделить нсе максимальные сильно связанные подграфы в графе.Однако устройство не позволяетнайти число внешне-внутреннего разделения вершины х , определяемоговыражением8 (х. ) = (й (х,;, х) +2 (х , х,; ) ),где х - множество вершин исследуемого графа 1Й (х, х ) и Й (х, х.; ) - соответственно веса расстояний между х, и х вершинами в пря-мом й обратном направлениях.Цель изобретения - расширениефункциональных возможностей устрой-.ства для исследования графов за счетвоэможности решения задач структурного анализа графов, а именно обеспечение дополнительной возможностиопределения числа внешне-внутреннего разделения вершин,Эта цель достигается тем, чтов устройство для исследования графов по авт. св, Р 643880 в каждуюмодель вершины графа дополнительновведены восьмой и девятый элементыИ, третий элемент ИЛИ и второй счетчик импульсон, выход которого подключен к второму входу блока индикации, выходы восьмого и девятогоэлементов И соединены соответственно с входами третьего элемента ИЛИ,выход которого подключен к входу.второго счетчика импульсов, входывосьмого элемента И соединены соответственно с нулевым выходом второготриггера, с первым и пятым входамимодели вершины графа, входы девятогоэлемента И подключены соответственнок нулевому выходу перного триггера,к второму и пятому входам моделиграфа, пятый нход которой соединенс управляющим входом блока управленияНа чертеже схематически представлено устройстно.Устройство содержит модели 1- 1вершин исследуемого графа, блок 2управления, (сдвиговой) регистр 3,элементы 4- 4 яВ состав каждой модели вершинывходят триггеры 5 и б, элементы И 714, элементы ИЛИ 15-17, элементНЕ 18, счетчики 19 и 20 импульсов,формирователи 21 и 22 одиночногоимпульса, блок 23 индикации, полюса(нходы и выходы) 24-31 модели вершины графа, полюса (вход и выходы)32-37 блока управления.Нахождение числа внешне-внутреннего разделения определяется дляпроизвольной вершины и включает нсебя нахождение числа внешнего разделения, а затем - числа внутреннегоразделения вершины хУстройство работает следующимобразом.первоначально посредством полю сов 24 и. 25 модели вершин коммутируются между собой в соответствии сконфигурацией исследуемого графа.Сдвиговой регистр 3 и счетчики19 и 20 импульсов обнуляются. Тригге ры 5 и б нсех моделей вершин устанавливаются в нулевое состояние(установочные шины не показаны),Первоначально н графе выбираетсяпроизвольная вершина х и для нееопределяются все числа внешнегоразделения. Выбор произвольной вершины х производит блок 2 управления.Для этого блок 2 управления выдаетимпульс через полюс 36 на вход сдвигового регистра 3. Продемонстрируем это на примере выбора модели1 вершины. На выходе первого разряда сдвигового регистра 3 появляется разрешение, которое поступает на один из входов элемента Имодели 14, Разрешение проходитчерез элемент И модели 1, так какна втором ее входе есть разрешениес полюса 26 модели 1( вершины, ипоступает на полюс 29. модели верши ны, чем обеспечивается ее выбор.Одновременно с выбором вершиных блок 2 управления выдает разрешение на полюса 28 и импульсы генератора импульсов ГИ (не показан) наполюса 31 всех моделей 1(- 1 вершины. Импульсы ГИ, пройдя элементИ 14 и элемент ИЛИ 17, поступают навход счетчика 20 импульсов и накапливаются в нем, Прохождение импуль сов ГИ через элемент И 14 обеспечивается разрешениями, которые снимаются с нулевого ныхода триггера 5и с полюса 28 модели вершины. Числоимпульсов, накопленных счетчиком 20,определяет величину числа внешнегоразделения между выбранной вершинойх и вершиной, которая может бытьдостигнута из вершины х. При этомн счетчик выбранной вершины заносится 0 импульсов, так как выбормодели вершины х сопронождаетсяустановкой ее трйггера 5 в единичноесостояние, что достигается разрешением, поступающим на полюс 29модели вершины, через элементы И 9 д и ИЛИ 15 на единичный вход этоготриггера. В результате с входа элемента И 14 снимается разрешение.В остальные модели вершин в счет чики 20 заносятся соответственно: в модели вершин, связанных непосредственно с выбранной, по одному импульсу; в счетчики 20 моделей вершин, связанных с выбранной через одну вершину, по два импульса и т.д,Такое занесение импульсов в каждую из последующих моделей вершин обе= спечинает импульс, сформированный в выбранной модели вершины х Формирователем 21 одиночного имйульса. Этот импульс, распространяясь по сети с полюса 24 через элементы И 7 и ИЛИ 15, устанавливает триггер 5 н единичное состояние и повторяется формирователями 21 одиночного импульса в каждой модели вершины, которые доступны из выбранной,1 Л - 1 П вершин. При этом импульс ГИс полюса 31 через элементы И 13 иИЛИ 17 поступает на вход счетчика20 импульсов и накапливается в нем.Число импульсов ГИ, поступивших навход счетчика 20, соответствует ве 25 личине числа внутреннего разделения,а общее число импульсов, накопленных счетчиком 20, определяет величину числа, внешне-внутреннего разделения вершины х и вершин, которые достигаются из вершины х и из которых достигается эта вершина.Прохождение импульсов ГИ через элемент И 13 обеспечивается разрешениями, которые снимаются с нулевого выхода триггера 6 и полюса 30, При этом в счетчики 20 моделей вершин, по аналогии, как и при определении числа внешнего разде 35 40 ления, заносится определенное число импульсов. В выбранную модель вершины х заносится 0 импульсов,так как момент определения числаннутреннего разделения сопровождается установкой триггера 6 в выбранной модели в единичное состояние.Это происходит разрешением с полюса30 через элементы И 10 и ИЛИ 16,. которое поступает на единичный входтриггв;а б. В остальные модели вершин число импульсов, занесенных в счетчик 20, определяется распрастранением импульса, сформированного формирователем 22 одиночного импульса выбранной модели, Этот импульс, распространяясь по сети с полюса 25 через элемент И 8 и ИЛИ 16, устанавливает триггеры 6 в единичное состояние и повторяется формирователями 22 одиночного импульса н каждой модели,Определение числа внутреннего раз деления вершины х происходит блоком 2 управления в результате снятия разрешения с полюсов 28 и выдачи разрешения на полюса 30 всех моделей из которых может быть достигнутавыбранная вершина,Модели вершин, для которых определено число внешне-внутреннегоразделения, о чем свидетельствуетединичное состояние триггеров 5 и 6,из дальнейшего рассмотрения исключаются. Это происходит в результатетого, что разрешения с единичныхвыходов триггеров 5 и б поступаютна входы элемента И 11 и с его выхода на вход элемента НЕ 18. Инверсия этого раерешения поступает черезполюс 26 на один из входов элементовИ моделей 1 - 1,что обеспечивает иблокировку.В дальнейшем устройство перехо"дит к определению числа внешне-внутреннего разделения вершин, для ко"торых оно не было определено, Процесс осуществляется аналогично описанному выше. Предварительно необходимо установить триггеры 5 и б внулевое состояние и обнулить счетчики 20 импульсов моделей вершин,.у которых оба триггера 5 и б одновременно не находятся в единичномсостоянии.Множество моделей 1 - 1 д вершинмоделируемого графа группируютсяпо подмножествам, что позволяет выделить относительно каких первоначально выбранных вершин х для нихопределено число внешне-вйутреннегоразделения. Для этого производитсяпометка вершин. Она производится,импульсом блока 2 управления черезполюс 35 на полюс 27 всех моделейвершин. Этот импульс, пройдя элементИ 12 в моделях вершин, у которыхтриггеры 5 и б одновременно находятся в единичном состоянии, поступаетна вход счетчика 19 и запоминаетсян нем,Процесс определения числа внешневнутреннего разделения для всехвершин прекращается тогда, когдана полюсе 32 блока 2 управления свыхода сдвигового регистра 3 не появляется сигнал.Номер подмножества, к которомуотносится вершина, и неличина числавнешне-внутреннего разделения индицируется блоком 23 индикации, входыкоторого подключены к выходам счетчиков 19 и 20.Введение в известное устройстнодополнительно новых двух элементовИ, элемента ИЛИ и счетчика импульсон, включенных в определенную схему, позволяет существенно расширитьее функциональные возможности: даетвозможность дополнительно определятьчисло внешне-внутреннего разделения.Формула изобретенияУстройство для исследованияграфов по авт,св. Р 643880, о т л и8 807313 Составитель техред С, В инин Г, назарова Редактор Л. Ке к ж .756 Подпис осударственного комитета СС лам изобретений и открытий ква, Ж, Раушская наб., д Заказ 294/7 Тир ВНИИПИ по д 113035, МоФилиал ППП "Патент", г. Ужгород, ул. Проектная,ч а ю щ е е с я тем, что, с це,ьюрасширения Функциональных возможчностей решения задач структурногоанализа графов, в каждую модельвершины графа дополнительно введенывосьмой и девятый элементы И, тре.тий элемент ИЛИ и второй счетчикимпульсов, выход которого подключенк второму входу блока индикации,выходы восьмого и девятого элементов И соединены соответственно свходами третьего элемента ИЛИ, выходкоторого подключен к входу второгосчетчика. импульсов, входы восьмогоэлемента И соединены соответственно с нулевым выходом второго триггера,с первым и пятым входами модели вершины графа, входы девятого элементаИ подключены соответственно к нулевому выходу первого триггера, к второму и пятому входам модели вершиныграфа, .пятый вход которой соединенс управляющим входом блока управленияИсточники информации,принятые во внимание при экспертизе1. Авторское, свидетельство СССРР б 43880 кл. 6 06 Р 15/20, 1975