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

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

50-

фиг.1

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

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

На фиг. 1 представлена функционал ная схема устройства; на фиг. 2 - функциональная схема блока определения компонент вершинной связности графа.

Устройство содержит блок 1 формирования комбинаций, блок 2 определения компонент вершинной связности графа, сумматор 3, блок 4 выбора минимального кода, первый тактовый вхо 5 устройства, выход 6 признака окончания работы устройства, второй тактовый вход 7 устройства, выход 8 числа вершинной связности графа устройства, выход 9 признака обновления числа вершинной связности устройства Блок 2 содержит узел 10 определения смежных верпшн графа, группу из В отключающих элементов, входы 2 опроса вершин графа, выходы 13 признаков соответствия вершин графа компонентам реберной связности, сумматор J4, узел.)5 сравнения, выход J6 признака наличия компонент связности.

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

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

5

0

5

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

Блок 2 работает следующим образом.

В блок 10 заносят информацию о топологии графа в виде матрицы смеж-; ности его вершин. Определяют общее количество вершин подграфа (заданного набором единиц на соответствующих входах 12 блока 2) и вершин, смежных с ними. Если это количество меньше количества вершин в графе (В), на выходе узла 15 сравнения появляется сигнал уровня логической единицы. При этом вершины, смежные с вершинами подграфа (исключая последние) , соответствуют компонентам вершинной связности.

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

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

0

5

0

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

определения компонент вершинной связ- зо связности блока.

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

20 М-го отключающего элемента, выход которого является выходом признака соответствия М-й вершины графа компоненте вершинной связности блока и подключен к входу М-го слагаемого

25 второй группы сумматора, выход которого подкхпочен к информационному входу узла сравнения, выход признака меньше которого является выходом признака наличия компонент вершинной