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

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

Иллюстрации

Показать все

Реферат

 

Изобретение относится к вычислительной технике и может быть использовано для исследования путей в системах, описываемых графами. Целью изобретения является расширение функциональных возможностей устройства за счет определения ребер дерева кратчайших путей в графе. Устройство содержит блок 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

® ВВ