Устройство для исследования параметров графа
СОЮЗ СОВЕТСКИХ
СОЦИАЛИСТИЧЕСНИХ
РЕСПУБЛИК (50 4 С 06 F 15/20
ГОСУДАРСТВЕННЫЙ НОМИТЕТ СССР (21) 4158578/24-24 (22) 10. 12.86 (46) 07.07.88, Бюл. Р 25 (72) Ю.И.Глотов и Б.N.Ãoðäååâ (53) 681.333 (088.8) (56) Авторское свидетельство СССР
У 491132, кл. С 06 F 15/20, 1975.
Авторское свидетельство СССР
У 525954, кл. С 06 F 15/20, 1974.
„„SU„„1408441 А 1 (54) УСТРОЙСТВО ДЛЯ ИССЛЕДОВАНИЯ
ПАРАМЕТРОВ ГРАФА (57) Изобретение относится к вычислительной технике и может быть использовано для определения величины кратчайшего пути в графах. Целью изобретения является расширение функциональных возможностей устройства за счет определения величины
1408441
25 ратчайшего пути из К-й вершины rpaа в М-ю вершину с учетом ограничейий на одновременность начала исполйения ветвей графа (K=1,...,P, М =
1,...,P, где Р— количество вершин
В графе). Устройство содержит матрицу из Р Р счетчиков 1, матрицу из Р элементов И 2, матрицу из РяР триггеров 3, группу из P элементов
ЙЛИ 4, группу из P триггеров 5, групиз P элементов И 6, вторую групу из Р триггеров 7, группу из P четчиков 8 и третью группу из P риггеров 9. После подачи тактовых пульсов на вход устройства все четчики 1, на вход разрешения счета оторых подан высокий потенциал с
ыхода соответствующего элемента И 2 на счетный вход которых поступают актовые импульсы с выхода соответствующего элемента И 6, начинают счет импульсов (исполнение ветвей, 1
Изобретение относится к вычислительной технике и может быть исполь; зовано для определения величины кратчайшего пути в графах.
Цель изобретения " расширение функциональных возможностей устрой ства эа счет определения величины ! кратчайшего пути из К-й вершины гра, фа в M-ю вершину с учетом ограничений на одновременность начала исполнения ветвей графа (К1,...,P, M=1,...,P, где Р— количество вершин в граФе).
На чертеже представлена функциональная схема устройства.
Устройство содержит матрицу из РхР счетчиков 1, матрицу из РяР элементов И 2, матрицу из РхР триггеров 3, группу из Р элементов ИЛИ 4, первую группу из Р триггеров 5, группу из Р элементов И 6, вторую группу из Р триггеров 7, группу из Р счетчиков 8 и третью группу из Р триггеров 9.
Устройство работает следующим образом.
Перед началом работы, установкой соответствующих триггеров Э в " 1" задается топология моделируемого графа, триггеры 5 обнуляются, в счетисходящих из достигнутых (или начальной) вершин графа, если для них (ветвей) отсутствует ограничение на начало исполнения). По достижении полной емкости одним из счетчиков 1 сигнал с его выхода переполнения устанавливает соответствуняций триггер
5 B единичное состояние (цостигнута очередная Вершина), единичный потенциал с выхода которого разрешает прохождение тактовых импульсов через один из элементов И 6, создавая условия для запуска вершин, исходящих из соответствующей вершины графа. Работа устройства продолжаетс" до тех пор, пока в единичное состояние не будет установлен триггер 5, соответствующий конечной вершине графа, при этом количество поданных на вход устройства тактовых импульсов соответствует весу пути из начальной в конечную вершину графа. 1 ил.
2 чики 1 заносятся коды, дополняющие веса ветвей из К-й вершины графа в
М-ю вершину до полной емкости счетчика. Установкой в "1" соответствующих триггеров 7 задаются вершины, для всех входящих в которые ветвей задано ограничение на начало
I исполнения ветви, в счетчики 8 заносятся коды, дополняющие вес ограничения до полной емкости счетчиков, установкой в "1" соответствующего триггера 5 задают вершину начала пути, установкой "1" триггеров 9 задают вершины, на начало исполнения всех входящих в которые ветвей отсутствует ограничение.
После подачи тактовых импульсов на,.вход устройства все счетчики 1, на вход разрешения счета которых подан высокий потенцИал с выхода соответ-. ствующего элемента И 2 и на счетный вход которых поступают тактовые импульсы с выхода соответствующего элемента И 6, начинают счет импульсов— исполнение ветвей, исходящих из достигнутых (или начальной) вершин гра-, фа, если для них (ветвей) отсутствует ограничение на начало исполнения).
14084
Формула изобретения
Составитель А.Мишин
Техред А.Кравчук
Редактор В.Данко
КоРРектоР Г,Решетник
Заказ 3353/52
Тираж 704 Подписное
ВНИИПИ Государственного комитета СССР по делам изобретений и открытий
113035, Москва, Ж-35, Уаушская наб., д. 4/5 ъ
Производственно;полиграфическое предприятие, г. Ужгород, ул. Проектная, 4
Одновременно, тактовые импульсы поступают на счетные входы счетчиков 8,,которые при наличии высокого потенциала с выхода триггера 7 начинают счет импульсов (определение момента снятия ограничения на запуск ветвей, входящих в К-ю вершину графа). Переполнение соответствующего счетчика 8 устанавливает соответствующий триг- . 10
rep 9 в "1" (снимает ограничение на запуск ветвей). По достижении полной емкости одним из счетчиков 1 сигнал с его выхода переполнения устанавливает соответствующий триггер 5 в 15 единичное состояние (достигнута очередная вершина), высокий потенциал с выхода которого разрешает прохождение тактовых импульсов через один иэ элементов И 6, создавая условия 20 для запуска вершин, исходящих из соответствующей вершины гра*а. Работа устройства продолжается до тех пор, пока в единичное состояние не будет установлен триггер 5, соответствующий конечной вершине графа, при этом количество поданных на входе устройства тактовых импульсов соответствует весу пути из начальной в конечную вершину графа. 30
В том случае, если выходы И-го триггера 9 подключить к вторым входам всех элементов И 2 М-й строки матрицы, можно ограничить начало исполнения ветвей, исходящих из М-й вершины графа. При подключении выхода К-ro триггера .9 к входу М-ro триггера 7 можно задавать более сложные условия ограничения, что выгодно отличает предложенное уст- 40 ройство от известного.
Устройство для исследования па- 45 раметров графа, содержащее матрицу
41
4 из РхР счетчиков (где P — количество вершин в графе), матрицу из P" P элементов И, матрицу нз РхР триггеров, группу из P элементов ИЛИ, первую группу из P триггеров и группу из P элементов И, причем выход
К-го элемента И группы (К=1,...,Р) подключен к счетным входам всех счетчиков К-й строки матрицы, выход М-го триггера (М=1,...,P) К-й строки матрицы подключен к первому входу М-ro элемента И К-й строки матрицы, выход которого подключен к вхору разрешения счета М-го счет-. чика К-й строки матрицы, выход признака переполнения которого подключен к К-му входу И-ro элемента ИЛИ группы, выход которого подключен к входу установки в "1" М-го триггера первой группы, выход которого является выходом признака достижения М-й вершины устройства и подключен к первому входу М-ro элемента И группы,. вторые входы всех элементов И группы подключены к тактовому входу устройства, отличающее с я тем, что, с целью расширения функциональных возможностей устройства эа.счет определения величины кратчайшего пути иэ К-й вершины графа в М-ю вершину графа с учетом ограничений на одновременность начала исполнения ветвей графа, в него введены группа иэ P счетчиков, вторая группа из P-триггеров и третья группа из P-триггеров, причем выход М-ro триггера второй группы подключен к входу разрешения счета И-го счетчика группы, выход признака переполнения которого подключен к входу установки в "1" М-го триггера третьей группы, выход которого подключен к вторым входам всех элементов И М-ro столбца матрицы, тактовый вход устройства подключен к счетным входам всех счетчиков группы.
