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

 

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

СОЮЗ СОВЕТСКИХ

СОЦИАЛИСТИЧЕСКИХ

РЕСПУБЛИК

„„Я0„„1363236 (51)4 G 06 F 15/20

I

ОПИСАНИЕ ИЗОБРЕТЕНИЯ "; „ц, М АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (54) УСТРОЙСТВО ДЛЯ ИССЛЕДОВАНИЯ

ПОДМНОЖЕСТВ ГРАФА (21) 4090582/24-24 (22) 18. 07. 86 (46) 30.12.87. Бюл. Р 48 (71) Ленинградский электротехнических институт им. В.И.Ульянова (Ленина) (72) Т.В.Волченская, В.С.Князьков, В.С.Дудкин и Д.П.Пуолокайнен (53) 681.333(088.8) (56) Авторское свидетельство СССР

Р 716043, кл. С 06 F 15/20, 1977.

Авторское свидетельство СССР

Ф 1180921, кл. G 06 F 15/20, 1984. (57) Изобретение относится к вычислительной технике и предназначено для решения задачи на графах, в частности для выделения максимальных внутренне устойчивых подмножеств, не являющихся собственными подмножествами никакого другого внутренне устойчивого подмножества. Цель изобретения — повышение быстродействия устройства при выделении максимальных внутренне устойчивых подмножеств.

Устройство содержит блок 1 управления, генератор 2 импульсов, матрицу

3 из P x P моделей ребер, где P — количество вершин в графе, триггеры 4, элементы И 5, первую группу из P злеЖ

1363236 ментов ИЛИ 6, группу из P регистров

7 сдвига, регистр 8 сдвига, элемент

ИЛИ 9, четвертый элемент 10 задержки, третий элемент 11 задержки, второй элемент 12 задержки, первый элемент

13 задержки, вторую группу из P элементов ИЛИ 14, группу из Р элементов

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

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

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

Устройство содержит блок 1 управления, генератор 2 импульсов, матрицу 3 из Р х Р моделей ребер, где P —количество вершин в графе, триггеры

4, элементы И 5, первую группу из Р элементов ИЛИ 6; .группу из P регистров 7 сдвига, регистр 8 сдвига, элемент ИЛИ 9, четвертый элемент 10 задержки, третий элемент 11 задержки, второй элемент 12 задержки, первый элемент 13 задержки, вторую группу из P элементов ИЛИ 14, группу из Р элементов И 15 и вход 16 пуска устройства.

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

В матрице 3 моделей ребер содержится информация о топологии графа, при этом соответствующие триггеры налы с выходов открытых элементов

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

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

8 — в единичное состояние.

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

Этот же сигнал через элемент ИЛИ

9, элемент 10 задержки и элементы

ИЛИ 14,... 14О проходит через те элементы И 15, на первые входы которых поступают единичные сигналы с информационных выходов регистров 7.

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

25 заданной в данном цикле, т.е. в рассматриваемом случае — с первой.

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

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

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

На первом шаге импульс с генератора 2 производит сдвиг информации в регистре 8. Появившийся на втором 30 выходе регистра 8 сигнал проходит элементы ИЛИ 14, И 15, И 5 д У ° ° °

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

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

На четвертом шаге сигнал с выхода элемента 11 задержки производит сдвиг 5р информации в регистре 7.

Второй импульс с выхода генератора 2 производит сдвиг информации в регистре 8 ° Единичный потенциал появляется на третьем выходе регистра, и работа устройства повторяется, (P-1)-й импульс генератора 2 запускает формирование P-ro максимального внутренне устойчивого подмножества

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

На этом работа устройства заканчивается. В одноименных P-x старших разрядах регистров 7 записана.информация о выделенных максимальных внутренне устойчивых подмножествах вершин, содержащих все вершины графа.

Причем характеристика максимального внутренне устойчиваого подмножества, содержащего первую вершину графа, записана в (P + 1)-х разрядах регистров 7; характеристика подмножества, содержащего вторую вершину, в P-x разрядах; характеристика подмножества, содержащего P-ю вершину, во вторых разрядах регистров 7. Вершина графа входит в максимальное внутренне устойчивое подмножество вершин графа, если в регистре 7, соответст- . вующем данной вершине, в разряде, соответствующем данному максимальному внутренне устойчивому подмножеству вершин, записан "011ý и не входит, если записана "1".

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

Устройство для исследования подмножеств графа, содержащее матрицу из P x P моделей ребер, где P — количество вершин в графе, генератор импульсов, две группы из P элементов

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

И той же модели ребра матрицы, выход элемента И M-й модели ребра (М = 1,...,P) К-й строки (K=1, P) матрицы подключен к К-му входу M-ro

Ъ элемента ИЛИ первой группы, выход которого подключен к информационному входу М-ro регистра сдвига группы, выход которого-подключен к первому входу M-го элемента И группы, выход. которого подключен к вторым входам всех элементов И моделей ребер М-й строки матрицы, вход пуска устройства подключен к установочному входу регистра сдвига, к установочным входам всех регистров сдвига группы и к входу элемента задержки, выход которого подключен к входу пуска гене.— ратора импульсов, выход которого подключен к входу признака сдвига реСоставитель А.Мишин.

Техред М,Дидык . Корректор О.Кравцова

Редактор А.Маковская

Тираж 671 Подписное

ВНИИПИ Государственного комитета СССР Р по делам изобретений и открытий

113035, Москва, Ж-35, Раушская .наб., д. 4/5

Заказ 6364/42

Производственно-полиграфическое предприятие, г. Ужгород, ул. Проектная, 4

5 136 гистра сдвига, М-й разряд информационного выхода которого подключен к первому входу M-го элемента ИЛИ второй группы, выход которого подключен к второму входу M-ro элемента И, P-й разряд информационного выхода регистра сдвига подключен к входу второго элемента задержки, выход которого

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

5 четвертый элемент задержки, причем

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

ИЛИ второй группы.