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

ъъ /,

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

Изобретение относится к вычислительной технике и может быть использовано для решения задач оптимального размещения аварийных служб, пунктов обслуживания, баз данных, коммутаторов телефонных сетей, электросетей и исследования других объектов, описываемых графами. Целью изобретения является расширение функциональных возможностей устройства за счет определения медиан графа. Устройство содержит блок 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 ил.

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

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

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

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

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

Перед началом работы на вход 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 регисграции подготавливается к очередному циклу измерений. Через время, достаточное для выполнения указанных операций, блок 1 синхронизации снимает сигнал с выхода 9 и формирует сигнал на выходе 10 и втором выходе 11 группы. Далее работа устройства повторяется, но при этом начальная вершина - вторая, затем третья и так далее до полного деребора всех В вершин. При этом в блоке 4 регистрации фиксируется время, необходимое для достижения М-й вершины из К-й по кратчайшему пути (М 1,...,В; К 1, ...,В) Минимальная сумма времен достижения М-й вершины из всех вершин графа, выбранная блоком 5, покажет медиану графа.

Блок 4 регистрации содержит время- импульсный интегрирующий преобразователь 15 и матрицу из В х В элементов 16 памяти, причем входы подготовки 17 и пуска 18 блока 4 подключены к входу установки в О и входу разрешения работы преобразователя 15 соответственно, информационный выход которого подключен к информационным входам всех элементов 16 памяти, К-й разряд адресного входа 19 блока 4 регистрации подключен к входам разрешения записи всех элементов 16 памяти К-й строки матрицы, М-й вход 20 признака записи времени исполнения М-й вершины графа подключен к входам признаков записи всех элементов 16 памяти М-го столбца матрицы, выход К-го элемента 16 памяти М-го столбца матрицы является выходом 21 времени достижения М-й вершины графа из его К-й вершины (по кратчайшему пути) блока 4 регистрации, вход 22 установки в О которого подключен к входам установки в О всех элементов 16 памяти.

Блок 4 регистрации работает следующим образом.

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

5

0

го пропорциональна длительности импульса. По окончании действия импульса на входе 18 преобразователь 15 переходит в режим хранения сигнала. При поступлении импульса уровня логической .единицы на один из входов 20 элемент 16 памяти, выбранный потенциалом уровня логической единицы, по одному из входов 19 регистрирует значение сигнала с выхода преобразователя 15.

Совмещение в рамках одного устройства возможности решения нескольких вычислительных задач, каждая из которых требует для своего решения оборудования, общего (т.е. эквивалентного или идентичного) с оборудованием других задач, можно сократить суммарные аппаратурные затраты, необходимые для решения всего комплекса задач. Например, предлагаемое устройство для определения медиан графа можно совместить с устройством для опреде- 5 ления центров графа, так как обе задачи требуют для своего решения идентичных блоков синхронизации, блоков определения кратчайшего пути (моделей графа), блоков задания матриц смежности с соответствующими функциональными связями. Для этого необходимо в предлагаемое устройство ввести второй блок регистрации времени исполнения вершин и второй блок выбора минимума с соответствующими функциональными связями.

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

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

5

0

5

5

ных блока выбора минимума, подключая, при помощи коммутатора, выходы сумматоров 6 и выходы второго блока регистрации к его информационным входам. Подавая на управляющий вход коммутатора сигнал выбора информационног направления с дополнительного выхода блока 1 синхронизации или с входа управления режимом работы (медианы/цент ры) устройства, можно последовательно во времени решить обе задачи.

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

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

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

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

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

W« 2/2U

1559353

21

Я« %