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

ОЮЗ СОВЕТСКИХ ЦИАЛИСТИЧЕСНИХ ПУБЛИК( ( л ение относится к вычисхнике и может быть исля определения величиго пути в гра 4 ах. Цельюявляется расширениеи возможностей устройопределения величины Ф УДАРСТВЕННЫЙ НОМИТЕТ СССР(56) Авторское свидетельство СССУ 491132, кл. С 06 Р 15/20, 1975Авторское свидетельство СССРУ 525954, кл. С 06 Р 15/20, 1974 54) УСТРОИСПАРАМЕТРОВ Г 57) Изобрет ительной тепользовано дны кратчайщеизобретенияфункциональнства за счет О ДЛЯ ИССЛЕДОВАНИЯФА1408441 5 10 15 20 25 ратчайшего пути из К-й вершины граа в М-ю вершину с учетом ограничейий на одновременность начала исполйения ветвей графа (К=1Р, М =1Р, где Р - количество вершинграФе). Устройство содержит матрицу из РхР счетчиков 1, матрицу из хР элементов И 2, матрицу из РхР триггеров 3, группу из Р элементов ЙЛИ 4, группу из Р триггеров 5, групиз Р элементов И 6, вторую групу из Р триггеров 7, группу из Р четчиков 8 и третью группу из Р риггеров 9. После подачи тактовыхпульсов на вход устройства все четчики 1, на вход разрешения счета оторых подан высокий потенциал с ыхода соответствующего элемента И 2на счетный вход которых поступаютактовые импульсы с выхода соответствующего элемента И 6, начинают счет импульсов (исполнение ветвей,1Изобретение относится к вычислительной технике и может быть исполь, зовано для определения величины кратчайшего пути в графах.ЦЕль изобретения - расширениефункциональных возможностей устройства эа счет определения величиныкратчайшего пути из К-й вершины гра, фа в М-ю вершину с учетом ограничений на одновременность начала исполнения ветвей графа (К 1Р, И=1Р, где Р - количество вершин в граФе).На чертеже представлена функциональная схема устройства.Устройство содержит матрицу из РХР счетчиков 1, матрицу из РхР элементов И 2, матрицу из РхР триггеров 3, группу из Р элементов ИЛИ 4, первую группу из Р триггеров 5, группу из Р элементов И 6, вторую группу из Р триггеров 7, группу из Р счетчиков 8 и третью группу из Р триггеров 9.Устройство работает следующим образом.Перед началом работы, установкой соответствующих триггеров Э в " 1" задается топология моделируемого графа, триггеры 5 обнуляются, в счетисходящих из достигнутых или начальной) вершин графа, если для них(ветвей) отсутствует ограничениена начало исполнения), По достиженииполной емкости одним из счетчиков 1сигнал с его выхода переполнения устанавливает соответствуняций триггер5 в единичное состояние (достигнутаочередная Вершина), единичный потенциал с выхода которого разрешаетпрохождение тактовых импульсов черезодин из элементов И 6, создавая условия для запуска вершин, исходящихиз соответствующей вершины графа. Работа устройства продолжаетс" до техпор, пока в единичное состояние небудет установлен триггер 5, соответствующий конечной вершине графа, приэтом количество поданных на входустройства тактовых импульсов соответствует весу пути из начальной вконечную вершину графа. 1 ил,2чики 1 заносятся коды, дополняющие веса ветвей из К-й вершины графа в М-ю вершину до полной емкости счетчика. Установкой в "1" соответствующих триггеров 7 задаются вершины, для всех входящих в которые ветвей задано ограничение на начало исполнения ветви, в счетчики 8 заносятся коды, дополняющие вес ограничения до полной емкости счетчиков, установкой в "1" соответствующего триггера 5 задают вершину начала пути, установкой "1" триггеров 9 задают вершины, на начало исполнения всех входящих в которые ветвей отсутствует ограничение.После подачи тактовых импульсов на,.Вход устройства все счетчики 1, на вход разрешения счета которых подан высокий потенцИал с выхода соответствующего элемента И 2 и на счетный вход которых поступают тактовые импульсы с выхода соответствующего элемента И 6, начинают счет импульсов - исполнение ветвей, исходящих из достигнутых (или начальной) вершин гра-, фа, если для них (ветвей) отсутствует ограничение на начало исполнения).14084 Формула изобретения Составитель А.МишинТехред А.Кравчук Редактор В.Данко Корректор Г.Решетник Заказ 3353/52 Тираж 704 Подписное ВНИИПИ Государственного комитета СССР по делам изобретений и открытий 113035, Москва, Ж-Э 5, Уаушская наб., д. 4/5зПроизводственно;полиграфическое предприятие, г. Ужгород, ул. Проектная, 4 Одновременно, тактовые импульсы поступают на счетные входы счетчиков 8, ,которые при наличии высокого потенциала с выхода триггера 7 начинают счет импульсов (определение момента снятия ограничения на запуск ветвей, входящих в К-ю вершину графа). Переполнение соответствующего счетчика 8 устанавливает соответствующий триг- . 10 гер 9 в "1" (снимает ограничение на запуск ветвей). По достижении полной емкости одним из счетчиков 1 сигнал с его выхода переполнения устанавливает соответствующий триггер 5 в 15 единичное состояние (достигнута очередная вершина), высокий потенциал с выхода которого разрешает прохождение тактовых импульсов через один иэ элементов И 6, создавая условия 20 для запуска вершин, исходящих из соответствующей вершины граа. Работа устройства продолжается до тех пор, пока в единичное состояние не будет установлен триггер 5, соответствующий конечной вершине графа, при этом количество поданных на входе устройства тактовых импульсов соответствует весу пути из начальной в конечную вершину графа. 30В том случае, если выходы М-го триггера 9 подключить к вторым входам всех элементов И 2 М-й строки матрицы, можно ограничить начало исполнения ветвей, исходящих из М-й вершины графа. При подключении выхода К-го триггера 9 к входу М-го триггера 7 можно задавать более сложные условия ограничения, что выгодно отличает предложенное уст ройство от известного. Устройство для исследования параметров графа, содержащее матрицу 414из РхР счетчиков (где Р - количество вершин в графе), матрицу иэ РфР элементов И, матрицу нз РхР триггеров, группу из Р элементов ИЛИ, первую группу из Р триггеров и группу из Р элементов И, причем выход К-го элемента И группы (К=1Р) подключен к счетным входам всех счетчиков К-й строки матрицы, выход М-го триггера (М=1 Р) К-й строки матрицы подключен к первому входу М-го элемента И К-й строки матрицы, выход которого подключен к вхоцу разрешения счета М-го счет-. чика К-й строки матрицы, выход при" знака переполнения которого подключен к К-му входу М-го элемента ИЛИ группы, выход которого подключен к входу установки в "1" М-го триггера первой группы, выход которого является выходом признака достижения М-й вершины устройства и подключен к первому входу М-го элемента И группы,. вторые входы всех элементов И группы подключены ктактовому входу устройства, о т л и ч а ю щ е е с я тем, что, с целью расширения функциональных возможностей устройства эа счет определения величины кратчайшего пути иэ К-й вершины графа в М-ю вершину графа с учетом ограничений на одновременность начала исполнения ветвей графа, в него введены группа иэ Р . счетчиков, вторая группа из Р-триггеров и третья группа из Р-триггеров, причем выход М-го триггера второй группы подключен к входу разрешения счета М-го счетчика группы, выход признака переполнения которого подключен к входу установки в н 1" М-го триггера третьей группы, выход которого подключен к вторым входам всех элементов И М-го столбца матрицы, тактовый вход устройства подключен к счетным входам всех счетчиков группы.