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

ментов ИЛИ 6, группу из Р регистров 7 сдвига, регистр 8 сдвига, элемент ИЛИ 9, четвертый элемент 10 задержки третий элемент 11 задержки, второй элемент 2 задержки, первый элемент 13 задержки, вторую группу из Р элементов ИЛИ 14, группу из Р элементов И 15 и вход 16 пуска устройства. Используя генератор 2 импульсов и регистр 8 сдвига, устройство обеспечивает последовательный анализ всех строк матриць 3 моделей ребер на предмет исключения из формируемого максимального внутренне устойчивого подмножества всех вершин, инцидентных рассматриваемой. Для этого сиг1

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

Целью изобретения является повьше- ние быстродействия устройства при вы- делении максимальных внутренне устойчивых подмножеств.

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

Устройство содержит блок 1 управления , генератор 2 импульсов, матрицу 3 из Р х Р моделей ребер, где Р - количество вершин в графе, триггеры 4, элементы И 5, первую группу из Р элементов ИЛИ 6 .группу из Р регистров 7 сдвига, регистр 8 сдвига, элемент ИЛИ 9, четвертый элемент 10 задержки, третий элемент 11 задержки, второй элемент 12 задержки, первый элемент 13 задержки, вторую группу из Р элементов ИЛИ 14, группу из Р элементов И 15 и вход 16 пуска устройства.

Устройство работает следующим об разом.

В матрице 3 моделей ребер содержится информация о ТОПОЛО.ГИИ графа, при этом соответствующие триггеры

;

налы с выходов открытых элементов И 15, проходя через открытые элементы И 5, эfIeмeнты ИЛИ 6 на информационные входы регистров 7, устанавливают первые входы указанных регистров 7 в единичное состояние, что соответствует исключению вершины из формируемого подмножества. По окончании анализа всех строк матрицы 3 характеристика максимального внутренне устойчивого подмножества, содержащего первую вершину графа, записана в (Р + 1)-х разрядах регистров 7, а характеристика подмножества, содержащего Р-ю вершину графа, - во вторых разрядах регистров 7. 1 ил.

51

25

30

установлень: в единичное состояние согласно матрице смежности графа.

С поступлением сигнала на вход 16 устройства первые разряды всех регистров 7 устанавливаются в нулевое состояние, первый разряд регистра 8 - в единичное состояние.

Сигнал с первого разряда информа ционного регистра 8 проходит ты ИЛИ 14,, И 15,, И 5 ,,,... 5 ,р и ИЛИ 6 ,... бр и обеспечивает занесение первой строки матрицы 3 моделей ребер в первые разряды регистров 7.

Этот же сигнал через элемент ИЛИ 9, элемент 10 задержки и элементы ИЛИ 14,... 14р проходит через те

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

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

Сигнал с выхода элемента I1 задержки производит сдвиг информации в регистрах 7, а сигнал с выхода элемента 13 задержки, величина времени задержки которого больше суммы времени задержек от элементов 10 и II, за- 15 содержащего вторз вершину, в Р-х

пускает генератор 2 импульсов.

Работа устройства состоит из Р циклов (Р-1 тактов генератора импульсов) . В каждом цикле вьщеляется одно максимальное внутренне устойчивое подмножество, обязательно содержащее вершину, номер которой совпадает с номером разряда информационного выхода регистра 8 установленного в единичное состояние. Искомое множество формируется в первых разрядах регистров 7 за четыре шага.

На первом шаге импульс с генератора 2 производит сдвиг информации в регистре 8. Появившийся на втором выходе регистра 8 сигнал проходит элементы ИЛИ 14, И 15, И 5 , 52,р, ШШ 6,,. производит запись второй строки матрицы 3 моделей ребер в первые разряды регистров 7. На третьем шаге сигнал с выхода элемента 10 задержки поступает в матрицу 3 моделей ребер, через открытые элементы И 15,,... 15р- на входы элементов И 5 соответствующих строк матрицы.

Если хотя бы один триггер 4 в рассматриваемой строке находится в единичном состоянии, единичный сигнал с его выхода проходит через открытый элемент И 5, элемент ИЛИ 6 и устанавливает первый разряд соответствующего регистра 7 в состояние 1.

На четвертом шаге сигнал с выхода

6р и на втором шаге

элемента 11 задержки производит сдвиг gQ которого подключен к вторым входам информации в регистре 7. всех элементов И моделей ребер М-й

Второй импульс с выхода генератора 2 производит сдвиг информации в регистре 8. Единичный потенциал появляется на третьем выходе регистра, и работа устройства повторяется,

(Р-1)-и импульс генератора 2 з.апус- кает формирование Р-го максимального внутренне устойчивого подмножества

графа и через элемент 12 задержки останавливает генератор 2.

)

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

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

му внутренне устойчивому подмножеству вершин, записан О, и не входит, если записана 1.

Формула изобретения

Устройство для исследования подмножеств графа, содержащее матрицу из Р X Р моделей ребер, где Р - количество верщин в графе, генератор импульсов , две группы ИЗ Р элементов

ШШ, группу из Р элементов И, группу из Р регистров сдвига, регистр сдвига и три элемента задержки, причем каждая модель ребра матрицы содержит элемент И и триггер, выход которого

подключен к первому входу элемента

И той же модели ребра матрицы, вы- ход элемента И М-й модели ребра

(М 1,...,Р) К-й строки (,...,Р) матрицы подключен к К-му входу М-го

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

строки матрицы, вход пуска устройства подключен к установочному входу регистра сдвига, к установочным входам всех регистров сдвига группы и к входу элемента задержки, выход которого подключен к входу пуска гене ратора импульсов, выход которого подключен к входу признака сдвига ре51363236

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

Изобретение относится к вычислительной технике и предназначено для решения задачи на графах, в частности для вьщеления максимальных внутренне устойчивых подмножеств, не являющихся собственными подмножествами никакого другого внутренне устойчивого подмножества. Цель изобретения - повьшение быстродействия устройства при вьщелении максимальных внутренне устойчивых подмножеств. Устройство содержит блок 1 управления, генератор 2 импульсов, матрицу 3 из Р X Р моделей ребер, где Р - количество вершин в графе, триггеры 4, элементы И 5, первую группу из Р элеСЛ