Устройство для исследования параметров графа
Изобретение относится к вычислительной технике и может быть использовано для решения задач оптимального размещения аварийных служб, пунктов обслуживания, баз данных, коммутаторов телефонных сетей, электросетей и исследования других объектов, описываемых графами. Целью изобретения является расширение функциональных возможностей устройства за счет определения медиан графа. Устройство содержит блок 1 синхронизации, блок 2 определения кратчайшего пути, блок 3 задания матрицы смежности, блок 4 регистрации времени исполнения вершин, блок 5 выбора минимума и группу из B сумматоров 6, где B - количество вершин в графе. Устройство для исследования параметров графа имеет вход 7 пуска устройства, вход 8 начальной установки устройства, первый 9 и второй 10 выходы блока 1 синхронизации, его выходы 11 группы, выход 13 признака исполнения всех вершин графа и выходы 14 признаков соответствия вершин медианам графа. Перед началом работы на вход 8 устройства подают импульс уровня логической единицы. При этом блок 4 регистрации обнуляется. В блок 3 задания матрицы смежности заносят информацию о топологии графа. По входам 12 задают веса ребер графа. На вход 7 пуска устройства подают импульс уровня логической единицы. При этом блок 1 синхронизации формирует последовательность сигналов уровня логической единицы, по которой в блоке 4 регистрации будет зафиксировано время, необходимое для достижения M-й вершины графа из его K-й вершины по кратчайшему пути (M=1,...,B K=1,...,B), а на выходе блока 5 будут выделены медианы графа. 3 ил.
сОюз сОветсних
СОЦИАЛИСТИЧЕСНИХ
КСПУБЛИН (19) (И) А1 (51)5 G 06 F 15/20
OflHCAHHE ИЗОБРЕТЕНИЯ
К A ВТОРСКОМЪ(СВИДЕТЕЛЬСТВУ
ГОсудАРстэенный нОмитет
flo изОБРетениям и ОтнРытиям пРи Гннт сссР (21 ) 44 1 7805/ 24-24;. (22) 25. 01 . 88.
: (46) 23.04.90. Вюл. -15 (72) О.Г.Алексеев, С.Н Зотов, В.Ю.Мержанов и Н.И.Ячкула (53) 681.333(088.8) (56) Авторское свидетельство СССР
Р 1320814, кл. G 06 F 15/20, 1986.
Авторское свидетельство СССР
Р 1348850 кл. С 06 F 15/20, 1986. (54) УСТРОЙСТВО ДЛЯ ИССЛЕДОВАНИЯ
ПАРАМЕТРОВ ГРАФА (57) Изобретение QTHocHTcH к вычислительной технике и может быть исполь2 зовано для решения задач оптимального размещения аварийных служб, пунктов обслуживания, баз данных, комму/ таторов телефонных сетей, электросетей и исследования других объектов-, описываемых графами. Целью изобретения является расширение функциональных возможностей устройства s а счет опре деления медиан графа. Устройство содержит блок 1
- синхронизации, блок 2 определения кратчайшего пути, блок 3 задания матрицы смежности, блок 4 регистрации времени исполнения вершин, блок 5 выбора минимума и группу из В сумматоров 6, 3, 1559353 где  — количество вершин в графе.
Устройство для исследования параметров графа имеет вход 7 пуска устройства, вход 8 начальной установки устройства, первый 9 и второй 10 выходы блока 1 синхронизации, его выходы 11 группы, выход 13 признака исполнения всех вершин графа и выходы 14 признаков соответствия вершин медианам графа. Перед началом работы на вход 8 устройства подают импульс уровня логической единицы. При этом блок 4 регистрации обнуляется. В блок 3 задания матрицы смежности заносят инфорИзобретение относится к вычислительной технике и может быть исполь" зовано для решейия задач оптимального размещения аварийных служб, пунктов
25 обслуживания, баз данных, коммутаторов телефонных сетей, подстанций, I электросетей и исследования других объектов, описываемых графами.
Целью изобретения является расширение функциональных возможностей ус" тройства за счет определения медиан графа.
На фиг.1 представлена функциональ- 35 ная схема устройства; на фиг.2 — функциональная схема блока регистрации времени исполнения .вершин; на фиг.3— временная диаграмма работы блока синхронизации. 40
Устройство содержит блок 1 синхронизации, блок 2 определения кратчайшего пути, блок 3 задания матрицы смежности, блок 4 регистрации времени исполнения вершин, блок 5 выбора минимума и группу из В (где В— количество вершин в графе) сумматоров
6. Кроме того, на фиг.1 показаны вход.
7 пуска устройства, вход 8 начальной установки устройства, первый 9 и второй 10 выходы блока i синхронизации, выходы 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 регистрации фиксируется время, необходимое для достижения M-й вершины из K-й по кратчайшему пути (M = 1,...,Â; К = 1, ...,В) 15
Минимальная сумма времен достижения
М-й вершины из всех вершин графа, выбранная блоком 5, покажет медиану граф а.
Блок 4 регистрации содержит времяимпульсный интегрирующий преобразова- тель 15 и матрицу из В х В элементов 16 памяти, причем входы подготовки 17 и пуска 18 блока 4 подключены к входу установки в "0" и входу разрешения работы преобразователя 15 соответственно, информационный выход которого подключен к информационным входам всех элементов 16 памяти, К-й разряд адресного входа 19 блока 4 регистрации подключен к входам разрешения записи всех элементов 16 памяти К-й строки матрицы, М-й вход 20 признака записи времени исполнения
M-й вершины графа подключен к входам признаков записи всех элементов 16 памяти М-ro столбца матрицы, выход
К-го элемента 16 памяти М-го столбца матрицы является выходом 21 времени достижения М-й вершины графа из его
К-й вершины (по кратчайшему пути) блока 4 регистрации, вход 22 установки в "0" которого подключен к входам установки в "0" всех элементов 16 памяти.
Блок 4 регистрации работает следующим образом.
При поступлении на вход 22 установки в "0" блока 4 регистрации импульса уровня логической единицы обнуляются все элементы 16 матрицы. При
50 подаче сигнала на вход 17 подготовки блока 4 регистрации импульса уровня логической единицы преобразователь
15 устанавливается в "О". При подаче импульса уровня логической единицы на вход 18 пуска преобразователь 15 формирует линейно возрастающий сигнал (напряжение или код), величина которого пропорциональна длительности импульса. По окончании действия импульса на входе 18 преобразователь 15 переходит в режим хранения сигнала.
При поступлении импульса уровня логической единицы на один из входов 20 элемент 16 памяти, выбранный потенциалом уровня логической единицы, по одному из входов 19 регистрирует значение сигнала с выхода преобразовате- ля 15.
Совмещение в рамках одного устройства возможности решения нескольких вычислительных задач, каждая из которых требует для своего решения оборудования, общего (т.е. эквивалентного или идентичного) с оборудованием других задач, можно сократить суммарные аппаратурные затраты, необходимые для решения всего комплекса задач, Например, предлагаемое устройство для определения медиан графа можно совместить с устройством для определения центров графа, так как обе задачи требуют для своего решения идентичных блоков синхронизации, блоков определения кратчайшего пути (моделей графа), блоков задания матриц смежнбсти с соответствующими функциональными связями. Для этого необходимо в предлагаемое устройство ввести второй блок регистрации времени исполнения вершин и второй блок выбора минимума, с соответствующими функциональными связями.
Если совмещение оборудования позволяет решать параллельно все задачи комплекса (как, например, в устройстве для определения центров и медиан графа), то, кроме сокращения аппаратурных затрат, достигается и повьппение быстродействия при решении всего комплекса задач.
Однако. часто совмещение оборудования не позволяет решать все (или некоторые) задачи комплекса одновременно, например, если общая часть оборудования должна быть подключена к выходу индивидуальной части оборудования каждой задачи. В этом случае используют методы коммутации. При этом индивидуальную часть оборудования каждой задачи подключают с помощью коммутаторов на вход общей части оборудования последовательно во времени. Например, в рамках устройства для определения центров и медиан графа можно совместить два идентич1559353 ных блока выбора минимума, подключая, при помощи коммутатора, выходы сум- маторов б и выходы второго блока регистрации к его информационным вхо5 дам. Нодавая на управляющий вход коммутатора сигнал выбора информационйого направления с дополнительного выхода блока 1 синхронизации или с входа управления режимом работы (медианы/цент-.10 ры) устройства, можно последовательно . во времени решить обе задачи.
Иногда все (или некоторые) задачи комплекса требуют повторного использования общей для них или индивидуаль-15 ной части оборудования. В этом случае используют различного рода блоки про межуточной регистрации (триггеры, ре,гистры, счетчики, блоки памяти, матрицы регистров, триггеров и т.п.), выход блока регистрации через коммутаторы подключают к общей (индивидуальной) части оборудования и синхронизируют момент записи информации в блок ретистрации и выбор информационного на- д5 правления коммутатора.
Указанные методы простого совмещеЙия оборудования, коммутации и промежуточной регистрации могут быть использованы не только на уровне бло- 30 ков устройств, но и на уровне узлов блоков, элементов узлов и т.д. Можно, .например, совместить общую часть оборудования нескольких блоков синхронизации различной констРукции (совме- 35 щение тактовых генераторов), блоков регистрации (например, адресных дешиф-.
Раторов), блоков выбора минимума и максимума и т.д. .40
Формула изобретения
Устройство для исследования параметров графа, содержащее блок определения кратчайшего пути, блок задания матрицы смежности и блок регистрации 45 времени исполнения верщин, причем вход начальной установки устройства
11 I I подключен к входу установки в О блока регистрации времени исполнения
1 вершин, выход признака наличия К-M-го ребра блока задания матрицы смежности (К=1, ...,В; М = 1, ...,В, где В количество вершин в графе) подключен к одноименному входу блока определения кратчайшего пути, о т л и ч а ю щ .е— е с я тем, что, с целью расширения функциональных возможностей устройства за счет определения медиан графа, в него введены блок синхронизации, группа из В сумматоров и блок выбора минимума,, причем вход пуска устройства подключен к входу пуска блока синхронизации, К-й выход группы которого подключен к К-му разряду адресного входа блока регистрации времени исполнения вершин и к входу имит ции исполнения К-й вершины блока определения кратчайшего пути, выход признака исполнения М-й вершины которого подключен к М-му входу признака записи блока регистрации времени исполнения вершин выход времени исполнения
М-й вершины из К-й начальной устройства подключен к входу К-го слагаемого
М-го сумматора группы, выход, которого подключен к М-му информационному входу блока выбора минимума, М-й выход позиции минимума которого является выходом признака соответствия M-й вершины медиане графа устройства, вход задания веса К,М вЂ” го ребра графа которого подключен к одноименному входу блока определения кратчайшего пути, выход признака исполнения всех вершин графа которого подключен к тактовому входу блока синхронизации, первый выход которого подключен к входу начальной установки блока определения кратчайшего пути и к входу подготовки блока регистрации времени исполнения вершин, вход пуска которого подключен к второму выходу блока синхронизации.
1559353
° ° ° 1 °
° ° °
° ° ° ь
° ° t
° ° °
° ° °
° ° ° ° °
° ° ° ° °
Bgg 2fgg
81р Н Йу 21 21gg
° ° °
Составитель А.Мишин
ТехредМ.Ходанич Корректор Т. Палий редактор И,Шулла
Заказ 838 Тираж 5б5 Подписное
ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР
113035, Москва, Ж-35, Раушская наб., д. 4/5
Производственно-издательский комбинат "Патент", г.Ужгород, ул. Гагарина,101
