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

СОЮЗ СОВЕТСКИХСОЦИАЛИСТИЧЕСКИХРЕСПУБЛИК ОПИСАНИ К АВТОРСКОМ,Ф ТЕНИЯ ЕТЕЛЬСТВУ.Крикунов ьство СССР /20, 1974. тво СССР /20, 1977. ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССРПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИЙ(54)(57) УСТРОЙСТВО ДЛЯ ИССЛЕДОВАНИЯГРАФОВ, содержащее блок управления,генератор импульсов, группу элементов ИЛИ и матрицу Н М моделей ребер,причем каждая модель ребра содержиттриггер, о т л и ч а ю щ е е с ятем, что, с целью расширения функционапьных воэможностей путем определения максимальных внутренне устойчивыхподмножеств вершин, в него введенагруппа регистров, а в каждую модельребра - элемент И, блок управлениясодержит .регистр, счетчик, дешифратор, три элемента задержки, группыэлементов ИЛИ и элементов И, выходыи первые входы которых соединенысоответственно с первыми входамиэлементов И моделей ребер одноименных строк матрицы моделей ребер ис нулевыми выходами первых разрядоводноименных регистров, вторые входы элементов И группы блока управления подключены к выходам одноименых элементов ИЛИ блока управления, выходы регистра блока управления соединены с первыми входами одноименных элементов ИЛИ группы блока управления, М выходов дешифратора подключены к вторым входам одноименных элементов ИЛИ группы блока управления, ( 11 +1 )-й выход дешифратора соединен с входом останова генератора импульсов, вход дешифратора подключен к выходу счетчика,8 -й выход регистра блока управления через первый элемент задержки соединен с входами сдвига регистров, а через второй элемент задержки - со счетным входом счетчика, установочный вход которого соединен с входом третьего элемента задержки, установочным входом регистра блока управления, 8 установочными входами регистров и является установочным входом устрой, ства, выход третьего элемента задержки подключен к входу запуска генератора импульсов, выход которого соединен с входом сдвига регистра блока управления, выход трйггера каждой модели ребра подключен к второму входу элемента И модели ребра, выходы элементов И моделей ребер каж" цого столбца матрицы моделей ребер соединены с входами одноименного элемента ИЛИ группы, выход которого фв соединен с входом первого разряда одноименного регистра, 1180921Изобретение относится к вычислительной технике, в частности к решению на графах задач выделения максимальных внутренне устойчивых подмножеств, не являющихся собствен ным подмножеством никакого другого внутренне устойчивого подмножества, в котором никакая пара вершин не соединена ребром.Цель изобретения - расширение функциональных воэможностей путем определения максимальных внутренне устойчивых подмножеств вершин.На фиг. 1 приведена структурная схема устройства; на фиг. 2 - струк турная схема блока управления.Устройство содержит блок 1 управления, генератор 2 импульсов, матрицу 3 1 Н моделей ребер, причем каждая модель содержит триггер 4 и элемент И 5, И элементов ИЛИ 6, М регистров 7. Блок 1 управления содержит регистр 8, счетчик 9, дешифратор 10, первый 11, второй 12 и третий 13 элементы задержки, М эле ментов ИЛИ 14 и И элементов И 15.Устройство работает следующим образом.В матрицу 3 моделей ребер заносится информация о топологии графа, 30 при этом триггеры 4 устанавливаются в единичное состояние согласно матрице смежности графа. ЪО С поступлением сигнала на установочный вход устройства устанавливаются в нулевое состояние первыеразряды всех регистров 7,устанавливаются в единичное состояние нулевой разряд и в нулевое состояние 4 Оостальные Ю разрядов регистра 8,сбрасывается в нулевое состояниесчетчик 9, на первом выходе дешифра-.тора 10 вырабатывается сигнал, который через элементы ИЛИ 14, И 15 1,И 5- И 5 р, ИЛИ 61 - ИЛИ 6,1 обеспечивает занесение первой строкиматрицы 3 моделей ребер в первыеразряды регистров 7. Через третийэлемент 13 задержки осуществляетсязапуск генератора 2,Работа устройства состоит из Я циклов, в каждом из которых определятся одно максимальное внутренне устойчивое подмножество, обя-, зательно содержащее вершину, йомер которой определяется содержимым счетчика 9. Искомое множество формируется в первых разрядах регистров 7.Сигналы с нулевых выходов первых разрядов регистров 7 поступают на первые входы соответствующих элементов И 15 и обеспечивают возможность дальнейшего анализа на связность только тех вершин которые не инцидентны с заданной в данном цикле вершиной.Сигналы с выхода генератора 2 поступают на сдвигающий вход регистра 8 и производят цикличное перемещение единицы, обеспечивая выдачу последовательности И+1 сигналов с единичных выходов разрядов регистра 8, которая определяет цикл работы устройства по выделению одного максимального внутренне устойчивого подмножества вершин графа.Сигналы с выходов регистра 8 через элементы ИЛИ 14 обеспечивают последовательный просмотр всех элементов И 15 с целью определения необходимос-. ти анализа вершин графа, соответствующей данной строке матрицы 3 моделей ребер, на возможность ее включения и максимальное внутренне устойчивое подмножество вершин графа, содержащее вершину, выбранную в данном цикле. Если соответствующий элемент И 15 открыт по первому входу от нулевого выхода первого разряда соответствующего регистра 7, то определяемая им вершина анализируется на предмет исключения из формируемого максимального внутренне устойчивого подмножества всех инцидентных ей вершин. В конце каждого очередного цикла работы устройства ( по Ю"у импульсу генератора 2 в .данном цикле) на единичном выходе В-го разряда регистра 8 вырабатывается сигнал, который, кроме обычных действий, через первый элемент 11 задержки осуществляет сдвиг на один разряд содержимого регистров 7 и через второй элемент 12 задержки увеличивает на единицу содержимое счетчика 9, Выходной сигнал с соответствующего выхода дешифратора 10 подготавливает схему устройства к очередному циклу аналогично тому, как это делается по выходному сигналу с первого выхода дешифратора 10 в первом цикле. Последний (В +1)-й ф импульс генератора 2 в каж,ом цикле работы устройства осуществляет цик3 1 лический сдвиг М - го н нулевой разряд регистра 8, завершая тем самым подготовку устройства к следующему циклу выделения очередного максимального внутренне устойчивого подмножества вершин графа.В конце каждого цикла информация о топологии исследуемого графа сохраняется в матрице 3 моделей ребер,в нулевом разряде регистра 8 записана единица, в остальных его разрядах - нули, содержимое счетчика 9 увеличено на единицу, информация о ранее сформированных максимальных внутренне устойчивых подмножествах вершин графа зафиксирована в одноименных разрядах регистров 7 и сдвинута в один разряд в сторону старших разрядов в первые разряды регистров)7 занесена строка матрицы 3 моделей ребер, которая обязательно включается в максимальное внутренне устойчивое подмножество вершин графа, формируемое в следующем цикле работы устройства.В конце И-го цикла работы устройства по И-у импульсу генератора 2 выполняются действия, аналогичные действиям по И-у импульсу генератора 2 в предыдущих циклах, за исклю 180921 4чением того, что увеличение на единицу содержимого счетчика 9 приводит к появлению сигнала на (М + 1) -м выходе дешифратора 10, который поступает на запрещающий вход генератора 2 и останавливает работу устройства. После завершения работы устройст О ва в одноименных Н старших разрядахрегистров 7 записывается информацияо выделенных максимальных внутреннеустойчивых подмножествах вершин,содержащих все вершины графа. Приэтом характеристика максимальноговнутренне устойчивого подмножества,содержащего первую вершину графа,записывается в (И + 1)-х разрядахрегистров 7, содержащего вторую вер шину в н-х разрядах содержащегоИ-ю вершину во вторых разрядах, ав первых разрядах записываются нули,Вершина графа входит в максимальноевнутренне устойчивое подмножество 25 вершин графа, если в регистре 7, соответствующем данной вершине, в разряде, соответствующем данному максимальному внутренне устойчивомуподмножеству вершин, записан нуль, ине входит, если записана единица.1ректор Е.Сирохм акаэ г. Уа д, ул. Проектная, 4 Филиал ППП "Пат 5928/49 Тираз ВНИИПИ Государст по делам изобр 113035, Москва,Ж, 709 Подлисенного комитета СССРтений и рткрытийРаушская наб., д. 4/5