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

(21) 4 (22) 2 (46) 2 (72) О В.Ю.И (53) 6 ГОСУДАРСТВЕННЫЙ КОМИТЕТПО ИЗОБРЕТЕНИЯМ И ОТНРЫТИПРИ ПНТ ССО 417805/24-245.01.883.04.90. Бюл. У 15(56) Авторское свидетельство СССРМ 1376098, кл. С 06 Г 15/20, 1986.Авторское свидетельство СССРЮ 1348850, кл. С О 6 Г 1 Я 2 О, 1986.(54) УСТРОЙСТВО ДЛЯ ИССЛЕДОВАНИЯ ПМЕТРОВ ГРАФА(57) Изобретение относится к вычислительной технике и может быть использовано для решения задач оптимальногоразмещения аварийных служб, пунктовобслуживания, баз данных, коммутаторов телефонных сетей, подстанций,электросетей и исследования другихобъектов, описываемых графами, Цельюизобретения является расширение функциональных возможностей устройства 2за счет определения центров графа;Устройство содержит блок 1 синхронизации, блок 2 определения кратчайшего пути, блок 3 задания матрицы смежности, блок 4 регистрации времени исполнения вершин и блок 5 выбора минимума . Устройство для исследования параметров графа имеет вход 6 пуска, выходы 7 группы блока 1 синхронизации, входы 8 задания веса ребер графа устройства, выход 9 признака исполнения всех вершин графа, первый 10 и второй 11 выходы блока 1 синхронизации, вход 12 начальной установки устройства и выходы 13 признаков соответствия вершин центру графа . При подаче на вход 6 импульса уровня логической единицы блок 1 синхронизации форнирует лоследовательность импульсов уровня логицеской единицы. При.атон блок Ц: фиксирует время исполнения всех вершин графа при использовании в качестве начальной каждой из них. Для вершин, соответствующих центру графа, это время минимальное. 3 ил.Изобретение относится к вычислительной технике и может быть исполь" зовано для решения задац оптимального размещения аварийных служб, пунктов обслуживания, баз данных, коммутаторов телефонных сетей, подстанций, электросетей и исследования других обьектов описываемых .графами.Целью изобретения является расши- О рение функциональных возможностей уст" ройства за счет определения центров граФаНа Фиг. 1 представлена функциональная схема устройства; на фиг. 2 - временная диаграмма работы блока синхронизации; на фиг. 3 - Функциональная схема блока регистрации времени исполнения вершин.Устройство. содержит блок 1 синхро низации, блок 2 определения кратчайшего пути, блок 3 задания матрицы смежности, блок 4 регистрации времени исполнения вершин и блок 5 выбора минимума. Кроме того, на фиг. 1 показаны 25 вход 6 пуска устройства, выходы 7 группы блока 1 синхронизации, входы 8 задания веса К-, М-го ребра графа устройства (К = 1 е В И = 1 ,В где В - количество вершин в графе), ЗО выход 9 признака исполнения всех вершин графа, первый 10 и второй 11 выходы, блока 1 синхронизации, вход 12 начальной установки устройства и выхо ды 13 признаков соответствия вершин центру графа устройства.Блок 4 регистрации времени исполнения вершин (графа) .содержит времяимпульсный интегрирующий преобразователь 14 и группу из В элементов 15 памяти, причем вход 16 пуска блока 4 подключен к входу разрешениярабаты преобразователя 14, информационный выход которого подклюцен к информационным входам всех элементов 19 памяти груп- д 5 пы, входы признаков записи которых подключены к входу 17 признака записи блока 4 регистрации времени исполнения вершин, вход 18 подготовки которого подключен к входу установки в "0" преобразователя 14, К-й разряд ад" ресного входа 19 блока 4 подключен к входу разрешения записи К-го элемента 15 памяти, информационный выход которого является К-м информационным выходом 20 блока Устройство работает следующим образом. Перед началом работы, подавая навход 12 начальной установки импульсный сигнал уровня логической единицы,обнуляют блок 4 регистрации времениисполнения вершин. В блок 3 заданияматрицы смежности заносят информациюо топологии графа, по входам 8 задаютвеса ребер графа. На вход 6 пуска устройства подают импульс уровня логицеской единицы, При этом блок 1 синхронизации формирует последовательностьсигналов уровня логической единицы,предусмотренную временной диаграммойего работы. Сигнал появляется на выходе О блока синхронизации. При этомпроисходит начальная установка блока2 определения кратчайшего пути и подготовка блока 4 регистрации. По завершении указанных операций блок 1 синхронизации снимает сигнал с выхода1 О и формирует сигналы на выходе 11 ипервом выходе 7 группы. При этом блок2 определения кратчайшего пути имитирует исполнение начальной вершины (вданном слуцае первой), блок 4 регистрации начинает подсчет времени исполнения вершин, Через время, достаточноедля исполнения всех вершин графа, блок2 формирует на своем выходе 9 импульсуровня логической единицы,При этом блок 1 останавливает счет времени блока 4, снимая сигнал с своего выхода 11, а блок 4 регистрирует время исполнения всех вершин графа из его К-й вершины. Через время, достаточное для регистрации, блок 1 синхронизации снимает сигнал с своего первого выхода 7 группы и формирует сигнал на выходе 10. При этом обнуляется блок 2 определения кратчайшего пути и подготавливается к работе блок 4 регистрации. По завершении указанных . операций блок 1 синхронизации снимает сигнал с выхода 1 О и формирует его на выходе 11 и втором выходе 7 группы. Далее работа устройства повторяется до полного перебора всех В вершин графа. По оконцании работы устройства номер позиции сигнала с минимальным значением блока 5 соответствует номеру вершины, которая является центром графа.Блок 4 регистрации времени исйолнения вершин работает следующим образомПри поступлении на вход 12 начальной установки импульса уровня логицес 1 Я 93 кой единицы все элементы 5 памяти группы обнуляются. При поступлении на вход 18 подготовки импульса начальной установки преобразователь 14 устанавливается в "0". При поступлении на вход 16 пуска импульса уровня логической единицы преобразователь 14 формирует на своем выходе линейно возрастающий сигнал (напряжение или код),10 величина которого пропорциональна длительности импульса на входе 16. При поступлении импульса уровня логичес" кой единицы на вход 17 элемент 15 памяти, выбранный потенциалом на одном из входов 19, регистрирует значение сигнала с выхода преобразователя 14. Формула изобретения20Устройство для исследования параметров графа, содержащее блок заданияматрицы смежности, блок определения кратчайшего пути и блок регистрации времени исполнения вершин, причем вы ход признака .наличия К,И-го ребра графа (К = 1.В, И 1 В, где В - количествовершин в графе) подключен к одноименному входу блока определения кратчайшего пути, вход начальной установки устройства подклюПчен к входу установки в 0 блока регистрации времени исполнения вершин, о т л и ч а ю щ е е с я тем, что, с целью расширения Функциональных возоможностей устройства за счет определения центров графа, в него введены = блок синхронизации и блок выбора минимума, причем вход пуска устройства подключен к входу пуска блока синхронизации, К-й выход группы которого подключен к входу имитации исполнения К-й вершины блока определения кратчайшего пути и к К-му разряду адресного входа блока регистрации времени исполнения вершин, К-й информационный выход которого является выходом времени исполнения всех вершин графа из его К-й вершины устройства и подключен к К-му информационному входу блока выбора минимума, К-й выход позиции минимума которого является выходом признака соответствия К-й вершины центру графа устройства, вход задания веса К,И-го ребра графа устройства подключен к одноименному входу блока определения кратчайшего пути, выход признака исполнения всех вершин графа которого подключен к входу признака записи блока регистрации времени исполнения вершин и к тактовому входу блока синхронизации, первый выход которого под" ключен к входу начальнойустановки блока определения кратчайшего пути и к входу подготовки блока регистрации времени исполнения вершин, вход пуска которого подключен к второму выходу блока синхронизации.1559354 Составитель А. МишинТехред М. Ходанич Корректор И, Муск Редактор И. 11 улл Подписно и ГКНТ СССР роиэводственно-издательский комбинат "Патент", г. Ужгород, ул. Гагарина,1 Заказ 838 ВНИИПИ Госу Тираж 565 рственного комитета по изобрете 113035, Москва Ж, Раушск