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

 

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

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

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

РЕСПУБЛИК

1829040 А1 (я)з G 06 F 15/20, 15/419

ГОСУДАРСТВЕННОЕ ПАТЕНТНОЕ

ВЕДОМСТВО СССР (ГОСПАТЕНТ СССР)

ОПИСАНИЕ ИЗОБРЕТЕНИЯ ",;,"„-„. ..„"- .

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (21) 4882568/24 (22) 12.11.90 (46) 23.07.93. Бюл. ¹ 27 (72) B Ã.Àíèñèìîâ, А.Н.Хомяков и Н.И,Ячкула (56) Авторское свидетельство СССР № 1392574, кл, G 06 F 15/20, 1988.

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

¹ 1251097, кл. G 06 F 15/20, 1984. (54) УСТРОЙСТВО ДЛЯ ОПРЕДЕЛЕНИЯ

ПАРАМЕТРОВ ГРАФА (1

ЬЭ

О

iO

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

Сущность изобретения заключается в том, что в устройство, содержащее матричную модель графа, блок индикации и дешифратор, введены группа элементов И, разделительные диоды и времяинтегрирующий преобразователь. При этом вход дешифратора соединен с входом задания номера вершины, окрестность которой будет определяться в процессе работы устройства, а выходы соединены с первыми входами соответствующих элементов И группы, вторые входы которых обьединены с входом запуска времяинтегрирующего преобразователя и соединены с входом запуска устройства, а инверсные входы эле(57) Изобретение относится к вычислительной технике и может быть использовано при решении на графах задачи определения окрестностей вершин графа заданного радиуса. Цель изобретения — повышение быстродействия устройства при определении окрестностей вершин графа заданного радиуса, Устройство содержит матричную модель графа, блок индикации, дешифратор, времяинтегрирующий преобразователь. группу элементов И и группу разделительных диодов, 1 ил. ментов И группы объединены с управляющим входом блока индикации и соединены с выходом признака достижения требуемого значения времяинтегрирующего преобразователя. Выходы элементов И группы соединены с катодами разделительных диодов, аноды которых соединены с полюсами модели графа, соединенными с моделями вершин исследуемого графа, которые соединены и с информационными входами блока индикации.

На чертеже приведена функциональная схема устройства, Устройство содержит матричную модель графа 1, блок индикации 2, времяинтегрирующий преобразователь 3, дешифратор 4, элементы И 5ь разделительные диоды 6 (i = 1, п, и — число вершин исследуемого графа). Кроме того, цифровые обозначения на схеме имеют: вход 7 задания номера исходной вершины (т.е. вершины, для которой определяется окрестность); входы 8>, i = 1, и, j = 1. п, i A j задания веса

1829040 дуг исследуемого графа; полюса 9ь i = 1, и, соединенные с моделями вершин исследуемого графа; вход 10 задания величины требуемого радиуса; вход 11 запуска устройства; вход 12 возврата времяинтегрирующего преобразователя в исходное состояние; управляющий вход 13 блока индикации, Модель графа 1 предназначена для задания топологии исследуемого графа и весов, входящих в него дуг. Блок может содержать матрицу из пхп кодоуправляемых моделей дуг, что обеспечивает независимость функциональной схемы устройства от топол гии исследуемого графа. Узлы соединениь моделей дуг являются моделями вершин графа и соединены с входами 9, i

1,п блока, При поступлении сигнала уровня логической единицы на вход 9ь в матричной модели графа осуществляется определение кратчайших расстояний от i-й вершины до остальных вершин, Через время, пропорциональное кратчайшему расстоянию от i-й вершины до j-й появляется сигнал уровня логической единицы на полюсе 9> блока.

Блок 2 индикации предназначен для регистрации и индикации вершин, входящих в определяемую окрестность. Регистрация с последующей индикацией осуществляется по сигналам, поступающим на информационные входы блока. При поступлении сигнала на управляющий вход 13 дальнейшая работа блока прекращается, что исключает ложное отображение вершин, не входящих в окрестность заданного радиуса.

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

При поступлении сигнала на вход возврата в исходное преобразователь 3 возвращается в исходное состояние.

Устройство для определения параметров графа работает следующим образом. По входам 9;, i = 1,n, j = 1,п задаются веса дуг моделируемого графа, при этом, если ij-я дуга в исследуемом графе отсутствует, то по входу 9л записывается предельно допустимое большое значение, которое должно превышать диаметр дерева кратчайших расстояний графа. По входу 7 в дешифратор

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

55 входу 10 в преобразователь 3 вводится значение, пропорциональное заданному радиусу R, Работа устройства начинается подачей сигнала уровня логической единицы на вход запуска устройства 11, с которого он поступает на вход запуска времяинтегрирующего преобразователя 3 и на объединенные вторые входы элементов 5ь i = 1, п.

При этом, если, например, в качестве исходной вершины взята i-я, то сигнал с выхода элемента 5 поступает через разделительный диод 6 íà i-й информативный вход блока 2 индикации и вход 9i матричной модели

1 графа, В матричной модели 1 графа начинается процесс моделирования достижения вершин графа из его i-й вершины, а преобразователь 3 начинает формировать линейно-возрастающий сигнал (напряжение или код). По мере достижения j-x вершин графа, т.е, через время, пропорциональное величине кратчайшего расстояния из i-й вершины графа до j-й, появляются сигналы уровня логической единицы на соответствующих входах 91, откуда они поступают на информационные входы блока 2 индикации. Через время, пропорциональное значению радиуса, сигнал, сформированный в преобразователе 3 станет равным значению, введенному в его по входу 10 и на выходе времяинтегрирующего преобразователя появляется сигнал, свидетельствующий об окончании решения. Этот сигнал поступает на объединенные инверсные входы элементов 5ь i = 1, и, исключая дальнейшую работу модели 1 графа, и на управляющий вход 12 блока индикации, исключая ложное включение вершин в искомую окрестность, Вершины графа, вошедшие в окрестность

1-й вершины заданного радиуса R, однозначно зафиксированы в блоке индикации. Аналогичным образом устройство работает при определении окрестности любой другой вершины графа и при любом другом заданном значении радиуса, Таким образом, предлагаемое устройство обеспечивает за один цикл работы, деятельность которого зависит от величины заданного радиуса и не зависит от числа вершин исследуемого графа, определение окрестностей вершин графа заданного радиуса.

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

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

8 г 8

Ь!- ярк-.;-:"-.=. ь о,пель гра!1в!

-+ —

Г:! !

Составитель Н. Ячкула

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

Корректор Н. Ревская

Редактор Т. Иванова

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

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

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

Производственно-издательский комбинат "Патент", r. Ужгород, ул.Гагарина, 101 о т л и ч а ю щ е е с я тем, что, с целью повышения быстродействия устройства при определении окрестностей вершин графа заданного радиуса, в него введены времяинтегрирующий преобразователь, группа 5 элементов И и группа разделительных диодов, вход задания номера исходной вершин ы устройства соединен с входом дешифратора, а выходы дешифратора соединены с первыми входами элементов И 10 группы, вторые входы которых объединены и соединены с входами запуска устройства, а инверсные входы элементов И объединены и соединены с выходом признака достижения требуемого значения времяинтегрирущего преобразователя, который соединен с управляющим входом блока индикации, выходы элементов И группы соединены с катодами разделительных диодов, аноды которых соединены с входами матричной модели графа, а вход запуска времяинтегрирующего преобразователя соединен с входом запуска устройства, вход задания величины требуемого радиуса и вход возврата в исходное состояние времяинтегрирующего преобразователя подключены к соответствующим входам устройства.