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

;БЫ ПИСАН ИЗОБ ТЕНИ КОМУ ЕТЕЛЬС В ла И люсами делями ые сое ми бло- С)Ь альная ,( ) ГОСУДАРСТВЕННОЕ ПАТЕНТНОВЕДОМСТВО СССР(56) Авторское свидетельство СССРМ 1392574, кл, 6 06 Е 15/20, 1988.Авторское свидетельство СССРМ 1251097, кл. 6 06 Р 15/20, 1984.(54) УСТРОЙСТВО ДЛЯ ОПРЕДЕЛПАРАМЕТРОВ ГРАФА Изобретение относится к области вычислительной техники и может быть использовано при решении задач на графах, например, для определения окрестностей вершин графа заданного радиуса,Цель изобретения - повышение быстродействия устройства при линии окрестностей вершин графа заданного радиуса.Сущность изобретения заключается в том, что в устройство, содержащее матричную модель графа, блок индикации и дешифратор, введены группа элементов И, разделительные диоды и времяинтегрирующий и реобразовател ь. При этом вход дешифратора соединен с входом задания номера вершины, окрестность которой будет определяться в процессе работы устройства, а выходы соединены с первыми входами соответствующих элементов И группы, вторые входы которых обьединены с входом запуска времяинтегрирующего преобразователя и соединены с входом запуска устройства, а инверсные входы эле 182904 О А 1(57) Изобретение относится к вычислительной технике и может быть использовано при решении на графах задачи определения окрестностей вершин графа заданного радиуса. Цель изобретения - повышение быстродействия устройства при определении окрестностей вершин графа заданного радиуса, Устройство содержит матричную модель графа, блок индикации, дешифратор, времяинтегрирующий преобразователь. группу элементов И и группу разделительных диодов, 1 ил. нтов И группы объединены с управляющим входом блока индикации и соединены с выходом признака достижения требуемого значения времяинтегрирующего преобразователя. Выходы элементов И группы соединены с катодами разделительных диодов, аноды которых соединены с по модели графа, соединенными с мо вершин исследуемого графа, котор динены и с информационными входа ка и нди ка ци и.На чертеже приведена функцион схема устройства,Устройство содержит матричную модель графа 1, блок индикации 2, времяинтегрирующий преобразователь 3, ф дешифратор 4, элементы И 5 ь разделительные диоды б ( = 1, п, и - число вершин исследуемого графа), Кроме того, цифровые обозначения на схеме имеют: вход 7 задания номера исходной вершины (т.е. вершины, для которой определяется окрестность); входы 8;,= 1, и, ) = 1, п,Ф) задания весадуг исследуемого графа; полюса 9 ь= 1, и, соединенные с моделями вершин исследуемого графа; вход 10 задания величины требуемого радиуса; вход 11 запуска устройства; вход 12 возврата времяинтегрирующего преобразователя в исходное состояние; управляющий вход 13 блока индикации,Модель графа 1 предназначена для задания топологии исследуемого графа и весов, входящих в него дуг. Блок может содержать матрицу из пхп кодоуправляемых моделей дуг, что обеспечивает независимость функциональной схемы устройства от топологии исследуемого графа. Узлы соединениь моделей дуг являются моделями вершин графа и соединены с входами 9, 1= 1,п блока, При поступлении сигнала уровня логической единицы на вход 9 ь в матричной модели графа осуществляется определение кратчайших расстояний от -й вершины до остальных вершин, Через время, пропорциональное кратчайшему расстоянию от -й вершины до )-й появляется сигнал уровня логической единицы на полюсе 9 блока.Блок 2 индикации предназначен для регистрации и индикации вершин, входящих в определяемую окрестность, Регистрация с последующей индикацией осуществляется по сигналам, поступающим на информационные входы блока. При поступлении сигнала на управляющий вход 13 дальнейшая работа блока прекращается, что исключает ложное отображение вершин, не входящих в окрестность заданного радиуса.Времяинтегрирующий преобразователь 3 предназначен для формирования по сигналу, поступающему на его вход запуска, линейно-возрастающего сигнала (напряжения или кода), сравнения его со значением, заданным по входу 10 и формирования сигнала уровня логической единицы на выходе признака достижения требуемого значения. При поступлении сигнала на вход возврата в исходное преобразователь 3 возвращается в исходное состояние.Устройство для определения параметров графа работает следующим образом. По входам 9;, = 1,п, ) = 1,п задаются веса дуг моделируемого графа, при этом, если ц-я дуга в исследуемом графе отсутствует, то по входу 9 л записывается предельно допустимое большое значение, которое должно превышать диаметр дерева кратчайших расстояний графа. По входу 7 в дешифратор 4 вводится код номера вершины, окрестность которой будет определяться в процессе работы устройства. При этом появляется сигнал уровня логической единицы на соответствующем выходе дешифратора 4. По 10 15 20 25 30 35 40 45 50 55 входу 10 в преобразователь 3 вводится значение, пропорциональное заданному радиусу В, Работа устройства начинается подачей сигнала уровня логической единицы на вход запуска устройства 11, с которого он поступает на вход запуска времяинтегрирующего преобразователя 3 и на объединенные вторые входы элементов 5 ь = 1, п. При этом, если, например, в качестве исходной вершины взята 1-я, то сигнал с выхода элемента 5 поступает через разделительный диод 6 на 1-й информативный вход блока 2 индикации и вход 9 матричной модели 1 графа, В матричной модели 1 графа начинается процесс моделирования достижения вершин графа из его -й вершины, а преобразователь 3 начинает формировать линейно-возрастающий сигнал (напряжение или код). По мере достижения )-х вершин графа, т.е, через время, пропорциональное величине кратчайшего расстояния из -й вершины графа до )-й, появляются сигналы уровня логической единицы на соответствующих входах 91, откуда они поступают на информационные входы блока 2 индикации. Через время, пропорциональное значению радиуса, сигнал, сформированный в преобразователе 3 станет равным значению, введенному в его по входу 10 и на выходе времяинтегрирующего преобразователя появляется сигнал, свидетельствующий об окончании решения, Этот сигнал поступает на объединенные инверсные входы эле. ментов 5 ь= 1, и, исключая дальнейшую работу модели 1 графа, и на управляющий вход 12 блока индикации, исключая ложное включение вершин в искомую окрестность, Вершины графа, вошедшие в окрестность 1-й вершины заданного радиуса В, однозначно зафиксированы в блоке индикации. Аналогичным образом устройство работает при определении окрестности любой другой вершины графа и при любом другом заданном значении радиуса,Таким образом, предлагаемое устройство обеспечивает за один цикл работы, деятельность которого зависит от величины заданного радиуса и не зависит от числа вершин исследуемого графа, определение окрестностей вершин графа заданного радиуса,Формула изобретения Устройство для определения параметров графа, содержащее матричную модель графа из пхп моделей дуг, узлы соединения которых моделируют вершины графа, соединенные с входами матричной модели графа, дешифратор и блок индикации, информационные входы которого соединены с входами матричной модели графа,9 9 УГУо Составитель Н. Ячкуладактор Т. Иванова Техред М.Моргентал Корректо евска каз 2476 ВНИИП Тираж Подписное осударственного комитета по изобретениям и открытиям при ГКНТ СС 113035. Москва, Ж, Раушская наб., 4/5Производственно-издательский комбинат "Патент", г. Ужгород, ул.Гагарина, 101 о т л и ч а ю щ е е с я тем, что, с целью повышения быстродействия устройства при определении окрестностей вершин графа заданного радиуса, в него введены время- интегрирующий преобразователь, группа 5 элементов И и группа разделительных диодов, вход задания номера исходной вершин ы устройства соединен с входом дешифратора, а выходы дешифратора соединены с первыми входами элементов И 10 группы, вторые входы которых объединены и соединены с входами запуска устройства, а инверсные входы элементов И объединены и соединены с выходом признака достижения требуемого значения времяинтегрирущего преобразователя, который соединен с управляющим входом блока индикации, выходы элементов И группы соединены с катодами разделительных диодов, аноды которых соединены с входами матричной модели графа, а вход запуска времяинтегрирующего преобразователя соединен с входом запуска устройства, вход задания величины требуемого радиуса и вход возврата в исходное состояние времяинтегрирующего преобразователя подключены к соответствующим входам устройства.