Устройство для исследования путей в графе

(56) Авторск У 842842, клАвторское У 525954, кл етельство СССР 0 7/122, 1979, ельство СССР Р 15/20) 1974. свид 066 етФеуФее ОСУДАРСТВЕННЫЙ КОМИТЕТ СССР ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТ(54) УСТРОЙСТВО ДЛЯ ИССЛЕПУТЕЙ В ГРАФЕ(57) Изобретение относитлительной технике и можетпользовано для исследованграфе. Целью изобретениярасширение функциональныхтей устройства за счет опвершин кратчайшего пути вройство содержит матрицуяквыч быть ис я путей вляется возможн еделени графе. з РхР с,139975 чиков 1, где Р " количество вершин В графе, матрицу из РхР триггеров 2, Первую группу иэ Р элементов ИЛИ 3, группу из Р триггеров 4, элемент , И 5, группу из Р элементов НЕ 6, втофую группу из Р элементов ИЛИ 7 и группу из Р счетчиков 8. После подачи импульсов на тактовый вход устройСтва все счетчики первой строки матрицы начинают счет импульсов (испол" Мение ветвей, исходящих из первой Вершины графа). Переполнение К-го Счетчика первой строки матрицы (К = Ф 1Р) устанавливает К-й триггертой же строки матрицы в единичное Состояние (достигнута К-я вершина 1 рафа), Высокий потенциал с выхода К"го элемента ИЛИ 3 поступает на входы разрешения счета всех счетчиковК-й строки матрицы, которые начина 3ют счет тактовых импульсов (исполне"ние ветвей, исходящих из К-й вершиныграфа), и т,д, Единичный потенциалс выхода элемента И 5 (достигнутывсе вершины графа) поступает на входы признака чтения всех триггеров2 Р-го столбца матрицы. На синхронизируемом информационном выходе М-готриггера 2 (М=1Р), принадлежа"щего кратчайшему пути в графе, появляется высокий потенциал, который устанавливает в единицу М-й триггер4, высокий потенциал с выхода которо"го поступает на входы признака чтениятриггеров 4 М-го столбца матрицы,Устройство работает аналогично дотех пор, пока не будут установленыв "единицу" все триггеры 4, соответствующие кратчайшему пути в графе.1 ил.Изобретение относится к вычислительной технике и может быть использовано для определения вершин и ве" Личины кратчайшего пути в графе,Целью изобретения является расшиение функциональных возможностейстройства за счет определения вершинКратчайшего пути в графе.На чертеже представлена функцио. Нальная схема устройства.Устройство содержит матрицу из РхРсчетчиков 1, где Р - количество вершин в графе, матрицу из РхР триггеров 2, первую группу из Р элементовИЛИ 3, группу иэ Р триггеров 4, элемент И 5,группу из Р элементов НЕ б,Вторую группу из Р элементов ИЛИ 7и группу из Р счетчиков 8,Устройство работает следующим образом.Перед началом работы в счетчики 1 Заносят коды, дополняющие веса соотВетствующих ветвей графа до полной емкости счетчика (в том случае, если Ветвь отсутствует, соответствующий ей счетчик обнуляют), все триггеры 2 и 4 и счетчики 8 обнуляют, на вход 10 15 20 25 пуска устройства подают единичный потенциал.После подачи тактовых импульсов на тактовый вход устройства все счетчики первой строки матрицы начинают счет импульсов (исполнение ветвей, исходящих из первой вершин графа), Переполнение К-го счетчика первой строки матрицы (К=1Р) устанавливает К-й триггер, 2 той же строкиматрицы в единичное состояние (достигнута К"я вершина графа) при условии, что с выхода элемента НЕ б навход разрешения записи указанноготриггера подается единичный потенциал.После установки К-го триггера любойстроки матрицы в "единицу" единичныйпотенциал с его несинхронизируемогоинформационного выхода, проходя черезэлемент НЕ Ь, запрещает установку вединичное состояние любого из оставшихся триггеров 2 К-го столбца матрицы и счет импульсов К-м счетчиком 8Единичный потенциал с выхода К-гоэлемента ИЛИ 3 поступает на входы раз"решения счета всех счетчиков 1 К-йстроки матрицы, которые начинают счеттактовых импульсов (исполнение ветвей, исходящих из К-й вершины графа),97534счетчиков, где Р " количество вершинв графе, матрицу из РхР триггеров,первую группу из Р элементов ИЛИ,группу из Р триггеров и элемент И, 5о т л и ч а ю щ е е с. я тем,что, сцелью расширения функциональных возможностей устройства эа счет определения вершин кратчайшего пути в гра О фе, в него введены группа из Р элементов НЕ, вторая группа из Р элементов ИЛИ и группа из Р счетчиков,причем выход признака переполнения К-госчетчика М-й строки матрицы (К.15 = 1 Р; М 1. Р) подключен кинформационному входу К-го триггераМ-й строки матрицы, несинхронизируемый информационный выход которого -подключен к М-му входу К"го элемента 20 ИЛИ первой группы, выход которогоподключен к входам разрешения счетавсех счетчиков (К+1)-й строки матрицы (КР), к К-му входу элемента И ивходу К-го элемента НЕ группы, выход 25 которого подключен к входу разрешения счета К-го счетчика группы и вхо"дам разрешения, записи всех .триггеровК-го столбца матрицы, синхронизируе-,мый информационный выход К го тригге- ЗО ра М-й строки матрицы подключен кК-му входу М-го элемента ИЛИ второйгруппы, выход которого подключен квходу установки в М-го триггера группы, выход которого подключен к вхо"дам признака чтения всех триггеровМ-го столбца матрицы (МР), выходэлемента И подключен к входам призна"ка чтения всех триггеров Р-го столбца матрицы, вход пуска устройства 40 подключен к входам разрешения записивсех счетчиков первой строки матрицы,тактовый вход устройства подключен к счетньм входам всехсчетчиков матрицы и счетньм вхо дам всех счетчиков груп.пы. 3 139 Устройство аналогично работает до тех пор, пока на выходе элемента И 5 не появится единичный потенциал (достигнуты все вершины графа). Единичный потенциал с выхода элемента И 5 поступает на входы признака чтения всех триггеров 2 Р-го столбца матрицы. На синхронизируемом информационном выходе М-го триггера 2 (М=1Р) (принадлежащего кратчайшему пути.в граФе) появляется единичный потенциал, который устанавливает в единицу М-й триггер 4, единичный потенциал с выхода которого поступает на входы признака чтения триггеров 4 М"го столбца матрицы. Устройство аналогично работает до тех пор, пока небудут установлены в единицу все триггеры 4, соответствующие кратчайшему пути в графе.В результате работы устройства оп" ределяются величина кратчайшего пути из первой вершины в К-ю (количество импульсов, поступивших на такто" вый вход устройства до момента появ" ления единичного потенциала на выходе К-го элемента ИЛИ 3, что соответствует коду, записанному в К"м счетчике 8) и вершины, принадлежащие кратчайшему пути (состав установленных в единицу триггеров 4).В качестве триггера 2 может быть использована совокупность Э-триггера и элемента И, причем информационный ,выход Р-триггера является несинхронизируемым информационным выходом триггера 2 и подключен к первому вхо" ду элемента И, второй вход которого является входом признака чтения триггера 2, причем выход элемента И является синхронизируемым информационным выходом триггера 2.Формула изобретенияУстройство для исследования путей в графе, содержащее матрицу из РхР Составитель А.Мишин Редактор А,Лежнина Техред А.Кравчук Корректор Г.РешетникЗаказ 2667/49 Тираж 704 ПодписноеВНИИПИ Государственного комитета СССРпо делам изобретений.и открытий113035, Москва, Ж, Раушская наб д, 4/5 Производственно-полиграфическое предприятие, г. Ужгород, ул. Проектная, 4