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

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