Устройство для исследования параметров графа Советский патент 1988 года по МПК G06F15/173 

(21)4158578/24-24

(22)10.12.86

(46) 07.07.88. Бюл. № 25

(72) Ю.И.Глотов и Б.М.Гордеев

(53) 681.333 (088.8)

(56) Авторское свидетельство СССР

491132, кл. G 06 F 15/20, 1975.

Авторское свидетельство СССР № 525954, кл. G 06 F 15/20, 1974.

(54) УСТРОЙСТВО ДНЯ ИССЛЕДОВАНИЯ ПАРАМЕТРОВ ГРАФА

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

(Л

00 4 4

кратчайшего пути из К-й вершины гра- 4а в М-ю вершину с учетом ограниче- йий на одновременность начала исполнения ветврй графа (,...,Р, М 1,..4,Р, где Р - количество вершин 8 графе). Устройство содержит матри- Йу из Р счетчиков 1, матрицу из Р элементов И 2, матрицу из Р tpиггepoв 3, группу из Р элементов 11ПИ 4, группу из Р триггеров 5, группу из Р элементов И 6, вторую группу иэ Р триггеров 7, группу из Р счетчиков 8 и третью группу из Р триггеров 9а После подачи тактовых импульсов на вход устройства все :четчики 1, на вход разрешения счета соторых подан высокий потенциал с ;зыхода соответствукяцего элемента И 2 и на счетный вход которых поступают тактовые импульсы с выхода соответствующего элемента И 6, начинают счет импульсов (исполнение ветвей.

: 1

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

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

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

Устройство содержит матрицу из счетчиков 1, матрицу из Рк элементов И 2, матрицу из Рхр триггеров 3, группу из Р элементов ИЛИ 4, первую группу из Р триггеров 5, группу из Р элементов И 6, вторую группу из Р триггеров 7 f группу из Р счетчиков 8 и третью группу из Р триггеров 9,

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

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

чики 1 заносятся коды, дополняющие веса ветвей из К-й вершины графа в М-ю вершину до полной емкости счетчика. Установкой в 1 соответ- 5 ствующих триггеров 7 задаются вершины, для всех входящих в которые ветвей задано ограничение на начало исполнения ветви, в счетчики 8 заносятся коды, дополняющие вес огра0 ничения до полной емкости счетчиков, установкой в l соответствующего триггера 5 задают вершину начала пути, установкой 1 триггеров 9 задают вершины, на начало исполнения всех

входящих в которые ветвей отсутствует ограничение.

После подачи тактовых импульсов на .Ьход устройства все счетчики 1, на вход разрешения счета которых подан

0 высокий потенциал с выхода соответ-- ствующего элемента И 2 и на счетный вход которых поступают тактовые импульсы с выхода соответствующего элемента И 6, начинают счет импульсов 5

исполнение ветвей, исходящих из дос- тигнутЬЕх (или начальной) вершин гра- , фа, если дам них (ветвей) отсутствует ограничение на начало исполнениях

Одновременно, тактовые импульсы поступают на счетные входы счетчиков 8 .которые при наличии высокого потенциала с выхода триггера 7 начинают счет импульсов (определение момента сняГия ограничения на запуск ветвей входящих в К-ю вершину графа). Переполнение соответствующего счетчика 8 устанавливает соответствующий триггер 9 в 1 (снимает ограничение на запуск ветвей), По достижении полной емкости одним из счетчиков 1 сигнал с его выхода переполнения устанавливает соответствующий триггер 5 в единичное состояние (достигнута очередная вершина), высокий потенциал с выхода которого разрешает прохождение тактовых импульсов через один из элементов И 6, создавая условия для запуска вершин, исходящих из соответствующей верршны граАа. Работа устройства продолжается до тех пор, пока в единичное состояние не будет установлен триггер 5, соответствую-; щий конечной вершине трафа, при этом количество поданных на входе устройства тактовых импульсов соответствует весу пути из начальной в конечную вершину графа,

В том случае, если выходы М-го триггера 9 подключить к вторым входам всех элементов И 2 М-й строки матрицы, можно ограничить начало исполнения ветвей, исходящих из М-й вершины графа. При подключении выхода К-го тр иггера -9 к входу М-го триггера 7 можно задавать более сложные условия ограничения, что выгодно отличает предложенное устройство от известного.

Формула изобретения

Устройство для иccлe t oвaния параметров графа, содержащее матрицу

из Рхр счетчиков (где Р - количество вершин в графе), матрицу из Р Р элементов И, матрицу из Рхр тригге- ров, группу из Р элементов ИЛИ,

первую группу из Р триггеров и группу из Р элементов И, причем выход К-го элемента И группы (,..,,Р) подключен к счетным входам всех

счетчиков К-й строки матрицы, выход М-го триггера (,...,Р) К-й строки матрицы подключен к первому входу М-го элемента И К-й строки матрицы, выход которого подключен

к разрешения счета М-го счетчика К-й строки матрицы, выход признака переполнения которого подключен к К-му входу М-го элемента ИЛИ группы, выход которого подключен к

входу установки в 1 М-го триггера первой группы, выход которого является выходом признака достижения М-й вершины устройства и подключен к первому входу М-го элемента И группы,.

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

определения величины кратчайшего пути из К-й вершины графа в М-ю вершину графа с учетом ограничений на одновременность начала исполнения ветвей графа, в него введены группа из Р .

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

признака переполнения которого подключен к входу установки в 1 М-го триггера третьей группы, выход которого подключен к вторым входам всех элементов И М-го столбца матрицы,

тактовый вход устройства подключен к счетным входам всех счетчиков группы.