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

Авторы патента:

G06F15/173 - с использованием сети связи, например, соединение по схеме матрицы, смешанное соединение, соединение по схеме пирамиды, звезды, снежинки (схемы переключения интерфейсов G06F 13/40)

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

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

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

РЕСПУБЛИК

А1 (19) (111 ($1) 4 С 06 F 15/20

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

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

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

ПРИ ГКНТ СССР

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (21) 4358165/24-24 (22) 25. 3 1.87 (46) 07.12,89. Бюл. В 45 (72) В.Л. Львов н, А.В. Подлелсанский (53) 681 . 333 (088. 8) (56) Авторское свидетельство СССР !

1 888134, кл. С 06 F 15/36, 1981.

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

У 1465891, кл. С 06 F 15/20, 04,02,87, (54) УСТРОЙСТВО ДЛЯ АНАЛИЗА ПАРАМЕТР0В ГРАФА (57) Изобретение относится к вычислительной технике и может быть использовано для определения числа,вершинной связности графа. С этой целью устройство содеркит блок 1 формирования комбинаций, блок 2 определения

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

1527640

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

Целью изобретения является расши5 рение функциональных возможности устройства за счет определения числа вершинной связности графа, На фиг. 1 представлена функциональ-1ð ная схема устройства; на фиг. 2 функциональная схема блока определения компонент вершинной связности графа °

Устройство содержит блок 1 форми15 рования комбинаций, блок 2 определения компонент вершинной связности графа, сумматор 3, блок 4 выбора минимального кода, первый тактовый вход

5 устройства, выход 6 признака окончания работы устройства, второй тактовый вход 7 устройства, выход 8 числа вершинной связности графа устройства, выход 9 признака обновления числа вершинной связности устройства. 25

Блок 2 содержит узел 10 определения смежных вершин графа, группу из

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

14, узел.15 сравнения, выход 16 признака налиЧия компонент связности, Устройство работает следующим образом, 35

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

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

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

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

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

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

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

I вход которого является вторым такто40

72д

Составитель А. Мишин

Редактор В. Петраш Техред Л.Сердюкова Корректор Т. Палий

Заказ 7511/53 Тираж 658 Подписное

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

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

Производственно-издательский комбинат "Патент", r.Óæãîðîä, ул. Гагарина,101

5 15276 вым входом устройства, о т л и ч а ю щ е е с я тем, что, с целью расширения функциональных воэможностей устройства эа счет определения числа вершинной связности графа, в него введен блок определения компонент вершинной связности графа, причем М-й разряд информационного выхода блока формирования комбинаций (М=1,..., В> где В вЂ” количество вершин в графе) подключен к входу опроса М-й вершины блока определения компонент вершинной связности графа, выход признака соответствия М-й вершины графа компонента 15 верппснной связности которого подключен к входу М-го слагаемого сумматора, информационный выход блока выбора минимального кода является выходом числа вершинной связности графа уст- 2О ройства, а выход признака "не больше" блока выбора минимального кода вЂ” выходом признака обновления числа вершинной связности устройства, выход признака завершения перебора комби- 25 наций блока формирования комбинаций является признаком окончания работы устройства, выход признака наличия компонент вершинной связности блока определения компонент вершинной связности подключен к входу разрешения работы блока выбора минимального кода °

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

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

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

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

Устройство для коммутации сообщений в сетях передачи данных // 1522232

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

Устройство для анализа параметров графа // 1522229

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

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

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

Устройство для раскраски графов // 1513470

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

Устройство для моделирования сетей в реальном времени // 1509926

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

Устройство для моделирования задач о длиннейшем пути в сетях // 1509925

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

Устройство для анализа параметров графа // 1509923

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

Матричное вычислительное устройство // 1509920

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

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

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

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

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

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

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

Устройство для исследования сетей петри // 2126171

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

Способ работы узла интерфейса пользователя в соответствии с распределенной многовыходовой системой поискового вызова, способ работы распределенной многовыходовой системы поискового вызова // 2157596

Изобретение относится к системам поискового вызова

Устройство для выбора рациональных решений // 2158955

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

Матричный коммутатор "prosto" // 2160925

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

Модуль коммуникационной сети // 2166793

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

Модуль матричного коммутатора // 2168204

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

Устройство для распознавания ситуаций // 2168207

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

Устройство для распознавания ситуаций // 2168764