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

(я)5 6 06 Е 15/419 комитетИ ОТКРЫТИЯМ ГОСУДАРСТВЕННЬПО ИЭОБРЕТЕНИПРИ ГКНТ СССР ИЗОБРЕ ЕЛЬСТВУ(56) Авторское свидетельство СССРЬ 1348850, кл. 6 06 Р 15/20; 1986.Авторское свидетельство СССРМ 1559354, кл. 6 06 Р 15/20, 1988.(54) УСТРОЙСТВО ДЛЯ РЕШЕНИЯ 3НА ГРАФАХ(57) Изобретение относится к обласчислительной техники и может быть иэовано для решения задач оптимаразмещения аварийных служб, базжения и других объектов, описывграфами, Целью изобретения яврасширение функциональных возм Изобретение относится к области вы- . числительной техники и может быть исполь- . зовано для решения задач оптимального размещения аварийных служб, баз снабжения, пунктов обслуживания и исследования других объектов, описываемых графами.Целью изобретения является расширение функциональных возможностей устрой. ства эа счет определения центров в графе со взвешенными вершинами и дугами.На чертеже представлена функциональная схема устройства.Устройство содержит блок 1 синхронизации, блок.2 определения величины кратчайшего пути, блок 3 выбора максимума. многоканальный блок 4 регистрации, много. стей устройства за счет определения центров в графе со взвешенными вершинами и дугами, Устройство содержит блок 1 синхронизации, блок 2 определения величины кратчайшего пути, блок 3 выбора максимума, многоканальный блок 4 регистрации, многоканальный блок 5 умножения, блок 6 выбора минимума, вход 7 пуска устройства, входы 8 задания элементов матрицы весов дуг устройства, входы 9 задания веса вершин устройства и выходы 10 признаков принадлежности вершин. множеству центров графа. При поступлении на вход 7 пуска устройства импульса уровня логической единицы, блок 1 синхронизации формирует последовательность сигналов, под управлением которой на выходах 10 устройства формируются сигналы признаков соответствия вершин центрам графа, 1 ил. канальный блок 5 умножения, блок 6 выбора минимума, вход.7 пуска устройства, входы 8 задания элементов матрицы весов дуг устройства, входы 9 задания веса вершин устройства и выходы 10 признаков принадлежности вершин множеству центров графа устройства,Предлагаемое устройство работает следующим образом.Перед началом работы по входам 8 задают веса дуг, а по входам 9 веса вершин исследуемого графа, Решение начинается подачей импульса уровня логической единицы на вход 7 пуска устройства. При этом блок 1 синхронизации формирует импульс на первом выходе группы выходов блока, 171653825 30 информационных выходов поступают на соответствующие входы группы входов пер 40 45 который поступает на соответствующий вход группы входов опроса блока 2 определения кратчайшего пути и соответствующий вход группы входов выбора многоканального блока 4 регистрации, При этом в блоке 2 осуществляется определение кратчайших путей из первой вершины графа во все остальные, а в блоке 4 подключается к информационному входу его первый элемент памяти. По мере моделирования достижения вершин исследуемого графа появляются сигналы на соответствующих выходах группы. выходов веса путей блока 2, откуда они поступают на соответствующие информационные входы блока 3 выбора максимума, Через время, достаточное для достижения всех вершин графа, будут присутствовать сигналы на всех информационных входах блока 3 и сигнал с его информационного выхода, пропорциональный максимальному.из всех кратчайших путей из первой вершины во все остальные вершины графа, поступает нв информационный вход многоканального блока 4 регистрации, где записывается в первый элемент памяти, Далее устройство работает аналогично, но при этом начальной вершиной будет вторая, затем третья и так далее до полного перебора всех вершин графа, По завершении этого процесса появляется сигнал уровня логической единицы на выходе блока синхронизации, который поступает на вход записи блока 4 и сигналы с его вых сомножителей многоканального блока 5 умножения. При этом в блоке 5 осуществляется умножение сигналов, поступающих на входы первых сомножителей,. на сигналы, пропорциональные весам вершин и поступающие на входы 9 вторых сомножителей блока, и сигналы, пропорциональные произведениям, поступают с информационных выходов блока 5 на информационные входы блока 6 выбора минимума, Минимальная из этих величин, выбранная блоком 6 и зафиксированная сигналом на его соот 5 10 15 20 ветствующем признаковом выходе 10, однозначно покажет вершину (или вершины), являющиеся центром графа со взвешеннымидугами и вершинами. Формула изобретения Устройство для решения задач на графах, содержащее блок синхронизации, блок определения величины кратчайшего пути, многоканальный блок регистрации и блок выбора минимума, причем вход пуска устройства подключен к входу пуска блока синхронизации, выход которого подключен к входу признака записи многоканального блока регистрации, К-й выход позиции минимума блока выбора минимума (К.В, где В - количество вершин в графе) является выходом признака принадлежности К-й вершины множеству центров графа устройства, вход задания (К,М)-го элемента матрицы весов дуг которого (М=1 В) подключен к входу задания веса (К,М)-й дуги блока определения величины кратчайшего пути, о т л и ч а ю щ е е с я тем, что, с целью расширения функциональных возможностей устройства за счет определения центров в графе со взвешенными вершинами и дугами, в него введен блок выбора максимума и многоканальный блок умножения, причем К-й выход группы синхронизации подключен к входу выбора К-го канала многоканального блока регистрации и к входу опроса К-й вершины блока определения:величины кратчайшего пути, выход веса пути в К-ю вершину которого подключен к К-му информационному входу блока выбора максимума, информационный выход которого подключен к информационному входу многоканального блока регистрации, информационный выход К-го канала которого подключен к входу первого сомножителя К- го канала, вход задания весе К-й вершины устройства подключен к входу второго сомножителя К-го канала многоканального блока умножения, выход К-го канала которого подключен к К-му информационному входу блока выбора минимума.1716538 Составитель О,АлексееТехред М,Моргентал орректор Т,М Н.Коляд едак при ГКНТ С 10 зводственно-издательский комбинат "Патент", г. Ужгород, ул. Г Заказ 614 Тираж ВНИИПИ Государственного комитета и 113035, Москва, Ж