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

 

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

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

РЕСПУБЛИК (5l)4 G06 F 15 20

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

К ABTOPCHOMY СВИДЕТЕЛЬСТВУ

l г

ГОСУДАРСТВЕННЫЙ НОМИТЕТ СССР

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИЙ (21) 4059308/24-24 (22) 21.04.86 (46) 07.09.87. Бюл. № ЗЗ (72) Г. H. Лаврик, Ю. И. Скорин, А. Ю. Печунов и И. А. Ручка (53) 681.333 (088.8) (56) Авторско« свидетельство СССР № 1075268, кл. G 06 F 15/20, 1972.

Авторское свидетельство СССР № 118092!, кл. Ci 06 F 15/20, 1984.

154) УС I ÐÎÉСТВО ДЛЯ ВЫДЕЛЕНИЯ .ЧАКСИМА. !ЬНЫХ ВНУТРЕННЕ УСТОЙЧИВЫХ ПО. !лМНО)КЕСТВ ГРАФА (57) Изобрст«ни«относится к вычислительной техник«, мож, т быть использовано для реl. II ив за, )а на графа х и позволяет Вы !

«лять мак«имальны«вн тренние устойчивые подмIíIë.. «; III! вершин, в которых никакая пара в«р шп I!««о«диH«Hа ребром. Устройство сод«ржит Вхо! 1 пуска, генератор 2 и япульсов, матрицу .> моделей ребер, тригг«р 4, эл«м«IITI I 11 5, группу элементов ИЛИ 6, :к гистры 7 — 9 сдвига, группу элементов ИЛИ ! !1, эл«м. II гы И 11 и, ц м«нт 12 задержки.

При пск -уплснии си. и;ила на вход 1, в нулевое сос1ояни«у«т,: швиваются первые разряцы всех р«гпстров 7, в единичное со«1 >инне — - первые и в I! .,I«âîñ состояние—

„„SU„„1336025 д1 все последующие К разрядов регистров 8 и

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

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

К вЂ” х разрядах, К-ую вершину — во вторых разрядах, а в первых разрядах записываются нули. 1 ил.

1336025

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

1

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

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

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

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

И 11 и элемент 12 задержки.

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

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

С поступлением сигнала на вход 1 пуска устройства устанавливаются в нулевое состояние первые разряды всех регистров 7, в единичное состояние первые разряды и в нулевое состояние все последующие К разрядов регистров 8 и 9. В этом случае на первом выходе регистра 9 появляется сигнал, который после прохождения через элементы 10i и l l i обеспечивает занесение первой строки матрицы 3 моделей ребер в первые разряды регистров 7. После этого задержанный в элементе 12 сигнал осуществляет запуск генератора 2 импульсов.

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

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

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

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

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

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

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

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

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

Составитель А. Мишин

Реда кто р С. П атруше в а Техред И. Верес Корректор А. Тяско

Заказ 3804/45 Тираж 672 Подписное

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

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

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

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

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