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

С

00

ы о

СА VI

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

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

На чертеже представлена функциональная схема устройства.

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

8задания режима работы устройства, входы

9задания начальной вершины пути устройства, входы 10 задания конечной вершины пути устройства, выходы 11 и 12 блока 2 синхронизации, выход 13 веса экстремального пути в графе устройства, выходы 14 признаков принадлежности дуг (ребер) экстремальному пути в графе устройства и выход 15 признака окончания работы.

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

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

На вход 7 пуска подают импульс уровня логической 1. При этом блок 2 синхронизации формирует последовательность импульсов, предусмотренную временной диаграммой его работы. Блок 2 формирует импульс уровня логической 1м на своем выходе 11, При этом блок 3 формирует потенциалы уровня логической Г на тех своих выходах,номера которых соответствуют номерам дуг (ребер), входящим в состав маршрута из начальной в конечную вершину графа. При этом опрошенные каналы блока 4 памяти выдают на свои выходы занесенные в них значения (т.е. значения весов дуг, входящих в состав текущего пути). Через время, достаточное для выполнения указанных операций, блок 2 синхронизации формирует импульс уровня логической Г на выходе 12. При этом блок Б суммирует все значения, поступившие на его входы слагаемых, сравнивает полученную сумму со значением, полученным в предыдущем такте

работы и при выполнении условия экстремума (больше или меньше) фиксирует текущее значение суммы и формирует импульс уровня логической 1 на выходе соответствующего признака. При этом блок 6 регистрации фиксирует поступившую на его вход информацию (состав дуг (ребер) пути, принятого в данном такте за экстремальный). Через время, достаточное для выпол0 нения указанных операций, блок 2 синхронизации формирует импульс уровня логической 1 на своем выходе 11, после чего работа устройства повторяется. После того как блок 3 закончит перечисление всех

5 возможных маршрутов, потенциалом уровня логической 1 с его соответствующего выхода блок 2 синхронизации останавливается. При этом на выходах 14 будет сформирован состав дуг, входящих в экстре0 мальный путь в графе, а на выходе 13 - вес этого пути.

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

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

0 его функциональных возможностей за счет определения экстремального пути в графе со взвешенными дугами, в него введены блок перечисления маршрутов и многоканальный блок памяти, причем выход значе5 ния (К.М)-го элемента блока задания

матрицы смежности (К 1,.,,, В; М 1В,

где В - количество вершин в графе) подключен к входу признака наличия (К,М}-й дуги блока перечисления маршрутов, выход при0 знака окончания списка маршрутов которого является выходом признака окончания работы устройства и подключен к входу останова блока синхронизации, первый выход которого подключен к тактовому входу

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

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

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

торого подключен к одноименному входуМ-й вход задания конечной вершины пути

блока перечисления маршрутов, второй вы-которого подключен к одноименному входу

ход блока синхронизации подключен к так-блока перечисления маршрутов, вход режитовому входу накапливающего блока5 ма работы устройства подключен к входу

выбора экстремальной суммы, информаци-выбора вида экстремума накапливающего

онный выход которого является выходом ве-блока выбора экстремальной суммы.

Изобретение относится к вычислительной технике и может быть использовано для исследования путей в графах. Целью изобретения является расширение функциональных возможностей устройства за счет определения экстремального пути, в графе со взвешенными дугами. Устройство содержит блок 1 задания матрицы смежности, блок 2 синхронизации, блокЗ перечисления маршрутов, многоканальный блок 4 памяти, накапливающий блок 5 выбора экстремальной суммы, блок 6 регистрации, вход 7 пуска устройства, вход 8 задания режима работы, устройства, входы 9 задания начальной вершины пути устройства, входы 10 задания конечной вершины пути устройства, выходы 11 и 12 блока 2 синхронизации, выход 13 веса экстремального пути в графе устройства, выходы 14 признаков принадлежности дуг (ребер) экстремальному пути в графе устройства и выход 15 признака окончания работы. После завершения начальных установок в устройстве на его вход 7 пуска подают импульс уровня логической Г. При этом блок 2 синхронизации формирует последовательность импульсов, предусмотренную временной диаграммой его работы, под управлением которой на выходах 14 устройства будет сформирован состав дуг, входящих в экстремальный путь в графе, а на выходе 13 - вес этого пути. 1 ил. « Ј