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

 

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

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

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

РЕСПУБЛИК (я)5 G 06 F 15/20

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

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

ПРИ ГКНТ СССР

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

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ

ЬЭ

Ql

ЬЭ

Ы (1 (21) 4818951/24 (22) 24.04,90 (46) 07.04.92. Бюл. ЬЬ 13 (72) А.М.Борисов, В.А.Буслаев, А.Б.Щербань и H.È.ß÷êóëà (53) 681.325.(088.8) (56) АвтОрское свидетельство СССР

f4 408312, кл. G 06 F 15/20, 1973.

Авторское свидетельство СССР .М 643880, кл. G 06 F 15/20, 1975. (54) УСТРОЙСТВО ДЛЯ ИССЛЕДОВАНИЯ

ГРАФОВ . (57) Изобретение относится к вычислительной технике и может быть использовано для Ы 1725226 А1 решения задачи выделения максимально полного подграфа графа. Целью изобретения является расширение класса решаемых задач за счет выделения максимально Roilного подграфа исследуемого графа. Поставленная цель достигается тем, что устройство содержит блок 1 задания матрицы смежности графа, блок 2 выбора минимального кода, группу сумматоров 3, триггеры 4 модулей вершин и элемент И 5, причем блок

1 задания смежности графа содержит модели дуг 6, триггер 7 модели дуги, элемент

ИЛИ 8, установочные входы 9, 10. вход 11 начальной установки, тактовый вход 12, выход 13 устройства. 1 ил.

1725226

ЗО

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

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

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

Устройство,содержит блок 1 задания матрицы смежйости графа, блок 2 выбора минимального ko ; группу сумматоров 3, триггеры 4i моделей вершин и элемент И 5 (i = 1,п, где n " число вершин исследуемогО рафа).

Блок 1 задания матрицы смежности графа предназначен для задания топологии исследуемого графй и содержит модели дуг 6, Ц = 1,п.(дугй с индексом И, где i - 1,п, в модели отсутСтвуют). Модели дуг идентичны и содержат триггер 7 модели дуги и элемент

ИЛИ 8. Крбмв T0f о, иа чертеже обозначенй установочные входы 9 и 10 модели дуги, вход 11 начальной установки устройства, тактов ай вход 12 устройства и выход 13 устройСтва, Устройство работает следующим образом. . ".

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

8 этих моделей дуг. С выходов элементов

ИЛИ 8 моделей дуг сигналы поступают на соответствующие входы элемента И 5 и входы соответствующих сумматоров 3i, i = 1,п.

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

Решение начинается подачей импульса на тактовый вход 12 устройства. При этом в блоке 2 осуществляется выбор минимального из входных сигналов и на соответствующем выходе блока появляется импульс уровня логической единицы, который поступает на единичный входтриггера соответствующей модели вершины, например на триггер 4i модели вершины. Триггер 4i модели вершины переходит в единичное состояние и сигнал с его единичного выхода поступает на объединенные входы всех моделей дуг i-го столбца и i-й строки блока

1, моделируя исключение i-й вершины из множества вершин искомого подграфа. С выходов моделей дуг сигналы через их элементы ИЛИ 8 поступают на соответствующие входы элемента И 5 и входы сумматоров

3i, i = 1,ï. Если при этом сигнал уровня логической единицы на выходе 13 устройства не появляется, t6 вновь подается импульс на тактовый вход 12 и начинается следующий шаг решения, который, как и возможные последующие, аналогичен рассмотренному.

Решение завершается, когда после очередного шага решения на всех входах элемента И 6 будут присутствовать сигналы единичного уровня и появится сигнал на выходе устройства 13.

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

Устройство для исследования графов, содержащее группу из и модулей вершин, где n — число вершин исследуемого графа, от л и ч а ю щ е е с я тем, что, с целью расширения класса решаемых задач за счет выделения максимально полного подграфа исследуемого графа, в него дополнительно введены группа сумматоров,.блок выбора минимального кода, элемент И; блок задания матрицы. смежности графа, который содержит матрицу и х и моделей дуг, причем модели дуг с индексом ii, где i = 1,п, в матрице отсутствуют, модель дуги содержит элемент ИЛИ модели дуги и триггер модели дуги, прямой выход которого соединен с первым входом элемента ИЛИ модели дуги, второй и третий входы и выход которого являются соответственно первым и вторым входами и выходом модели дуги, установочные входы триггера модели дуги являются установОчными входами модели дуги, каждая модель вершины представляет собой триггер, выход модели вершины соединен с первыми входами моделей дуг одноименного столбца и вторыми входами моделей дуг одноименной строки блока задания матрицы смежности графы, входы. Слагаемых каждого. из сумматоров группы соединены с выходами одноименной модели дуг одноименного сумматора строки блока задания

1725226

15

30

40

50

Составитель А.Борисов

Техред М,Моргентал Корректор ЭЛончакова

Редактор С.Пекарь

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

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

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

Производственно-издательский комбинат "Патент", r. Ужгород, ул.Гагарина, 101 матрицы смежности графа, выход сумматора группы соединен с одноименным входом блока выбора минимального кода, выходы которого соединены с установочными входами одноименных моделей вершин, входы сброса которых соединены с входом начальной установки устройства, выход каждо модели дуги,соедйнен с одноименным вхоф м элемейта- И,,"выход которого является выходом устройства," вход синхронизации

5 блока выбора мийимального кода является тактовым входом устройства.