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

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

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

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

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

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

Устройство.содержит блок 1 синхро- 20 шении указанных операций блок 1 синнизации, блок 2 определения кратчайшего пути, блок 3 задания матрицы смежности, блок k регистрации времени исполнения вершин и блок 5 выбора минимума. Кроме того, на фиг. 1 показаны вход 6 пуска устройства, выходы 7 группы блока 1 синхронизации, входы 8 задания веса К-, М-го ребра графа устройства (К 1,,..,В;. М 1,...,В, где В - количество вершин в графе), выход 9 признака исполнения всех вершин графа, первый 10 и второй 11 выходы -блока 1 синхронизации, вход 12 начальной установки устройства и выхо ды 13 признаков соответствия вершин центру графа устройства.

Блок-k регистрации времени исполнения вершин (графа).содержит времяимПри этом блок 1 останавливает счет времени блока Ц, снимая сигнал с свое го выхода 11, а блок k регистрирует время исполнения всех вершин графа из его К-й вершины. Через время, достаточное для регистрации, блок 1 синхро низации снимает сигнал с своего перблок 2 определения кратчайшего пути и подготавливается к работе блок 4 регистрации. По завершении указанных пульсный интегрирующий преобразователь Т и группу из В элементов 15 памяти, 40 вого вых°Да 1 группы и формирует сиг- причем вход 16 пуска блока k подклю- нал на выходе 10. При этом обнуляется чен к входу разрешения работы преобразователя 14, информационный выход которого подключен к информационным входам всех элементов Э памяти труп- 45 опеРаЧий блок 1 синхронизации снимает пы, входы признаков записи которыхсигнал с выхода 10 и формирует его на

подключены к входу 17 признака записи выходе 11 и втором выходе 7 группы, блока k регистрации времени исполне- Далее работа устройства повторяется ния вершин, вход 18 подготовки которого подключен к входу установки в JQ О преобразователя Н, К-й разряд адресного входа 19 блока k подключен к входу разрешения записи К-го элемента 15 памяти, информационный выход которого является К-м информационным

выходом 20 блока Ц.

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

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

Блок k регистрации времени исполнения вершин работает следующим образом.

При поступлении на вход 12 начальной установки импульса уровня логичесхронизации снимает сигнал с выхода 10 и формирует сигналы на выходе 11 и первом выходе 7 группы. При этом блок 2 определения кратчайшего пути имитирует исполнение начальной вершины (в данном случае первой), блок k регистрации начинает подсчет времени исполнения вершин. Через время, достаточное для исполнения всех вершин графа, блок 2 формирует на своем выходе 9 импульс уровня логической единицы.

При этом блок 1 останавливает счет времени блока Ц, снимая сигнал с своего выхода 11, а блок k регистрирует время исполнения всех вершин графа из его К-й вершины. Через время, достаточное для регистрации, блок 1 синхронизации снимает сигнал с своего первого вых°Да 1 группы и формирует сиг- нал на выходе 10. При этом обнуляется опеРаЧий блок 1 синхронизации снимает сигнал с выхода 10 и формирует его на

блок 2 определения кратчайшего пути и подготавливается к работе блок 4 регистрации. По завершении указанных вого вых°Да 1 группы и формирует сиг- нал на выходе 10. При этом обнуляется опеРаЧий блок 1 синхронизации снимает сигнал с выхода 10 и формирует его на

выходе 11 и втором выходе 7 группы, Далее работа устройства повторяется

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

Блок k регистрации времени исполнения вершин работает следующим образом.

При поступлении на вход 12 начальной установки импульса уровня логичес155935

кой единицы все элементы 15 памяти группы обнуляются0 При поступлении на вход 18 подготовки импульса начальной установки преобразователь 1 устанавливается в О. При поступлении на 5 вход 16 пуска импульса уровня логической единицы преобразователь 1 формирует на своем выходе линейно возрастающий сигнал (напряжение или код),, величина которого пропорциональна длительности импульса на входе 16. При поступлении импульса уровня логической единицы на вход 17 элемент 15 памяти, выбранный потенциалом на одном К-й вершины устройства и подключен к

из входов 19, регистрирует значение сигнала с выхода преобразователя .

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

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

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

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

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

б

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

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

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

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

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

/ЈЭ 1S&

Фи&З