Устройство для исследования графов Советский патент 1992 года по МПК G06F15/20 

111

сл

С

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

XI

ю сл ю ю о

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

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

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

Устройство, содержит блок 1 задания матрицы смежности графа, блок 2 выбора минимального Кода, группу сумматоров 3| триггеры 4| моделей вершин и элемент И 5 (i 1,п, где п - число вершин исследуемого

графа)- ; :;

Блёк 1 задания матрицы смежности графа предназначен для задания топологии исследуемого графа и содержит модели дуг 6ц. У 1,п,(Дуги с индексом П, где i 1,n, в модели отсутствуют). Модели дуг идентичны и содержат триггер 7 модели дуги и элемент ИЛИ 8. Кроме того, на чертеже обозначень установочные входы 9 и 10 модели дуги, вход 11 начальной установки устройства, тактоёЫй вхбд 12 устройства и выход 13 устройства.

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

Перед началом решения подачей импульсов уровня логической единицы на установочные входы 9 моделей дуг 6ij, соответствующих имеющимся в исследуемом графе дугам, задается топология графа, а подачей импульса на вход 11 начальной установки устройства Обеспечивается возврат в исходное нулевое состояние триггеров 4i моделей вершин. При этом сигналы уровня логической единицы с единичных выходов триггеров 7 моделей дуг 6ij, соответствующих единичным элементам матрицы смежности исследуемого графа, поступают на первые входы элементов ИЛИ 8 этих моделей дуг. С выходов элементов ИЛИ ё моделей дуг сигналы поступают не соответствующие входы элемента И 5 и BXQJ- ды соответствующих сумматоров 3i, i 1,ri. С выходов сумматоров сигналы, пропорциональные числу единиц в соответствующих строках матрицы смежности исследуемого графа, подаются на информационные входы блока 2 выбора минимального кода.

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

триггер 4) модели вершины. Триггер 4| модели вершины переводит в единичное состояние и сигнал с efb единичного выхода поступает на объединенные входы всех

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

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

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

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

30

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

Устройство для исследования графов, содержащее группу из п модулей вершин, где п - число вершин исследуемого графа, отличающееся тем, что, с целью

5 расширения класса решаемых задач за счет выделения максимально полного подграфа исследуемого графа, в него дополнительно введены группа сумматоров, блок выбора минимального кода, элемент И, блок зада0 ния матрицы смежности графа, который содержит матрицу п х п моделей дуг, причем модели дуг с индексом ii, где i 1,n, в матрице отсутствуют, модель дуги содержит элемент ИЛИ модели дуги и триггер модели

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

матрицы смежности графа, выход сумматора группы соединен с одноименным входом блока выбора минимального кода, выходы которого соединены с установочными входами одноименных моделей вершин, входы сброса которых соединены с входом начальной установки устройства, выход каждое модели дуги соединен с одноименным вхо- Јфм элементаИ, 4ш6д которого является выходом устройстЁЭ, вход синхронизации блока выбора минимального кода является тактовым входом устройства.