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

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

Иллюстрации

Показать все

Реферат

 

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

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

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

РЕСПУБЛИН

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

H SXOrCsew иД т л *С у

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

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

ПРИ ГКНТ СССР (2)) 4624139/24-24 (22) 06.10,88 (46) 07,11.90, Бюл. ¹ 41 (72) А.С.Ханжиев и С.В.Авдеев (53) 68).333 (088.8) (56) Авторское свидетельство СССР № 2)1164, кл. G 06 Р )5/20, 1966, Авторское свидетельство СССР № 1038951, кл, G 06 Р 7/122, 1982, (54) УСТРОЙСТВО ДЛЯ РЕНЕНИЯ ЗАДАЧ НА

ГРАФАХ (57) Изобретение относится к вычислительной технике и может быть использовано для исследования путей в графе, Целью изобретения является повышение быстродействия устройства при определении веса критического пути в графе. Устройство содержит блок 1 за„.,Я0„„1605258 А 1 щ)5 G 06 F 15/419

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

1605258

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

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

Устройство работает следующим об- 20 разом, \

Пусть необходимо определить вес критичес ко ro (длиннейше го или кр ат чайшего) пути в графе, Перед началом работы в блок 1 задания матрицы весов 25 дуг заносят информацию о весе дуги, соединяющей К-ю и М-ю вершину графа (К1...,, В; M=! В, где В - количество вершин в графе), в блок 2 saдания матрицы смежности - информацию 30 о топологии графа, задают начальную и конечную вершины пути (в блоке 3).

На вход 6 пуска устройства подают сигнал уровня логической единицы, При этом блок 3 выдает на выходы 7 состав дуг критического (кратчайшего или длиннейшего) пути, а многоканальный коммутатор 4 выдает на выходы каналов, открытых потенциалами уровня логической единицы с выходов 7, зна- 40 чения, поступившие на входы этих каналов (т.е, веса дуг, входящих в состав критического пути), При этом сум" матор 5 выдает на выход 8 вес критического пути в графе, 45

Если исследуется граф (сеть) со взвешенными вершинами или со взвешенными вершинами и дугами (ребрами), на

1 информационные входы мно гок акал ьно го коммутатора 4 необходимо выдать значения весов вершин и/или ребер, а на управляющие входы коммутатора 4значения признаков принадлежности вершин и/или ребер (дуг) составу критиче ско го пути, Формула изобретения

Устройство для решения задач на графах, содержащее блок задания матрицы весов дуг, блок задания матрицы смежности и блок определения критического пути, вход пуска которого является входом опроса устройства, причем выход значения (К,М)=го элемента блока задания матрицы весов дуг (К=l, В; М=l...,, В, где В - количество вершин в графе) подключен к входу задания веса (К,M)-й дуги блока определения критического пути, выход значения (К,М)-ro элемента блока задания матрицы смежности подключен к входу признака наличия (К,М)-й дуги блока определения критического пути, отличающее ся тем, что, с целью повышения быстродействия устройства при определении веса критического пути в графе, в него введены многоканальный коммутатор и сумматор, прияем выход значения (К,M)-ro элемента блока задания матрицы весов дуг подключен к (К,M)-му информацион- . ному входу многоканального коммутатора, выход признака принадлежности (К,М)-й дуги множеству дуг критического пути в графе блока определения критического пути является одноименным выходом устройства и подключен к управлякидему входу (К,М)-ro канала многоканального коммутатора, информационный выход которого подключен к входу (К, М)-ro слагаемого сумматора, выход которого является выходом веса критического пути в графе устроиства

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

Техред H.Äèäûê Корректор M.Максимишинец

Редактор Н,Тупица

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

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

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

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