Устройство для решения задач на графах

Устройство для решения задач на графах

Иллюстрации

Показать все

Реферат

 

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

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

СОЦИАЛИС(ИЧГСКИХ

РЕСПУВЛИК

1684796 А1

<5i ) g 06 f 15>

ГОСУД>3РСТВЕННЬ<Й КОМИ1Г >

ПО ИЗОБРЕТЕНИЯМ И О1КРЫТИЯМ

ПРИ ГКНТ СССР

В« Г.:2ЯЗИР

ОПИСАНИЕ ИЗОБРЕТЕНИЯ ос 00 ф

) 4 ()»

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (21) 4634478/24 (22) 09.01.89 (46) 15.10.91. Бюл. М 38 (71) Таганрогский радиотехнический институт им. В.Д. Кал м ы ко ва (72) В,M.Ãëóøàíü,.Â.М.Курейчик и А.В.Пришибской (53) 681.333(088.8) (56) Авторское свидетельство СССР

М 1180921, кл. G 06 F 15/20, 1984.

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

М 1363236, кл. G 06 F 15/20, 1986 (54) УСТРОЙСТВО ДЛЯ РЕШЕНИЯ ЗАДАЧ

НА ГРАФАХ (57) Изобретение относится к вычислительной технике и может быть использовано для определения внутренне устойчивых подмножеств. Целью изобретения является повышение быстродействия устройства при решении задач определения внутрен><е устойчивых подмножеств графа, Устройство

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

Целью изобретения является полы>ление быстродействия устройства I

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

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

На К-й вход 5 задания центральной вершины подмножества и põoä 6 опроса подают сигнал уровня лсгической единицы. При этом на выходах 7 устройс<ва будет сформирован состав в<>у, ре»;<е уста><чивых вершин, включающих К-ю вершину. 1 ил гистрации матрицы смеж<>ости, входы 5 задания центральной вершины подм>к>жества устройства, вход 6 ОГ1 Г30сд устройст вэ и >3> ходы 7 приз>;аков принадлежнос>и 13epl>II»<

><од>лно>кеству в><у<ренне устой ив> х

Ус3 ройство pa63o3se I слв ly><3. оГ<разо;л.

Пусть необходимо определит> <3> > тр»-:<не устойчивое подMI ожество вег.:!l1>< I < афа, включающих заданну>,3, н -3>lp> Hoð К->о (це><тральную), вершину.

Перед на <алом рабсты рл 3r3яд>< б;>ока

2 устанавливают >3 единицу. в hi>. г.:,гистрации >латр>1цt< с>л -жн от и

1684796

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

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

Редактор Н.Каменская Техред M.Ìîðãåíòàë Корректор А.Осауленко

Заказ 3508 Тираж Подписное

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

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

Производственно-издательский комбинат "Патент", г. Ужгород, ул.Гагарина, 101 формацию о топологии графа. На К-й вход

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

 — количество вершин в графе) подключен

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

15 подключен к входу опроса К-й вершины блока определения смежных вершин, выход признака принадлежности M-й вершины множеству смежных которого подключен к входу установки в ноль М-го разряда блока

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