Устройство для определения параметров графа
Изобретение относится к вычислительной технике и может быть использовано для исследования путей в системах, описываемых графами. Целью изобретения является расширение функциональных возможностей устройства за счет определения ребер дерева кратчайших путей в графе. Устройство содержит блок 1 задания матрицы смежности, блок 2 удаления заходящих дуг, блок 3 определения кратчайшего пути, блок 4 регистрации и блок 5 определения конечных вершин дуг, кроме того, вход 6 начальной установки устройства, вход 7 пуска устройства и выходы 8 признаков принадлежности ребер дереву кратчайших путей. При подаче на вход 7 пуска устройства сигнала, имитирующего исполнение начальной вершины графа, блок 3 определения кратчайшего пути выдает в блок 4 регистрации сигналы, отмечающие исполнение дуг (ребер) графа в порядке окончания их моделирования. 4 ил.
СОЮЗ СО8ЕТСНИХ
СОЦИАЛИСТИЧЕСКИХ
РЕСПУБЛИК (51) 5 G 06 F 15/20
МИЬаЩ
ВБИЛИ;)-,j, y.,)))gg
ЕИБЛЩ:)-,,,;, ОПИСАНИЕ ИЗОБРЕТЕНИЯ
К А BTOPCHOMY СВИДЕТЕЛЬСТВУ
ГОСУДАРСТ8ЕННЫЙ НОМИТЕТ
ПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМ
ПРИ ГКНТ СССР (2i) 4392551/24-24 (22) 15.03.88 (46) 30.10.90. Бюл. М - 40 (72) M.М. Овчинников, 10.M. Коптев и В.А. Дементьев (53) 681.333(088.8) (56) Авторское свидетельство СССР
N - 223468, кл. G 06 G 7/122, 1967, Авторское свидетельство СССР
Р 1522229, кл. G 06 F 15/20, 1988. (54) УСТРОЙСТВО ДЛЯ ОПРЕДЕЛЕНИЯ Па-
РАМЕТРОВ ГРАФА (57) Изобретение относится к вычисли» тельной технике и может быть использовано для исследования путей в системах, описываемых графами. Целью изобретения является расширение функциональных возможностей устройства за
„„SU„1603396 А 1
2 счет определения ребер дерева кратчайших путей в графе. Устройство содержит блок 1 задания матрицы смежности, блок 2 удаления заходящих дуг, блок
3 определения кратчайшего пути, блок
4 регистрации и блок 5 определения конечных вершин дуг, кроме того, вход
6 начальной установки устройства, вход 7 пуска устройства и выходы 8 признаков принадлежности ребер дереву кратчайших путей. При подаче на вход
7 пуска устронства сигнала, имитиру- ющего исполнение начальной вершины графа, блок 3 определения кратчайшего пути выдает в блок 4 регистрации сигналы, отмечающие исполнение дуг (ре- а бер) графа в порядке окончания их моФ делирования. 4 ил.
3 1603396 4
Э
Изобретение относится к вычислительной технике и может быть использо вано для исследования путей в системах, описываемых графами.
Целью„изобретения является расширение функциональных воэможностей устройства за счет определения ребер дерева кратчайших путей в графе.
На фиг. 1 представлена функциональ-1р ная схема устройства; на фиг. 2функциональная схема блока определения конечных вершин дуг; на фиг. 3функциональная схема блока удаления заходящих дуг; на фиг. 4 - функциональная схема блока регистрации.
Устройство содержит блок 1 задания матрицы смежности, блок 2 удаления за" ходящих дуг, блок 3 определения крат» чайшего пути, блок 4 регистрации и 2р блок 5 определения конечных вершин дуг. Кроме того, на фиг. 1 обозначено: 6 — вход начальной установки устройства; 7 вход — пуска устройства и
8 — выход признаков принадлежности ре-25 бер дереву кратчайших пчтей.
Блок 5 определения конечных вершин дуг содержит матрицу из В х В элементов И 9, где  — количество вершин в графе, и группу из В элементов
ИЛИ 10, причем вход 11 признака наличия (К, M)-й дуги блока 5 определения конечных вершин дуг (К = 1,...,В;
N = 1,...,В) подключен к первому входу К-ro элемента И 9 М-й строки матрицы, выход которого подключен к
М-му входу К-го элемента ИЛИ 10 группы, выход которого является выходом
12 признака соответствия К-й вершины конечной вершине дуги блока 5 опре- 4О деления конечных вершин дуг, вход 13 опроса (К, М)-й дуги графа которого подключен к второму входу К-го элемен" та И 9 M-й строки матрицы.
Блок 2 удаления заходящих дуг содержит матрицу из В х В ключей 14, причем вход 15 признака наличия (К, М)-й дуги блока 2 удаления заходящих дуг подключен к информационному входу
К-ro ключа 14 M-й строки матрицы ин50 формационный выход которого является выходом 16 признака наличия (К, М)-й дуги блока удаления заходящих дуг, вход 17 задания К-й вершины которого подключен к управляющим (отключающим) входам всех ключей 14 К-ro столбца матрицы.
Блок 4 регистрации содержит матрицу из В х В триггеров 18, причем (К, М)-й информационный вход 19 блока 4 регистрации подключен к входу установки в "1" К-го триггера М-й строки матрицы, прямой выход которого является (К, M)-м информационным выходом
20 блока 4 регистрации, вход 21 установки в "0" которого подключен к входам установки в "0" всех триггеров 18 матрицы.
Устройство работает следующим образом.
Перед началом работы в блок 1 задания матрицы смежности заносят информацию о топологии графа, при этом ребра графа задают двумя противоположно направленными дугами, обнуляют блок
4 регистрации, в блок 3 определения кратчайшего пути заносят информацию о параметрах вершин и ребер (цепи установки параметров моделирования вершин и ребер не показаны). о
На вход 7 пуска устройства подают сигнал, имитирующий исполнение начальной вершины графа (это может быть сиг нал, изменяющийся по амплитуде, представленный серией импульсов уровня
"1", потенциал того же уровня и т.п., в зависимости от конструкции блока 3).
При этом блок 3 определения кратчайше,zo пути моделирует систему, заданную параметрами графа. При этом блок .4 ре«гистрирует дуги графа, моделирование которых закончено, а блоки 2 и 5 удаляют дуги, заходящие в вершину, конечную для дуги, окончившей моделирование.
По исполнении всех вершин графа, о чем может свидетельствовать сигнал с выхода (не показан) признака исполнения всех вершин графа блока 3, в блоке
4 регистрации содержится информация о ребрах (или дугах, если моделируют орграф) дерева кратчайших путей и направление, в котором пройдено ребро (К, M или М, К).
Блок 4 регистрации работает следующим образом.
При поступлении на вход 21 установки в "0" импульса уровня логической единицы все триггеры 18 устанавливаются в "0". При появлении сигналов уровня "1" на входах 19 соответствующие им триггеры 18 устанавливаются в 111lt
Формула изобретения
Устройство для определения парамет ров графа, содержащее блок задания
1 Яу
Й8 8
° е е
О е Ф
9 4 е
° е ° ее е
° ° ° ° е ° ° . °
° °
Э O Э
10 10 еее е ° е
Р В8
88
108
121 122
Раг. Я
5 11:0339 матрицы смежности, блок определения кратчайшего пути и блок регистрации, причем вход задания начальной вершины графа устройства подключен к одноименному входу блока определения крат5 чайшего пути, о т л и ч а ю щ е е с я тем, что, с целью расширения функциональных возможностей устройства за счет определения ребер дерева кратчайших путей в графе, в него введены блок определения конечных вершин дуг и блок удаления заходящих дуг, причем выход признака наличия (К, М)-й дуги блока задания матрицы смежности (К = 1,...,B; M = 1,... В, где Вколичество вершин в графе) подключен к одноименному входу блока удаления заходящих дуг и к одноименному входу блока определения конечных вершин 20 дуг, выход признака соответствия К-й
; вершины конечной вершине дуги которо6 6
ro подключен к входу задания К-й вершины блока удаления заходящих дуг, выход признака наличия (К, И)-й дуги которого подключен к одноименному входу блока определения кратчайшего пути, выход признака окончания моде-лирования (К, M)-й дуги которого подключен к (К, И)-му информационному входу блока регистрации, (К, М)-й информационный выход которого является выходом признака принадлежности (К, M)-го ребра дереву кратчайших путей устройства и подключен к входу опроса (К, M)-й дуги блока определения конечных вершин дуг, вход начальной установки устройства подключен к вхо-ду установки в "О" блока регистрации, вход пуска устройства подключен к входу имитации исполнения начальной вершины блока определения кратчайшего пути.
Ь Е Е
ЬЬ
° ° a„ /a„mл ®вл
1У 19 /9gy 1Я го„2
20 у ga
®as 4 ââ
Составитель А. Мишин
Техред M.Ходанич
Редактор М. Лазоренко
Корректор С. Черни
Заказ 3387 Тираж 568 Подписное
ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР
113035, Москва, Ж-35, Раушская наб., д. 4/5
Производственно-издательский комбинат "Патент", r Ужгород, ул. Гагарина, 101
Ь Ь °
° ° °
° ° Ь
1603396
17
° ° ° бп ® вв Раг. 3
® ВВ
