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

ИЯ ПАс Ю СУДАРСТВЕННЫЙ НОМИТЕТ СССРДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ ОПИСАНИЕ К АВТОРСКОМУ СВИ(54) УСТРОЙСТВО ДЛЯ ОПРРАМЕТРОВ ГРАФА(57) Изобретение относится к области вычислительной техники и можетбыть использовано при решении задачна графах, например, для определенияокрестностей вершин графа заданногорадиуса. Цель изобретения - повыше ние точности. Цель достигается вве-дением в устройство группы элементов,. И и элемента ИЛИ. Устройство позво"ляет повысить точность при определении количества вершин графа, входящих в заданный радиус, т.к; при этоманализируются все пути, ведущие в исследуемую вершину. 3 ил.Изобретение относится к вычислительной технике и может быть использовано при решении задач на графах, например, для определения окрестностей вершин графа заданного радиуса.Цель изобретения - повышение точности.На Фиг.1 представлена функциональ. ная схема устройства; на фиг.2 - 10 Функциональная схема модели ветви графа; на фиг.3 - временная диаграмма работы устройства.Устройство для определения параметров графов содержит модель 1 гра Г фа, модель 2 ветви графа, регистр 3, блок 4 индикации, генератор 5 линейно-изменяющегося напряжения (ГЛИН), дешифратор 6, блок 7 сравнения, счет- чик 8, группу 9 - 9 ключей, блок 20 10 задания радиуса, группу 11 - 11 переключателей, элемент ИЛИ 12, группу 13, - 13 элементов И.Модель 1 графа состоит из моделей 2 ветвей графа, соединенных в соответствии с топологией исследуемого графа.Модель 2 ветви графа содержит два тиристорных ключа 14, два потенцио- метра 15, два ключевых диода 16, З 0 два токозадающих резистора 17, источник 18 напряжения и компаратор 19.В данном устройстве использован обычный матричный дешифратор 6.С выхода дешифратора потенциал "1" подается на, управляющий вход только того ключа; номер которого соответствует номеру вершины графа, для которой происходит в данный момент времени процесс определения в 0 заданный радиус. На все управляющие входы остальных ключей подается потенциал "0".Регистр 3 предназначен для запоминания вершин, вошедших в заданный ра диус. При определении окрестности вершин другого радиуса или для другой вершины предшествующая информацияЭ сбрасывается сигналом по входу сброса. 50Блок 4 индикации состоит из и светодиодов и предназначен для отображения вершин, вошедших в окрестность радиуса.Управляемый ГЛИН вырабатывает пилообразное напряжение У , максимальная величина которого пропорциональна заданному радиусу. ГЛИН 5 запускается сигналом по входу запуска, сброс и новый цикл начинаются сигналом по входу сброса. Работа ГЛИН 5 прекращается по входу запрета. На входахсброса и запрета ГЛИН 5 имеются элементы задержки входных сигналов, нап" ример КВ-цепочки. Время задержки выбирается такое, чтобы напряжение на выходе ГЛИН увеличилось от 0,95 11 до 11.В качестве элемента 7 сравнения использован, например, компаратор. Блок 10 задания радиуса - регулируемый источник постоянного напряжения, напряжение на выходе которогоустанавливается пропорциональным эаданному радиусу.Устройство для определения параметров графов работает следующим образом.Вершина графа, для которого опре."деляются окрестности вершин заданного радиуса, с помощью переключателя 11 подключается к шине нулевого потенциала, а на все остальные вершины поочередно с ГЛИН 5 подается напряжение, пропорциональное заданномурадиусу. Если вершина входит в заданный радиус, соответствующий потенциалподается на соответствующий вход регистра и происходит отображение наблоке индикации, что говорит о вхождении данной вершины в окрестностизаданного радиуса. ПерекоммутацияГЛИН 5 осуществляется автоматическипри достижении напряжением на еговыходе величины, пропорциональнойзаданному радиусу.В математическом плане задача заключается в том, что для любой вершины х графа С = (Х, Г), пусть К(х;) есть множество тех вершин х;графа С, которые достижимы из вершинх, с помощью путей с длинами Й (х,(х,),не превосходящими величины КК(х,) = 1 х Й(х;, х.) ( К,х еХ3Модель ветви графа работает следующим образом.На входные зажимы 1., 1 модели 2подается напряжение, изменяющееся от 0,95 Пдо 11 (где 11 - напряжение, пропорциональное заданному радиусу), при котором через любой ключевой диод 16 и токозадающий резистор 17 в зависимости от полярности приложенного напряжения начинает протекать ток1367019 000010 000010 2 3 000100 000011 20 0010000010000 000100 000101 30 35 40 45 50 55 1 (если приложенное напряжение 0 меньше веса ветви 11, ток через мо" дель ветви 2 не протекает). Этот ток создает на одном из двух токозадающих 5 резисторов 17 соответствующее падение напряжения, которое подается на первый вход компаратора 19. Компаратор 19 срабатывает и на его выходе появляется потенциал "1". Вес модели 1 О ветви 2 создается с помощью потенци 4 ометра 15. Если модели ветвей состав ляют определенный путь, то ток по этому пути начинает протекать только в случае, если 15мП) .Е: П где ш - количество моделей ветвей,вошедших в данный путь.Значение радиуса задается в блоке 1 О задания радиуса окрестности вершины графа, автоматизация процесса вершин для проверйи факта вхождения вершин в заданный радиус осуществляется с помощью ГЛИН 5, схемы 7 сравнения, дешифратора 6, счетчика 8 и аналоговых ключей 9 - 9. Определение нахождения вершины в заданном радиусе осуществляется моделями 2 ветвей графа, регистром 3, ГЛИН 5, блоком 10 задания радиуса и отобра;жается в блоке 4 индикации.В исходном состоянии из моделей 2 ветвей графа составляется граф с заданными связями. На моделях 2 ветвей с помощью потенциометров 15 устанавливаются их веса, на блоке 10 задания радиуса устанавливается заданный радиус. Вершина, для которой определяется окрестность вершин заданного радиуса, заземляется с помощью переключателя 11.Работа устройства начинается с момента поступления сигнала на вход запуска устройства. ГЛИН 5 начинает вырабатывать линейно изменяющееся напряжение (фиг.За, ,), которое поступает на вход схемы 7 сравнения и на управляющие входы ключей 9, - 9,. кото 1 ые закрыты, так как на всех вы-, ходах дешифратора 6 нулевые потенциалы. При достижении напряжением на выходе ГЛИН 5 значения 0,95 от напряжения, пропорционального заданному радиусу окрестности У, срабатывает . схема 7 сравнения, так как на его первом и втором входах напряжение одинаково. На выходе схемы 7 сравнения (фиг.Зб, Т ) появляется напряжение "1", которое поступает на вход сброса ГЛИН 5 и на информационный вход счетчика 8. С выхода счетчика 8 кодовая комбинация поступает на вход дешифратора 6, и на выходе его перво 11 1 го разряда появляется потенциал 1 разрешающий прохождение напряжения с выхода ГЛИН 5 на первую вершину графа . Это поясняется таблицей в з аимных состояний счетчика 8 и дешифратора 6 .Счетчик Вершины Дешифратор 000001 1 000001 На входе сброса ГЛИН 5 стоит элемент задержки, поэтому сброс напряжения на его выходе происходит через время Ве = Т-(фиг.З 6), а напряжение на его выходе в моментдостигает значения У.В момент е начинается формирование второго цикла пилообразного напряжения, В момент, когда это напряжение достигает значения 0,95 У срабатывает блок 7 сравнения, на ее выходе появляется потенциал "1", который поступает на информационный вход счетчика 8 и вход сброса ГЛИН 5, В результате на втором выходе дешифратора 6 появляется напряжение, которое открывает второй аналоговый ключ 9, и напряжение с ГЛИН 5 поступает на вторую вершину графа (фиг.Зг), Если напряжение У 1 П, то с компаратора 19 напряжение "1" подается на второй вход элемента ИЛИ 12 и через И 131 (так как на первый вход И 131. подается напряжение с второго выхода дешифратора 6) на второй выход регистра 3 И, на второй индикаторблока индикации 4. Второй светодиодзасветится, отображая тот факт, чтовершина два вошла в заданный радиус. 1 Если Г (11, то с компаратора 19 сни мается нулевой потенциал и второй индикатор не засветится.513670Аналогичным образом устройство работает до и"цикла пилообразного нап,ряжения, вырабатываемого ГЛИН 5. Когда напряжение п-го цикла пилообразного напряжения достигает значения 0,95 0, с и-го выхода дешифратора 6 на вход запрета ГЛИН 5 подается сигнал запрета, который запрещает дальнейшее генерирование пилообразных 1 О сигналов после достижения на. выходе ГЛИН 5 налряжения равного 0.На блок 4 индикации светятся светодиоды, отображающие какие вершины вошли в заданный радиус для выбран б ной вершины.Для определения вершин, входящих в заданный радиус (для следующей вершины), необходимо установить новое исходное состояние и очистить разря." ды дешифратора 6 и регистра 3 сигналом по шине сброса устройства.Формула изобретения25Устройство для определения параметров графа, содержащее модель графа, группу ключей, счетчик, дешифратор, блок сравнения, генератор линей- но-изменяющегося напряжения, регистр, Зо 19 6блок индикации, блок задания радиуса,выход которого соединен с первым входом блока сравнения, выход которогоподключен к входу останова генератора линейно изменяющегося напряжения.и к счетному входу счетчика, выходкоторого соединен с входом дешифратора, выходы которого подключены к управляющим входам ключей группы и квходу запуска генератора линейно-изменяющегося напряжения, выход которого соединен с вторым входом блокасравнения и с информационными входами ключей группы, выход которого подключен к входам моделей вершин, графа, вход сброса счетчика являетсявходом сброса устройства и соединенс входом сброса регистра, выходы которого подключены к входам блока индикации, о т л и ч а ю щ е е с ятем, что, с целью повышения точности,в него введены группа элементов И иэлемент ИЛИ, входы которого соединены с выходами моделей вершин, выходэлемента ИЛИ подключен к первым входам элементов И группы, вторые входыкоторых соединены с выходами дешифратора, выходы элементов И подключенык входам регистра.