Устройство для решения задач на графах
Изобретение относится к вычислительной технике и может быть использовано для исследования путей в графе. Целью изобретения является повышение быстродействия устройства при определении веса критического пути в графе. Устройство содержит блок 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
