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

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

Цель изобретения - повышение быстродействия устройства при линии окрестностей вершин графа заданного радиуса.

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

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

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

СП

С

00

N

ю

0

О

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

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

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

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

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

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

ной вершины взята i-я, то сигнал с выхода

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

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

0 времяинтегрирующего преобразователя появляется сигнал, свидетельствующий об окончании решения. Этот сигнал поступает на объединенные инверсные входы элементов 5i, i 1, n, исключая дальнейшую

5 работу модели 1 графа, и на управляющий вход 12 блока индикации, исключая ложное включение вершин в искомую окрестность. Вершины графа, вошедшие в окрестность i-й вершины заданного радиуса R, однознач0 но зафиксированы в блоке индикации. Аналогичным образом устройство работает при определении окрестности любой другой вершины графа и при любом другом заданном значении радиуса.

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

0 окрестностей вершин графа заданного радиуса.

Формула изобретения Устройство для определения параметров графа, содержащее матричную модель

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

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

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

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