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

(19) 06 Р 15/ 51) ОПИСАНИЕ ИЗОБРЕТЕНИ свисс я С ,. с . сссс Е. . . с.ДЕТЕЛЬ А ВТОРСКОМ ГОСУДАРСТВЕННЫЙ КОМИТЕТРО ИЗОБРЕТЕНИЯМ И ОТТНРЫТИЯПРИ ГКНТ СССР(56) Авторское свидетельство СССР Р 211164, кл. С 06 Р 15/20, 1966,Авторское свидетельство СССР В 1038951, кл, С 06 Р 7/122, 1982, (54) УСТРОЙСТВО ДЛЯ РЕНЕНИЯ ЗАДАЧ НА ГРАФАХ(57) Изобретение относится к вычислительной технике и может быть использовано для исследования путей в граФе, Целью изобретения является повышение быстродействия устройства при определении веса критического пути в графе, Устройство содержит блок 1 зардния матрицы весов дуг, блок 2 эадаиия матрицы смежности, блок 3 определения критического пути, многоканальный коммутатор 4, сумматор 5, вход 6опроса устройства, выходы 7 признаковпринадлежности дуг множеству дуг критического пути в графе устройства ивыход 8 веса критического пути устройства. Перед началом работы в блок 1задания матрицы весов дуг заносят инФормацию о весе дуг графа, в блок 2задания матрицы смежности - информацию о топологии графа, в блоке 3 задают начальную и конечную веригиныграфа. На вход пуска устройства подают сигнал уровня логической "1", Приэтом сумматор 5 выдает на выход 8 вескритического пути в графе. 1 ил, 11605258 информ ацио нные входы мно го к ан аль но го коммутатора 4 необходимо выдать значения весов вершин и/или ребер, а на управляющие входы коммутатора 4- значения признаков принадлежности вершин и/или ребер (дуг) составу критиче ско го пути. Формула изобретения Составитель А,МишинТехред М,Дидык Корректор М.Максимишинец Редактор Н,Тупица Заказ 3455 Тираж 567 ПодписноеВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР113035, Москва, Ж, Раушская наб., д. 4/5 Производственно-издательский комбинат "Патент", г.Ужгород, ул. Гагарина, 101 Изобретение относится к вычислительной технике и может быть использовано для исследования путей в графе,Цель изобретения - повышение. бы-.стродействия устройства при определении веса критического пути в графе,На чертеже представлена функциональная схема устройства,Устройство содержит блок 1 задания 10матрицы весов дуг, блок 2 заданияматрицы смежности, блок 3 определениякритического пути, многоканальный коммутатор 4, сумматор 5, вход 6 опросаустройства, выходы 7 признаков принадлежности дуг множеству дуг критического пути в графе устройства ивыход 8 веса критического пути устройства.Устройство работает следующим образом,Пусть необходимо определить вескритического (длиннейшего или кратчайшего) пути в графе, Перед началомработы в блок 1 задания матрицы весов 25дуг заносят информацию о весе дуги,соединяющей К-ю и М-ю вершину графа(К 1 В; М 1 В, где В - количество вершин в графе), в блок 2 задания матрицы смежности - инФормацию 30о топологии графа, задают начальнуюи конечную вершины пути (в блоке 3).На вход 6 пуска устройства подаютсигнал уровня логической единицы,При этом блок 3 выдает на выходы 7 35состав дуг критического (кратчайшегоили длиннейшего) пути, а многоканальный коммутатор 4 выдает на выходы каналов, открытых потенциалами уровнялогической единицы с выходов 7, значения, поступившие на входы этих каналов (т.е, веса дуг, входящих в состав критического пути), При этом сум"матор 5 выдает на выход 8 вес критического пути в графе, 45Если исследуется граф (сеть) совзвешенными вершинами или со взвешенными вершинами и дугами (ребрами), на1 Устройство для решения задач награфах, содержащее блок задания матрицы весов дуг, блок задания матрицысмежности и блок определения критического пути, вход пуска которого является входом опроса устройства, причем выход значения (К,М)=го элементаблока задания матрицы весов дуг (К=1,В; М=1 В, где В - количество вершин в графе) подключен к входу задания веса (К,М)-й дуги блокаопределения критического пути, выходзначения (К,М)-го элемента блока задания матрицы смежности подключен квходу признака наличия (К,М)-й дугиблока определения критического пути,отличающее ся тем, что, сцелью повышения быстродействия устройства при определении веса критического пути в графе, в него введены многоканальный коммутатор и сумматор, прияем выход значения (К,М)-гоэлемента блока задания матрицы весовдуг подключен к (К,М)-му информацион- .ному входу многоканального коммутатора, выход признака принадлежности(К,М)-й дуги множеству дуг критического пути в графе блока определениякритического пути является одноименным выходом устройства и подключен куправлякцему входу (К,М)-го каналамногоканального коммутатора, информационный выход которого подключен квходу (К, М)-го слагаемого сумматора, выход которого является выходом веса критического пути в графе устройства