Устройство для выделения максимальных внутренне устойчивых подмножеств графа Советский патент 1987 года по МПК G06F15/173 

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

Цель изобретения - упрошение конструкции устройства.

На чертеже представлена функциональная схема устройства.

Устройство содержит вход 1 пуска устройства, генератор 2 импульсов, матрицу 3 моделей ребер, триггеры 4, элементы И 5,

вершины графа, соответствующей данной строке матрицы 3 моделей ребер, на возможность ее включения в максимальное внутренне устойчивое подмножество вершин графа, содержащее вершину, выбранную в данном цикле. Если соответствующий элемент И 11 открыт по первому входу сигналом с инверсного выхода первого разряда соответствующего регистра 7; то определяемая им верщина анализируется на предмет 10 исключения из формируемого максимального внутренне устойчивого подмножества всех инцидентных ей верщин. В конце каждого очередного цикла работы устройства (по К-му импульсу генератора 2 в данном

.-.„ , .. ., -, цикле) на прямом выходе (K-f-l)-го разряда

группу элементов ИЛИ 6, регистры 7-9 регистра 8 вырабатывается сигнал, который сдвига, группу элементов ИЛИ 10 элементы осуществляет сдвиг на один разряд содержи- И 11 и элемент 12 задержки.мого регистров 7 и 9. В результате сдвига

Устройство работает следующим образом. содержимого регистра 9 единичный сигнал В матрицу 3 моделей ребер заносится появляется на очередном его выходе. Этот информация о топологии графа, при этом 2о сигнал подготавливает схему устройства к триггеры 4 устанавливаются в единичное очередному циклу аналогично тому, как это

делается по выходному сигналу первого разряда регистра 9.

В конце К-го цикла работы устройства по К-му сигналу на входе признака

вое состояние первые разряды всех регист- 25 сдвига регистра 9 на его выходе (К,+ 1)-го ров 7, в единичное состояние первые раз- разряда появляется единичный сигнал, останавливающий генератор 2 и заверщающий функционирование устройства.

После останова устройства в однои- ,..менных К старших разрядах регистров 7 зачерез элементы 10: и lli обеспечивает за- 30 писывается информация о выделенных макси- несение первой строки матрицы 3 моделей мальных внутренне устойчивых подмножеств ребер в первые разряды регистров 7. После этого задержанный в элементе 12 сигнал осуществляет запуск генератора 2 импульсов. Работа устройства состоит из К циклов, в каждом из которых определяется одно максимальное внутренне устойчивое подмножество, обязательно содержащее вершину совпадающую по номеру с циклом. Искомое множество формиуется в первых разрядах регистров 7.

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

С поступлением сигнала на вход 1 пуска устройства устанавливаются в нулеряды и в нулевое состояние все последующие К разрядов регистров 8 и 9. В этом случае на первом выходе регистра 9 появляется сигнал, который после прохождения

35

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

Сигналы с выхода генератора 2 поступа-Формула изобретения

ют на вход признака сдвига регистра 8 и производят цикличное перемещение единицы, обеспечивая выдачу последовательносУстройство для выделения максимальных внутренне устойчивых подмножеств грати К+1 сигналов с прямых выходов раз- фа, содержащее матрицу моделей ребер.

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

Сигналы с выходов регистра 8 через элементы ИЛИ 10 обеспечивают последовательный просмотр всех элементов И 1I с целью определения необходимости анализа

55

группу регистров сдвига, две группы элементов ИЛИ, группу элементов И, первый регистр сдвига, элемент задержки и генератор импульсов, причем каждый узел матрицы моделей ребер содержит элемент И и триггер, выход которого подключен к первому входу элемента И того же узла матрицы моделей ребер, вход пуска устройства под30 писывается информация о выделенных макси- мальных внутренне устойчивых подмножеств

35

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

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

55

группу регистров сдвига, две группы элементов ИЛИ, группу элементов И, первый регистр сдвига, элемент задержки и генератор импульсов, причем каждый узел матрицы моделей ребер содержит элемент И и триггер, выход которого подключен к первому входу элемента И того же узла матрицы моделей ребер, вход пуска устройства подключей к установочным входам всех регистров сдвига группы, к установочному входу первого регистра сдвига и входу элемента задержки, выход которого подключен к входу пуска генератора импульсов, выход которого подключен к входу управления сдвигом первого регистра сдвига, выход К-го элемента ИЛИ первой группы (,..., М, где М - количество вершин в графе) подключен к первому входу К-го элемента

выход которого подключен к второму входу Р-го элемента И группы, отличающееся тем, что, с целью упрощения устройства, в него введен второй регистр сдвига, причем К-й разряд информационного выхода первого регистра сдвига подключен к первому входу К-го элемента ИЛИ первой группы, (М+ 1)-й разряд информационного выхода первого регистра сдвига подключен к входам управления сдвигом всех регистров

И группы, выход которого подключен к вто-Ю сдвига группы и к информационному входу рым входам элементов И всех узлов К-йвторого регистра сдвига, К-й разряд ин- строки матрицы моделей ребер, выход эле-формационнрго выхода которого подключен мента И К-го узла Р-го столбца матрицык второму входу К-го элемента ИЛИ пер- моделей ребер (,...,М) подключен к К-мувой группы, (М-)-1)-й разряд информацион- входу Р-го элемента ИЛИ второй группы,.с ного выхода второго регистра сдвига под- выход которого подключен к информацион-ключен к входу останова генератора им- ному входу Р-го регистра сдвига группы,пульсов.

выход которого подключен к второму входу Р-го элемента И группы, отличающееся тем, что, с целью упрощения устройства, в него введен второй регистр сдвига, причем К-й разряд информационного выхода первого регистра сдвига подключен к первому входу К-го элемента ИЛИ первой группы, (М+ 1)-й разряд информационного выхода первого регистра сдвига подключен к входам управления сдвигом всех регистров

сдвига группы и к информационному входу второго регистра сдвига, К-й разряд ин- формационнрго выхода которого подключен к второму входу К-го элемента ИЛИ пер- вой группы, (М-)-1)-й разряд информацион- ного выхода второго регистра сдвига под- ключен к входу останова генератора им- пульсов.