Устройство для решения задач на графах

 

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

СОЮЗ СОВЕТСКИХ

СОЦИАЛИСТИЧЕСКИХ

РЕСПУБЛИК

1 (я)э 6 06 F 15/419

ГОСУДАРСТВЕННЫЙ КОМИТЕТ

ПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМ

ПРИ ГКНТ СССР

ОПИСАНИЕ ИЗОБРЕТЕНИЯ . К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ

1 (21) 4769983/24 (22) 14.12.89 (46) 29,02.92,.Бюл. tk 8 (72) О.Г. Алексеев, А.М. Борисов и Н,И, Ячкула (53) 681,333(088.8) (56) Авторское свидетельство СССР

hh 1348850, кл. G 06 F 15/20; 1986.

Авторское свидетельство СССР

N - 1559354, кл. 6 06 F 15/20, 1988. (54) УСТРОЙСТВО ДЛЯ РЕШЕНИЯ ЗАДАЧ

HA ГРАФАХ (57) Изобретение относится к области вычислительной техники и может быть использовано для решения задач оптимального размещения аварийных служб, баз снабжения и других объектов, описываемых графами, Целью изобретения является расширение функциональных возможноИзобретение относится к области вычислительной техники и может быть использовано для решения задач оптимального размещения аварийных служб, баз снабжения, пунктов обслуживания и исследования других объектов, описываемых графами.

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

На чертеже представлена функциональная схема устройства.

Устройство содержит блок 1 синхронизации, блок 2 определения величины кратчайшего пути, блок 3 выбора максимума. многоканальный блок 4 регистрации, много„>Ы „„171б538 А1 стей устройства за счет определения центров в графе со взвешенными вершинами и дугами. Устройство содержит блок 1 синхронизации, блок 2 определения величины кратчайшего пути, блок 3 выбора максимума. многоканальный блок 4 регистрации, многоканальный блок 5 умножения, блок 6 выбора минимума, вход 7 пуска устройства, входы 8 задания элементов матрицы весов дуг устройства, входы 9 задания веса вершин устройства и выходы 10 признаков принадлежности вершин. множеству центров графа. При поступлении на вход 7 пуска устройства импульса уровня логической единицы, блок 1 синхронизации формирует последовательность сигналов, под управлением которой на выходах 10 устройства фор- ф мируются сигналы признаков соответствия вершин центрам графа, 1 ил. канальный блок 5 умножения, блок 6 выбора минимума, вход.7 пуска устройства, входы 8 задания элементов матрицы весов дуг устройства, входы 9 задания веса вершин устройства и выходы 10 признаков принадлежности вершин множеству центров графа устройства.

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

Перед началом работы по входам 8 задают веса дуг, а по входам 9 веса вершин исследуемого графа. Решение начинается подачей импульса уровня логической единицы на вход 7 пуска устройства. При этом блок 1 синхронизации формирует импульс на первом выходе группы выходов блока, 1716538

25

35

45 который поступает на соответствующий вход группы входов опроса блока 2 определения кратчайшего пути и соответствующий вход группы входов выбора многоканального блока 4 регистрации, При этом в блоке 2 осуществляется определение кратчайших путей из первой вершины графа во все остальные, а в блоке 4 подключается к информационному входу его первый элемент памяти. По мере моделирования достижения вершин исследуемого графа появляются сигналы на соответствующих выходах группы. выходов веса путей блока 2, откуда они поступают на соответствующие информационные входы блока 3 выбора максимума, Через время, достаточное для достижения всех вершин графа, будут присутствовать сигналы на всех информационных входах блока 3 и сигнал с его информационного выхода, пропорциональный максимальному.из всех кратчайших путей из первой вершины во все остальные вершины графа, поступает нв информационный вход многоканального блока 4 регистрации, где записывается в первый элемент памяти. Далее устройство работает аналогично, но при этом начальной вершиной будет вторая, затем третья и так далее до полного перебора всех вершин графа. По завершении этого процесса появляется сигнал уровня логической единицы на выходе блока синхронизации, который поступает на вход записи блока 4 и сигналы с его информационных выходов поступают на соответствующие входы группы входов первых сомножителей многоканального блока

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

6 и зафиксированная сигналом íà его соответствующем признаковом выходе 10, однозначно покажет вершину (или вершины), являющиеся центром графа со взвешенными дугами и вершинами.

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

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

1716538

Составитель Q.Àëåêñååâ

Техред ММоргентал Корректор Т.Малец

Редактор Н.Коляда

Производственно-издательский комбинат "Патент", r. Ужгород; ул. Гагарина, 101

Заказ 614 Тираж Подписное

ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР

113035, Москва, Ж-35, Раушская наб., 4/5