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

Изобретение относится к вычислительной технике, в частности к решению на графах задач выделения максимальных внутренне устойчивых подмножеств, не являющихся собствен ным подмножеством никакого другого внутренне устойчивого подмножества в котором никакая пара вершин не соединена ребром. Цель изобретения - расширение функциональных возможностей путем определения максимальных внутренне устойчивых подмножеств вершин. На фиг. 1 приведена структурная схема устройства; на фиг. 2 -.струк турная схема блока управления. Устройство содержит блок 1 управ ления, генератор 2 импульсов, матрицу 3 NN моделей ребер, причем каждая модель содержит триггер 4 и элемент И 5, N элементов ИЛИ 6,М регистров 7. Блок 1 управления со держит регистр 8, счетчик 9, дешиф ратор 10, первый 11, второй 12 и третий 13 элементы задержки, N эле ментов ИЛИ 14 и N элементов И 15. Устройство работает следующим образом. В матрицу 3 моделей ребер заносится информация о топологии графа при этом триггеры 4 устанавливаются в единичное состояние согласно матрице смежности графа. С поступлением сигнала на установочный вход устройства устанавливаются в нулевое состояние первы разряды всех регистров 7,устанавли ваются в единичное состояние нулевой разряд и в нулевое состояние остальные N разрядов регистра 8, сбрасывается в нулевое состояние счетчик 9, на первом выходе дешифр тора 10 вырабатывается сигнал, кот рый через элементы ИЛИ 14, , И 15, И 5, - И SN , ИЛИ 6, - ИЛИ 6, обес печивает занесение первой строки матрицы 3 моделей ребер в первые разряды регистров 7. Через третий элемент 13 задержки осуществляется запуск генератора 2. Работа устройства состоит из N циклов, в каждом из которых определятся одно максимальное внутренне устойчивое подмножество, обя зательно содержащее вершину, HONfep которой определяется содержимым счетчика 9. Искомое множество фор- 12 мируется в первых разрядах регистров 7. Сигналы с нулевых выходов первых разрядов регистров 7 поступают на первые входы соответствующих элементов И 15 и обеспечивают возмож : ность дальнейшего анализа на связность только тех вершин которые не инцидентны с заданной в данном цикле вершиной. Сигналы с выхода генератора 2 поступают на сдвигающий вход регистра 8 и производят цикличное перемещение единицы, обеспечивая выдачу последовательности N+1 сигналов с единичных выходов разрядов регистра 8, которая определяет цикл работы устройства по вьщелению одного максимального внутренне устойчивого подмножества вершин графа. Сигналы с выходов регистра 8 через элементы ИЛИ 14 обеспечивают последовательный просмотр всех элементов И 15 с целью определения необходимое-; пи анализа вершин графа, соответствующей данной строке матрицы 3 моделей ребер, на возможность ее включения и максимальное внутренне устойчивое подмножество- вершин графа, содержащее вершину, выбранную в данном цикле. Если соответствующий элемент И 15 открыт по первому входу от нулевого выхода первого разряда соответствующего регистра 7, то определяемая им вершина анализируется на предмет исключения из формируемого максимального внутренне устойчивого подмножества всех инцидентных ей вершин. В конце каждого очередного цикла работы устройства ( по N-y импульсу генератора 2 в данном цикле) на единичном выходе N-ro разряда регистра 8 вырабатьгоается сигнал, который, кроме обычных действий, через первый элемент 11 задержки осуществляет сдвиг на один разряд содержимого регистров 7 и через второй элемент 12 задержки увеличивает на единицу содержимое счетчика 9. Выходной сигнал с соответствующего выхода дешифратора 10 подготавливает схему устройства к очередному циклу аналогично тому, как это делается по выходному сигналу с первого выхода дешифратора 10 в первом цикле. Последний (N +1)-й импульс генератора 2 в кажд.ом цикле ) работы устройства осуществляет цик3

лический гдвиг N -го в нулевой разряд регистра 8, завершая тем самым подготовку устройства к следующему 1диклу вьщеления очередного максимального внутренне устойчивого подмножества вершин графа.

В конце каждого цикла информация о топологии исследуемого графа сохраняется в матрице 3 моделей ребер,в нулевом разряде регистра 8 записана единица, в остальных его разрядах нули, содержимое счетчика 9 увеличено на единицу, информация о ранее сформированных максимальных внутренне устойчивых подмножествах вершин графа зафиксирована в одноименных разрядах регистров 7 и сдвинута в один разряд в сторону старших разрядов в первые разряды регистров 7 занесена строка матрицы 3 моделей ребер, которая обязательно включается в максимальное внутренне устойчивое подмножество вершин графа, формируемое в следующем цикле работы устройства.

В конце N-ro цикла работы устройства по N-y импульсу генератора 2 выполняются действия, аналогичные действиям по N-y импульсу генератора 2 в предыдущих циклах, за исклю809214

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

После завершения работы устройства в одноименных N старших разрядах регистров 7 записывается информация о вьщеленных максимальных внутренне устойчивых подмножествах вершин, содержаш 1х все вершины графа. При

15 этом характеристика максимального внутренне устойчивого подмножества, содержащего первую вершину графа, записывается в (N +1)-х разрядах регистров 7, содержащего вторую вершину в N-X разрядах содержащего N-ro вершину во вторых разрядах, а в первых разрядах записываются нули. Вершина графа входит в максимальное внутренне устойчивое подмножество

5 вершин графа, если в регистре 7, соответствующем данной верпшне, в разряде, соответствующем данному максимальному внутренне устойчивому

подмножеству вершин, записан нуль, и

0 не входит, если записана единица.

УСТРОЙСТВО ДНЯ ИССЛЕДОВАНИЯ ГРАФОВ, содержащее блок управления, генератор импульсов, группу элементов ШШ и матрицу NN моделей ребер, причем каждая модель ребра содержит триггер , отличающееся тем, что, с цепью расширения функциональных возможностей путем определения максимальных внутренне устойчивых подмножеств вершин, в него введена группа регистров, а в каждую модель ребра - элемент И, блок управления содержит регистр, счетчик, дешифратор, три элемента задержки, группы элементов ИЛИ и элементов И, выходы и первые входы которых соединены соответственно с первыми входами элементов И моделей ребер одноименных строк матрицы моделей ребер и с нулевыми выходами первых разрядов одноименных регистров, вторые входы элементов И группы блока управления подключены к выходам одноименных элементов ИЛИ блока управления, выходы регистра блока управления соединены с первыми входами одноименных элементов ИЛИ группы блока управления, N выходов дешифратора подключены к вторым входам одноименных элементов ИЛИ группы блока управления, (N +1 )-й выход дешифратора соединен с входом останова генератора импульсов, вход дешифратора подключен к выходу счетчика, N -и выход регистра блока управления через первый элемент задержки соединен с входами сдвига регистров, а через второй элемент задержки - со (Л счетным входом счетчика, установочный вход которого соединен с входом третьего элемента задержки, установочным входом регистра блока управления, S установочными входами регистров и .является установочным входом устройг , ства, выход третьего элемента задержки подключен к входу запуска генератора импульсов, выход которого соединен с входом сдвига регистра блока управления, выход триггера каждой модели ребра подключен к второму входу элемента И модели ребра, выходы элементов И моделей ребер каждого столбца матрицы моделей ребер соединены с входами одноименного элемента ШШ группы,выход которого соединен с входом первого разряда одноименного регистра.