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

(У

О

о СП

N5 СП

00

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

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

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

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

Пусть необходимо определить вес критического (длиннейшего или кратчайшего) пути в графе. Перед началом работы в блок 1 задания матрицы весов дуг заносят информацию о весе дуги, соединяющей К-ю и М-ю вершину Графа (К,,,,, В; ,,.,, В, где В- количество вершин в графе), в блок 2 задания матрицы смежности - информацию о топологии графа, задают начальную и конечную вершины пути (в блоке 3), На вход 6 пуска устройства подают сигнал уровня логической единицы. При этом блок 3 выдает на выходы 7 состав дуг критического (кратчайшего или длиннейшего) пути, а многоканальный коммутатор 4 выдает на выходы каналов, открытых потенциалами уровня логической единицы с выходов 7, зна- чения, поступившие на входы этих каналов (т,е, веса дуг, входящих в состав критического пути). При этом сум матор 5 выдает на выход 8 вес критического пути в графе,

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

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

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

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

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