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

 

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

СОЮЗ СОВЕТСКИХ

СОЦИАЛИСТИЧЕСКИХ

РЕСПУБЛИН (19) (И) (51)5 С 06 " 15/20 фба б

ГОСУДАРСТВЕННЫЙ КОМИТЕТ

ПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМ

ПРИ ГКНТ СССР

И А ВТОРСКОМ .Ф СВИДЕТЕЛЬСТВУ (21) 4417805/24-24 (22) 25.01.88 (46) 23 04.90. Бюл. N 15 (72) О.Г. Алексеев, С.Н. Зотов, В.Ю. Мержанов и Н.И. Ячкула (53) 681.333(088.8) (56) Авторское свидетельство СССР

Ю 1376098, zsl. G 06 F 15/20, 1986.

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

V 1348850, кл. G 06 F 15/20, 1986. (54) УСТРОЙСТВО ДЛЯ ИССЛЕДОВАНИЯ ПАРАМЕТРОВ ГРАФА (57) Изобретение относится к вычислительной технике и может быть использовано для решения задач оптимального размещения аварийных служб, пунктов обслуживания, баз данных, коммутаторов телефонных сетей, подстанций, электросетей и исследования других обьектов, описываемых графами. Целью изобретения является расширение функциональных возможностей устройства

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

Устройство для исследования параметров графа имеет вход 6 пуска, выходы

7 группы блока 1 синхронизации, входы

8 задания веса ребер графа устройства, выход 9 признака исполнения всех вершин графа, первый 10 и второй 11 выходы блока 1 синхронизации, вход !2 начальной установки устройства и выходы 13 признаков соответствия вершин центру графа . При подаче на вход 6 импульса уровня логической единицы блок 1 синхронизации формирует последовательность импульсов уровня логической единицы. При. этом блок 4: фиксирует время исполнения всех вершин графа при использовании в качестве начальной каждой из них. Для вершин, соответствующих центру графа, это время минимальное. 3 ил. з 1559354

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

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

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

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

rруппы блока 1 синхронизации, входы

8 задания веса К-, М-го ребра графа . устройства (К = 1,...,В И = I,...,Â> где В - количество вершин в графе), Зр выход 9 признака исполнения всех вершин графа, первый 10 и. второй 11 выходы, блока 1 синхронизации, вход 12 начальной установки устройства и выхо ды 13 признаков соответствия вершин 35 центру графа устройства.

Блок 4 регистрации времени исполнения вершин (графа) .содержит времяимпульсный интегрирующий преобразователь

14 и группу из В элементов 15 памяти, причем вход 16 пуска блока 4 подключен к входу разрешения рабаты преобразователя 14, информационный выход которого подключен к информационным входам всех элементов 19 памяти груп- 45 пы, входы признаков записи которых подключены к входу 17 признака записи блока 4 регистрации времени исполнения вершин, вход 18 подготовки которого подключен к входу установки в

"0" преобразователя !4, К-й разряд ад" ресного входа 19 блока 4 подключен к входу разрешения записи К-ro элемента 15 памяти, информационный выход которого является К-м информационным выходом 20 блока 4.

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

Перед началом работы, подавая на вход 12 начальной установки импульсный сигнал уровня логической единицы, обнуляют блок 4 регистрации времени исполнения вершин. В блок 3 задания матрицы смежности заносят информацию о топологии графа, по входам 8 задают веса ребер графа. На вход 6 пуска устройства подают импульс уровня логической единицы. При этом блок 1 синхронизации формирует последовательность сигналов уровня логической единицы, предусмотренную временной диаграммой его работы. Сигнал появляется на выходе !О блока синхронизации. При этом происходит начальная установка блока

2 определения кратчайшего пути и подготовка блока 4 регистрации. По завершении указанных операций блок 1 синхронизации снимает сигнал с выхода !

0 и формирует сигналы на выходе 11 и первом выходе 7 группы. При этом блок

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

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

При этом блок 1 останавливает счет времени блока 4, снимая сигнал с своего выхода lt, а блок 4 регистрирует время исполнения всех вершин графа из его К-й вершины. Через время, достаточное для регистрации, блок 1 синхронизации снимает сигнал с своего первого выхода 7 группы и формирует сигнал на выходе 10. При этом обнуляется блок 2 определения кратчайшего пути и подготавливается к работе блок 4 регистрации. По завершении указанных . операций блок 1 синхронизации снимает сигнал с выхода 1О и формирует его на выходе 11 и втором выходе 7 группы.

Далее работа устройства повторяется до полного перебора всех В вершин графа. По окончании работы устройства номер позиции сигнала с минимальным значением блока 5 соответствует номеру вершины, которая является центром графа.

Блок 4 регистрации времени исйолнения вершин работает следующим образом °

При поступлении на вход 12 начальной установки импульса уровня логичес155935 кой единицы все элементы 5 памяти группы обнуляются. При поступлении на вход 18 подготовки импульса начальной установки преобразователь 14 устанавливается в "0". При поступлении на вход 16 пуска импульса уровня логической единицы преобразователь 14 формирует на своем выходе линейно возрастающий сигнал (напряжение или код),10 величина которого пропорциональна длительности импульса на входе 16. При поступлении импульса уровня логичес" кой единицы на вход 17 элемент 15 памяти, выбранный потенциалом на одном из входов 19, регистрирует значение сигнала с выхода преобразователя 14.

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

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

В - количество > вершин в графе) подключен к одноименному входу блока определения кратчайшего пути, вход начальной установки устройства подклюП чен к входу установки в„0 блока регистрации времени исполнения вершин, о т л и ч а ю щ е е с я тем, что, с целью расширения функциональных воз4

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

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

К-й вершины устройства и подключен к

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

155935"

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

Техред И. Ходанич Корректор И. Муска

Редактор И. Булла

Заказ 838 Тираж 565 Подпи с ное

ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР

113035, Москва, Ж-35, Раушская наб., д. 4/5

Производственно-издательский комбинат "Патент", г. Ужгород, ул. Гагарина,101