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

)5 6 06 Г 15/419 ОПИСАНИЕ ИЗОБРЕТЕН ВУ ВТОРСКОМУ СВИДЕТЕ и/ ГОСУДАРСТВЕННЫЙ КОМИТЕТПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМПРИ ГКНТ СССР(56) Авторское свидетельство СССР М 1501095, кл. 6 06 Р 15/20, 1988.Авторское свидетельство СССР ЬЬ 1596344, кл, 6 06.Р 15/20, 1988.(54) УСТРОЙСТВО ДЛЯ РЕШЕНИЯ ЗАДАЧ НА ГРАФАХ(57) Изобретение относится к вычислительной технике и может быть использовано для исследования путей в графах. Целью изобретения является расширение функциональных возможностей устройства за счет определения экстремального пути, в графе со взвешенными дугами, Устройство содержит блок 1 задания матрицы смежности, блок 2 синхронизации, блок 3 перечисления маршрутов, многоканальный блок 4 памяти,2накапливающий блок 5 выбора экстремальной суммы, блок 6 регистрации, вход 7 пуска устройства, вход 8 задания режима работы. устройства, входы 9 задания начальной вершины пути устройства, входы 10 задания конечной вершины пути устройства, выходы 11 и 12 блока 2 синхронизации, выход 13 веса экстремального пути в графе устройства, выходы 14 признаков принадлежности дуг (ребер) экстремальному пути в графе устройства и выход 15 признака окончания работы, После завершения начальных установок в устройстве на его вход 7 пуска подают импульс уровня логической "1". При этом блок 2 синхронизации формирует последовательность импульсов, предусмотренную временной диаграммой его работы, Я под управлением которой на выходах 14 устройства будет сформирован состав дуг, входящих в экстремальный путь в графе, а на выходе 13 - вес этого пути, 1Изобретение относится к вычислительной технике и может быть использовано дляисследования путей в графе.Целью изобретения является расширение функциональных возможностей устрой. 5ства за счет определения экстремальногопути в графе со взвешенными дугами,На чертеже представлена функциональная схема устройства,Устройство содержит блок 1.задания 10матрицы смежности, блок 2 синхронизации,блок 3 перечисления маршрутов, многоканальный блок 4 памяти, накапливающийблок 5 выбора экстремальной суммы, блок 6регистрации, вход 7 пуска устройства, вход 158 задания режима работы устройства, входы9 задания начальной вершины пути устройства, входы 10 задания конечной вершиныпути устройства, выходы 11 и 12 блока 2синхронизации, выход 13 веса экстремального пути в графе устройства, выходы 14признаков принадлежности дуг (ребер) экстремальному пути в графе устройства и выход 15 признака окончания работы,Устройство работает следующим абраЗОМ,Перед началом работы в блок 1 заносятинформацию о топологии графа, обнуляютнакапливающий блок 5, устанавливают блок3 перечисления маршрутов в исходное состояние, по входам 9 и 10 задают номераначАльной и конечной вершин пути, по входу 8 задают режим работы устройства )определение кратчайшего (вид экстремума -минимум) или длиннейшего(вид экстремума - максимум) пути), в каналы блока 4памяти заносят значения весов соответствующих дуг.На вход 7 пуска подают импульс уровнялогической "1", При этом блок 2 синхронизации формирует последовательность импульсов, предусмотренную временнойдиаграммой его работы. Блок 2 формируетимпульс уровня логической ".1" на своем выходе 11, При этом блок 3 формирует потенциалы уровня логической "1" на тех своихвыходах, номера которых соответствуют номерам дуг (ребер), входящим в состав маршрута из начальной в конечную вершинуграфа, При этом опрошенные каналы блока 504 памяти выдают на свои выходы занесенные в них значения (т.е, значения весов дуг,входящих в состав текущего пути). Черезвремя, достаточное для выполнения указанных операций, блок 2 синхронизации формирует импульс уровня логической "1" навыходе 12. При этом блок 5 суммирует всезначения, поступившие на его входы слагаемых, сравнивает полученную сумму со значением, полученным в предыдущеМ такте работы и при выполнении условия экстремума (больше или меньше) фиксирует текущее значение суммы и формирует импульс уровня логической "1" на выходе соответствующего признака. При этом блок 6 регистрации фиксирует поступившую на его вход информацию (состав дуг (ребер) пути, принятого в данном такте за экстремаль- ный). Через время, достаточное для выполнения указанных операций, блок 2 синхронизации формирует импульс уровня логической "1" на своем выходе 11, после чего работа устройства повторяется. После того как блок 3 закончит перечисление всех возможных маршрутов, потенциалом уровня логической "1" с его соответствующего выхода блок 2 синхронизации останавливается, При этом на выходах 14 будет сформирован состав дуг, входящих в экстремальный путь в графе, а на выходе 13 - вес ЭТОГО пУти.Формула изобретения Устройство для решения задач на графах, содержащее блок задания матрицы смежности, блок регистрации, накапливающий блок выбора экстремальной суммы и блок синхронизации, вход пуска которого является входом пуска устройства, о т л ич а ю щ е е с я тем, что, с целью расширения его функциональных возможностей за счет определения экстремального пути в графе со взвешенными дугами, в него введены блок перечисления маршрутов и многоканальный блок памяти, причем выход значения (К,М)-го элемента блока задания матрицы смежности(К = 1, ., В; М =1, , В, где В - количество вершин в графе) подключен к входу признака наличия (К,М)-й дуги блока перечисления маршрутов, выход признака окончания списка маршрутов которого является выходом признака окончания работы устройства и подключен к входу останова блока синхронизации, первый выход которого подключен к тактовому входу блока перечисления маршрутов выход признака принадлежности (К,М)-й дуги множеству дуг текущего маршрута которого подключен в (К,М)-му разряду информационного входа блока регистрации и к входу опроса (К,М=го канала многоканального блока памяти, информационный выход (К,М)-го канала которого подключен к входу (К,М)-го слагаемого накапливающего блока выбора экстремальной суммы, выход признака наличия экстремума которого подключен к входу признака записи блока регистрации, (К,М)-й разряд информационного выхода которого является выходом признака принадлежности(К,М)-ой дуги экстремальному пути в графе устройства. К-йЗаказ 3415 ТиражПодписное ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР 113035, Москва, Ж. Раушская наб., 4/5 Производственно-издательский комбинат "Патент", г. Ужгород, ул. Гагарина, 101 вход задания начальной вершины пути которого подключен к одноименному входу блока перечисления маршрутов, второй выход блока синхронизации подключен к тактовому входу накапливающего блока выбора экстремальной суммы, информационный выход которого является выходом веса экстремального пути в графе устройства, М-й вход задания конечной вершины пути которого подключен к одноименному входу блока перечисления маршрутов, вход режи ма работы устройства подключен к входувыбора вида экстремума накапливающего блока выбора экстремальной суммы,