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

О)

о оо

Од СО О5

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

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

На фиг. 1 представлена функциональ ная схема устройства; на фиг. 2 функциональная схема блока определе ния конечных вершин дуг; на фиг. 3 функциональная схема блока удаления заходящих дуг; на фиг. 4 - функцио нальная схема блока регистрации.

Устройство содержит блок 1 задания матрицы смежности, блок 2 удаления заходящих дуг, блок 3 определения кратчайшего пути, блок 4 регистрации и блок 5 определения- конечных вершин дуг. Кроме того, на фиг. 1 обозначено: 6 вход начальной установки усТ ройства; 7 вход пуска устройства и 8 - выход признаков принадлежности ре бер дереву кратчайших путей.

Блок 5 определения конечных вершин дуг содержит матрицу из В х В элементов И 9, где В количество вершин в графе, и группу из В элементов ИЛИ 10, причем вход 11 признака наличия (К, М)й дуги блока 5 определения конечных вершин дуг (К 1,...,В; М 1,...sB) подключен к первому входу элемента И 9 строки матрицы, выход которого подключен к входу К-го элемента ИЛИ 10 группы, выход которого является выходом 12 признака соответствия К-й вершины конечной вершине дуги блока 5 определения конечных вершин дуг, вход 13 опроса (к, М)-й дуги графа которого подключен к второму входу К-го элемента И 9 М-й строки матрицы.

Блок 2 удаления заходящих дуг содержит матрицу из В X В ключей 14, причем вход 15 признака наличия (К, М)й дуги блока 2 удаления заходящих дуг подключен к информационному входу К-го ключа 14 М-й строки матрицы, информационный выход которого является выходом 16 признака наличия (К, М)-й дуги блока удаления заходящих дуг, вход 17 задания К-й вершины которого подключен к управляющим (отключающим) входам всех ключей 14 К-го столбца матрицы.

Блок 4 регистрации содержит матрицу из В X В триггеров 18, причем (К,

964

М)-й информационный вход 19 блока 4 регистрации подключен к входу установки в 1 К-го триггера М-й строки матрицы, прямой выход которого является (К, М)-м информационным выходом 20 блока 4 регистрации, вход 21 установки в О которого подключен к входам установки в О всех триггеров 18 матрицы.

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

Перед началом работы в блок 1 задания матрицы смежности заносят информацию о топологии графа, при этом ребра графа задают двумя противоположно направленными дугами, обнуляют блок

о

5

0

5

0

5

4 регистрации, в блок 3 определения кратчайшего пути заносят информацию о параметрах вершин и ребер (цепи установки параметров моделирования вершин и ребер не показаны). о

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

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

Блок 4 регистрации работает следующим образом.

При поступлении на вход 21 установки в О импульса уровня логической единш все триггеры 18 устанавливаются в О. При появлении сигналов уровня 1 на входах 19 соответству- им триггеры 18 устанавливаются в 1.

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

Устройство для определения парамет- ров графа, содержащее блок задания

матриц, смежности, блок определения кратчай иего пути и блок регистрации, причем вход задания начальной вершины графа устройства подключен к одноименному входу блока определения кратчайшего пути, отличающееся тем, что, с целью расширения функциональных возможностей устройства за счет определения ребер дерева кратчайших путей в графе, в него введены блок определения конечных вершин дуг и блок удаления заходящих дуг, причем выход признака наличия (К, М)-й дуги блока задания матрицы смежности (К 1,...,Bj М 1,...,В, где В - количес во вершин в графе) подключен к одноименному входу блока удаления заходящих дуг и к одноименному входу блока определения конечных вершин дуг, выход признака соответствия К-й .вершины конечной вершине дуги которо1bU

1bU3J9(i

го подключен к входу задания К-й вершины блока удаления заходящих дуг, вькод признака наличия (К, М)-й дуги которого подключен к одноименному входу блока определения кратчайшего пути, выход признака окончания моделирования (К, М)-й дуги которого подключен к (К, М)-му информационному

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

конечных вершин дуг, вход начальной установки устройства подключен к входу установки в О блока регистрации, вход пуска устройства подключен к

входу имитации исполнения начальной вершины блока определения кратчайшего п(ути.

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

/5/

fpuz.2

16„Г6, /5,

7% 75; 1

2;

%

1тТ

J32iJ3iB

21

егг

2/

.X%2

t г/7„

00

Л/%в. f

Редактор М. Лазоренко

2%7 2% .

Составитель A. Мишин

Техред М.Ходанич , Корректор С. Черни

IB2В

00

pUg 2/

Л/%в. f