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

СОЮЗ СОВЕТСКИХСОЦИАЛИСТИЧЕСКИРЕСПУБЛИК 4 ГОСУДАРСТВЕННЫЙ . КОМИТЕТ СССРПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ ОБРЕТЕНИЯ ИСА ВУ(56) Авторское свидетельство СССРУ 643880, кл. С 06 Р 15/20, 1975.Авторское свидетельство СССРВ 1134946, кл.С 06 Р 15(20, 1985. втоесномм свидет 801410051(54) УСТРОЙСТВО ДЛЯ ИССЛЕДОВАНИЯГРАФОВ(57) Изобретение относится к вычислительной технике и можетбыть использовано для решения задач на графах. Целью изобретения является снижение аппаратурных затрат. Устрой-.ство позволяет проводить разбиениеграфа на максимальные сильно связанные подграфы, а также находить входные и выходные вершины подграфа, 3 илИзобретение относится к цифровой вычислительной технике и может быть использовано для решения задач на графах,5Целью изобретения является снижение аппаратурных затрат., На фиг,1 приведен пример реализации устройства для исследования граФов; на фиг.2 - структура блока моде лирования; на фиг.З - модель вершины графа.Устройство для исследования графов (фиг,1) содержит блок 1 моделирования графа, блок 2 управления, группы 3-5 элементов ИЛИ, группы 6-9 элементов И, элемент И 10, группы 11-13 триггеров, элементы ИЛИ 14 и 15, регистр 16 сдвига, вход 17 задания начальной вершины графа, вход 18 зада ния топологии графа, вход 19 пуска устройства, выход 20 признака окончания работы устройства, входы 21, 22 задания режима работы, выход 23 принака окончания. ввода информации. 25Блок моделирования графа содержит ход 24 разрешения записи информациисостоит из идентичных моделей верин 25Модель вершины блока моделироваия содержит первый информационный ыход 26, первый. информационный вход 7, второй информационный вход 28, торой информационный выход 29, вход 0 разрешения записи, элементы И 31 - 3, триггер 34.35Устройство реализует следующие ункции: ввод данных о топологии иследуемого графа, выделение макси- альных сильно связанных подграфов рафа, определение входных (выходных)40 ершин подграфа,В описании работы устройства симолами ", , У обозначены сигналы а соответствующих выходах блока управления.Устройство работает следующим образом.1. Режим ввода данных о топологиирафа.Режим ввода задается подачей посоянного потенциала на вход 21. По сигналу У с входа 17 устройства заг 1 исывается "1" в первый разряд регистра 16, По сигналу Ъ информация с входа 18 устройства заносится через злементы ИЛИ 5 группы в триггеры 11 группы, Информация в блок 1 моделирования заносится построчно, Сигнал У открывает элемент И 7 и проходит на1первую группу входов блока 1. Сигналоткрывает элементы И 8 группы иинформация с выходов триггеров 11группыпоступает на вторую группувходов блока 1 моделирования. СигналУ разрешает запись в модели вершин.Таким образом, по сигналам Уз, У , У41записывается информация первой строки блока 1 моделирования,Сигнал У произведет сдвиг врегистре 16, подготавливая тем самымвозможность записи во вторую строкублока 1 моделирования. Как только будут введены все п строк, появитсясигнал на выходе 23 признака окончанияввода информации,2. Режим выделения максимальныхсильно связанных подграф.Устройство реализует алгоритм нахождения максимальных сильно связанных подграфов графа С(Х), основанныйна нахождении прямого Г+(ХК) и обратного Г (ХК) транзитивных замыканийнекоторой вершины графа ХК с последующим образованием их пересеченияГ(ХК) П Г (ХК). Подготовка устройства к работе заключается в подачепостоянного потенциала на вход 22устройства.По сигналу с входа 19 происходитсброс устройства в исходное состояниеи запуск блока управления. По сигналу. У, который управляет вводом информации с входа 17 устройства, в регистр 16 сдвига записывается "1"только в К-й разряд, который соответствует К-й вершине графа, являющейсяначальной для формирования первогоподграфа.Сигнал У открывает элемент 7 ийпоступает на К-й вход первой группыблока 1 моделирования. Если триггер34 модели вершины К-й строки находится в единичном состоянии, то сигналчерез вход 28, элемент И 31 и выход26 проходит на соответствующийвыход второй группы блока 1 и черезэлемент ИЛИ 4 группы устанавливаетсоответствующий триггер 12 группы вединичное состояние. Так формируетсяпрямое транзитивное замыкание первого порядка Г (К). Кроме того, сигФ 1нал с К-го разряда регистра 16 поступает через элементы ИЛИ 4и 5 к иустанавливает в единичное состояниесоответственно триггеры 12 к и 11тем самым формируя Г (Хк)ПХк.Сигнал У открывает элемент 8 и поступает на К-й вход второй группы блока 1 моделирования. Если триггер 34 ячейки К-го столбца находится в5 единичном состоянии, то сигнал через вход 27 модели вершины графа, элемент И 33 и выход 29 проходит на входы установки в единицу триггеров 11 группы, Таким образом, на данном шаге образуется обратное транзитивное замыкание первого порядка вершины Хк, т.е, Г "(Х) цх (триггер 11, установлен в единичное состояние на предыдущем шаге). 15По сигналу У откроются элементы И 7 группы, на первые входы которых через элементы ИЛИ 3 группы поступают единичные сигналы с выходов соответствующих триггеров 12 К-го разряда 20 регистра 16 сдвига. Аналогично уста новятся в единичное состояние тригге. ры 12, соответствующие найденному прямому транзитивному замыканию второго порядка Г (Х) Ц Г+"(Хк) Ц Хк. 25По сигналу У откроются элементы И 8 группы, соответствующие триггерам 11, установленным в единичное состояние. Таким образом будет найдено Г-(Х) Ц Г-(Х) Ц Х,.. 30Рассмотренные шаги циклически повторяются до.тех пор, пока их число не превысит длины максимального пути графа Далее сигнал Уь открывает те элементы И 9 группы, на вторые и третьи входы которых поступают единичные35 сигналы с выходов соответствующих триггеров 11 и 12, Тем самым реализуется пересечение найденного прямого и обратного транзитивных замыканийС(Х) = Г+ (Х,)Ц Г (Х,). Номера переключающихся в единичное состояние триггеров 13 группы соответствуют номерам вершин графа, объединенных в первый максимальный сильно связанный 45 подграф С(Х к) .Сигнал У; произведет сдвиг в регистре 16 сдвига,. например в Р-й разряд, и установит триггеры 11 и 12 в нуле, вое состояние.Если Р-я вершина уже вошла в какой-либо подграф, то единичный сигналс выхода триггера 13 поступает на вход элемента 6, проходит его и через элемент ИЛИ 14 поступает на вход , управления сдвигом регистра 16. Про-, 55 исходит еще один сдвиг и снова проверка условия, входит ли рассматриваемая вершина в подграф. Пока не закончатся сдвиги, сигналс выхода элемента ИЛИ 14 блокируетработу блока управления.Проверка на окончание работы производится элементом И 10, который выдает сигнал 20 окончания работы, есливсе триггеры 13 группы установленыв единичное состояние. Сигнал окончания работы подается на вход сбросаблока управления.3. Режим определения входных (выходных) вершин подграфов.Определение входных и выходныхвершинмаксимальных сильно связанныхподграфов заключается в выборе какого-либо максимального сильно связан"ного подграфа С(хк), в определенииГф СС (Х ) 3 и Г- ГЮС(Х)3 и в пометке вершин, удовлетворяющих условиям Г СС(хк)1 П С(хк) и ГСС(Х ) П С(Х).Первые помеченные вершины являютсявходными вершинами максимальных сильно связанных подграфов, а вторые -выходными,Подготовка устройства к работе заключается в подаче на входы 21, 22устройства постоянного потенциала.Запуском работы устройства служит:сигнал с входа 19, который сбрасываетв ноль все регистры, триггеры, счетчики.Сигналы У 1 и У разрешают ввод информации с входов 17 и 18 соответственно, С входа 17 вводится информа-ция о:подграфе Сс(Х) (для выходныхвершин о подграфе С(хк), а с входа18 - о подграфе С(хк) (для выходныхвершин.о подграфе С 1 С(Х. СигналУ (У ) открывает элемейты 7 (8) Ии по входам первой (второй) группыблока 1 устанавливает смежные к рассматриваемым вершины, которые фиксируются в триггерах 12 (11)группы. Посигналу У производится фиксация номеров входных (выходных) вершин натриггерах 13,Формула изобретенияУстройство для исследования графов, содержащее блок моделирования графа, блок управления, регистр сдвига и первую группу элементов И, первые входы которых подключены к.выходам соответствующих разрядов регистра сдвига, .вход разрешения записи которого соединен с первым выходом блока5 1410 управления, блок моделирования графа содержит и моделей-вершин, где и - число вершин исследуемого графа, о т- , л и ч а ю щ е е с я тем что с цеЭ Ф5 лью снижения аппаратурных затрат, оно содержит вторую, третью и четвертую группы элементов И, первую, вторую и третью группы элементов ИЛИ, первую, вторую и третью группы триггеров, первый и второй элементы ИЛИ, элемент И, вторые входы первой группы элементов И соединены с выходами соответствующих триггеров третьей группы и входамн элемента И, выход которого 15 является выходом признака окончания работы устройства и соединен с входом . сброса блока управления, вход пуска устройства соединен с входом сброса регистра сдвига, входами установкифюитьв 20 в О триггеров третьей группы, входом пуска блока управления и первым входом второго элемента ИЛИ, второй вход которого соединен с выходом первого элемента ИЛИ, а выход соединен 25 с входами установки в "О" триггеров первой и второй групп, вход управления сдвигом регистра сдвига соединен с входом блокировки .блока управленияс выходом первого элемента ИЛИ,ервый вход которого соединен с выодами элементов И первой группы,торой выход блока управления соедиен с входами синхронизации триггеровторой группы, входы установки в "1"оторых соединены с выходами соответ 35твующих элементов ИЛИ третьей група выходы - с первыми входами элеентов И третьейи четвертой групп,ретий выход блока управления соеди 40ен с первыми входами элементов И Второй группы, выходы которых соедииены с входами первой группы блокамоделирования графа, а вторые входыэлементов И второй группы соединены свыходами соответствующих элементовИЛИ первой группы, четвертый выходблока управления соединен с вторымивходами элементов И третьей группы,выходы которых соединены с входамивторой группы блока моделированияграфа, вход разрешения записи которого соединен с пятым выходом блока управления, вход задания начальной вершины графа устройства соединен с информационным входом сдвигового регистра, выходы разрядов которого соединены с первыми входами соответствующих элементов ИЛИ первой, второй итретьей групп, вторые входы элементовИЛИ первой группы соединены с выходамисоответствующих триггеров первойгруппы и вторыми входами элементов Ичетвертой группы, третьи входы которых подключены к шестому выходу блокауправления, второй вход первого элемента ИЛИ соединен с седьмым выходомблока управления, восьмой выход которого является выходом признака окончания ввода информации, вторые входыэлементов ИЛИ третьей группы соединены с входом задания топологиИ графа,а третьи входы соединены с первойгруппой выходов блока моделированияграфа, вторая группа выходов которогосоединена с вторыми входами соответствующих элементов ИЛИ второй группы,выходы которых соединены с входамиустановки в "1" соответствующих триггеров первой группы, выходы элементовИ четвертой группы соединены с входами установки в " 1" триггеров третьейгруппы..Демчи ор едактор О.Спесив аказ 3482 Й еское предприятие, г, Ужгород, ул. Проектная,игр роизводственн Тираж 704 ВНИИПИ Государственн по делам изобрете 13035, Москва, Ж, РПодписноео комитета СССРй и открытийушская наб., д. 4