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

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

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

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

Устройство содержит блок 1 элементов ИЛИ, блок 2 регистрации вершин внутренне устойчивого подмножества блок 3 определения смежных вершин, блок 4 регистрации матрицы смежности, входы Б задания центральной вершины подмножества устройства, вход 6 опроса устройства и вь1- ходы 7 признаков принядпежнос и вершин подмножеству пнуфенне устойчив х

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

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

Перед началом работу разряды Гмока 2 устанавливают в единицу и блок ; р-.ги страции матрицы омежж гли i;n им

О 00

vj О

формацию о топологии графа. На К-й вход 5 задания центральной вершины подмножества подают сигнал уровня логической единицы. При этом блок 3 определения смежных вершин выдает сигналы уровня логической единицы на те свои выходы признаков, которые соответствуют вершинам, принадлежащим множеству смежных с центральной. Через время, достаточное для выполнения указанной операции, на вход б опроса устройства подают сигнал уровня логической единицы. При этом блок,2 регистрации устанавливает в ноль те из своих разрядов, которым соответствуют единичные сигналы на его устано- вочных входах (т.е. из подмножества внутренне устойчивых исключаются вершины, смежные с центральной). При этом на выходах 7 устройства будет сформирован состав внутренне устойчивых вершин, включающих К-ю вершину.

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

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

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