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

) ГОСУДАРСТВЕННЫЙ НОМИТЕТ СССРПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ(54) УСТРО 11 СТВО ДЛЯ ОП ДЕМЕТРОВ ГРАФОВ(57) Изобретение относится к областивычислительной техники и может бытьиспользовано при решении задач на .графах, например для определения окрестностей вершин графа заданногорадиуса. Изобретение позволяет упростить устройство, Устройство содержитмодель 1 графа, которая состоит измоделей 2 ветвей графа, соединенныхв соответствии с топологией исследуемого графа, и-разрядный регистр 3,(п - количество вершин графа), блок4 индикации, генератор 5 линейно изменяющегося напряжения, дешифратор 6,схему 7 сравнения, счетчик 8, ключи9,-9 , блок 10 задания радиуса, группу переключателей 11-11),. Модель 2ветви графа содержит два тиристорныхключа, два потенциометрацва ключевых диода) два токозадающих резистора, источник напряжения и компаратор. 1 з.п.ф-лы, 3 ил.251097 2нальна заданному радиусу, ГЛИН 5 запускается сигналом по входу запуска; сброс и новый цикл начинаютсясигналом по входу сброса. Работа5 ГЛИН 5 прекращается по входу запрета. На входах сброса и запретаГЛИН 5 имеются элементы задержкивходных сигналов, например КС-цепочки, Время задержки выбирается такое, 1 О чтобы напряжение на выходе ГЛИН увеличилось от 0,95 П до Б.В качестве элемента 7 сравненияиспользован, например, компаратор.Блок 10 задания радиуса - регули руемый источник постоянного напряжения, напряжение на выходе которогоустанавливается пропорциональным заданному радиусу.Устройство для определения парамет ров графов работает следующим образом.Вершина графа, для которого определяются окрестности вершин заданного радиуса, с помощью переключателя 11 подключается к шине нулевого потенциала, а на все остальныевершины поочередно с ГЛИН 5 подаетсянапряжение, пропорциональное заданному радиусу. Если вершина входит в заданный радиус, соответствующий потен- ЗО циал подается на соответствующий входрегистра и происходит отображениена блоке индикации, что говорит овхождении данной вершины в окрестности заданного радиуса, Перекоммутация 1"ЛИН 5 осуществляется автоматически при достккении напряжениемна его выходе величины, пропорциональной заданному радиусу.В математическом плане задача заключается в том, что для любой вершины х, графа С = (Х, Г) пустьК (х ) есть множество тех вершин х1 ,1графа С, которые достижимы из вершинх; с помощью путей с длинами Й(х;,х ), не превосходящими величины К Изобретение относится к вычислительной технике и может быть использовано при решениях задач на графах,например, для определения окрестностей вершин графа заданного радиуса.Целью изобретения является упрощение устройства для определенияпараметров графов.На фиг.1 представлена Функциональная схема устройства для определения параметров графов; на Фиг,2 -функциональная схема модели ветвиграфа; на фиг.3 - временная диаграмма работы устройства.Устройство для определения параметров графов содержит модель 1 граФа, модель 2 ветви графа, и-разрядный регистр 3, блок 4 индикации, генератор 5 линейно изменяющегося напряжения (ГЛИН), дешифратор 6, схему 7 сравнения, счетчик 8,ключи 9 -9 , блок 1 О заданйя радиуса окрестности вершины графа, группу переклю"чателей 11, -11.Модель 1 графа состоит из моделей 2 ветвей графа, соединенных в соответствии с топологией исследуемогографа.Модель 2 ветви графа содержит дватиристорных ключа 12, два потенциометра 13, два ключевых диода 14,два токозадающих резистора. 15, источник 16 напряжения и компаратор 17,В данном устройстве использованобычный матричный дешифратор 6,С выхода дешифратора потенциал"1" подается на управляющий входтолько того ключа, номер которогосоответствует номеру вершины графа,для которой происходит в данный момент времени процесс определения в,заданный радиус. На все управляющиевходы остальных ключей подается потенциал 0.Регистр 3 предназначен для запоминания вершин, вошедших в заданныйрадиус. При определении окрестностивершин другого радиуса или для другой вершины предшествующая информация сбрасывается сигналом по входусброса,Блок 4 индикации состоит из 6 светодиодов и предназначен для отображения вершин, вошедших в окрестность заданного радиуса.Управляемый ГЛИН вырабатываетпилообразное напряжение 11, максимальная величина которого пропсрциоБ., (х )= х/Й(хх,) ( К,хе; Х. Модель ветви графа работает следующим образом.На входные зажимы , 1 модели 2 подается напряжение, изменяющееся от 0,95 11 до 11 я (где 11 - напряжение, пропорциональное заданному радиусу), при котором через любой ключевой диод 14 и токозадающий резистор 15 в зависимости от полярности приложенного напряжения начинает про з 125текать ток 1 (если приложенное напряжение Б меньше "веса" ветви 1,ток через модель ветви 2 не протекает). Зтот ток создает на одном издвух токозадающих резисторов 15 соответствующее падение напряжения,которое подается на первый вход компарат ра 17. Компаратор 17 срабатывает и на его выходе появляется потенциал "1". "Вес" модели ветви 2 соэ- Одается с помощью потенциометра 13,Если модели ветвей составляют определенной путь, то ток по этому путиначинает протекать только в случае,5если У 2 . Б;, где ш - количество11моделей ветвей, вошедших в данныйпуть.Значение радиуса задается в блоке 10 задания радиуса окрестности 20вершины графа, автоматизация процесса вершин для проверки факта вхождения вершин в заданный радиус осуществляется с помощью ГЛИН 5, схемы7 сравнения, дешифратора 6, счетчика 8 и аналоговых ключей 9;-9. Определение нахождения вершины в задан -ном радиусе осуществляется моделями 2 ветвей графа, регистром 3, ГЛИН5, блоком 10 задания радиусаи отоб- Оражается в блоке 4 индикации,В исходном состоянии из моделей2 ветвей графа составляется граф сзаданными связями. На моделях 2 ветвей с помощью потенциометров 13 уста-Знавливаются их "веса", на блоке 10задания радиуса устанавливается заданный радиус. Вершина, для которой определяется окрестность вершин заданного радиуса, заземляетсяс помоп;ью переключателя 11. Работа устройства начинается с, момента поступления сигнала на вход. запуска устройства. ГЛИН 5 начинает вырабатывать линейно изменяющееся напряжение (фиг,За, С) 1 которое поступает на вход схемы 7 сравнения и на управляющие входы ключей 9-9, которые закрыты, так как на всех выходах дешифратора 6 - нулевые потен О циалы. При достижении напряжением на выходе ГЛИН 5 значения 0,95 от напряжения, пропорционального заданному радиусу окрестности Б 1 срабатывает схема 7 сравнения, так как на его первом и втором входах напряжение одинаково. На выходе схемы 7 сравнения (фиг.Зб, йз) появляется097 4 напряжение л . которое поступает на вход сброса ГЛИН 5 и на информационный вход счетчика 8. С выхода счетчика 8 кодовая комбинация поступает на вход дешифратора б,и на выходе его первого разряда появляется потен 11 11циал 1 , разрешающий прохождение напряжения с выхода ГЛИН 5 на первую вершину графа . Э то поясняется таблицей взаимных состояний счетчика 8 и дешифр ато ра б: Счетчик Вершины Дешифратор 1 2 3 5 000001 000010 000011 000100 000101 00 . . . 0 0 0 1 0 0 . . . 00 1 0 00. 0 1 00 0 0 . . . 1 00 0 0 0 . . . 1 000 0 На входе сброса ГЛИН 5 стоит элемент задержки, поэтому сброс напряжения на его выходе происходит через время ь Т = С - С (фиг.Зб), анапряжение на его выходе в моментдостигает значенияВ момент Т начинается формирование второго цикла пилообразного напряжения. В момент, когда это напряжение достигает значения 0,95 Б 1срабатывает схема 7 сравнения, наее выходе появляется потенциал 1который поступает на информационныйвход счетчика 8 и вход сброса ГЛИН5. В результате на втором выходе дешифратора 6 появляется напряжение,которое открывает второй аналоговыйключ 92 1 и напряжение с ГЛИН 5 поступает на вторую вершину графа(Фиг.Зг). Если напряжение УПто с компаратора 17 напряжение "1"подается на второй вход регистра 3и с второго выхода регистра 3 - навторой индикатор блока 4 индикации,Второй светодиод светится, отображаятот факт что вторая вершина вошла взаданный радиус. Если Б с Б 1 тос компара.тора 17 снимается нулевойпотенциал и второй индикатор не светится,Аналогичным образом устройство работает до и -го цикла пилообразного напряжения, вырабатываемого ГЛИН 5. Когда напряжение 1 -го цикла пилообразного напряжения достигает значения 0,95 01 с и-го выхода дешифратора б на вход запрета ГЛИ 5 пода 1251097ется сигнал запрета, который запрещает дальнейшее генерирование пилообразных сигналов после достижения на выходе ГЛИН 5 напряжения 11.На блоке 4 индикации светятся светодиоды, отображающие, какие вершины вошли в заданный радиус для выбранной вершины,10Для определения вершин, входящих в заданный радиус (для следующей вершины), необходимо установить новое исходное состояние и очистить разряды дешифратора 6 и регистра 3 сигналом по шине сброса устройства.формула и з о б р е т е н и я1. Устройство для определения параметров графов, содержащее и-разрядный регистр (где и - число вершин графа), блок индикации, счетчик, дешифратор и модель графа., о т л и- чающее с я тем, что, с целью д упрощения устройства, в него введены группа переключателей, генератор линейно изменяющегося напряжения, группа ключей, схема сравнения и блок задания радиуса окрестности вер-ЗО шины графа, причем модель графа состоит иэ моделей ветвей графа, соединенных в соответствии с топологией исследуемого графа, выходы моделей ветвей графа модели графа подключены к группе информационных входов п-разрядного регистра, группа выходов которого подключена к группе входов блока индикации, входы моделей ветвей графа модели графа подключены к группе выходов коммутатора, каждый информационный вход из группы входов которого подключен к выходу соответствующего ключа группы, управляющие входы всех ключей группы объединены и подключены к выходу генератора линейно изменяющегося напряжения и к первому входу схемы сравнения, второй вход которой подключен к выходу блока задания радиуса окрестности вершины графа, выход схемы сравнения подключен к входу сброса генератора линейно изменяющегося на"пряжения и к информационному входусчетчика, вход сброса которого объединен с входом сброса п-разрядногорегистра и является входом сбросаустройства, выход счетчика подключенк входу дешифратора, выходы разрядовкоторого подключены соответственнок информационным входам ключейгруппы, выходы моделей ветвей граФа модели графа через соответствующие переключатели группы переключателей подключены к шине нулевого потенциала и к выходам соответствующихключей группы, вход запрета генератора линейно изменяющегося напряжения подключен к выходу и-го разряда дешифратора, а вход запуска генератора линейно изменяющегося напряжения является входом запуска устройства,2. Устройство по п, 1, о т л и -ч а ю щ е е с я тем, что модель ветви графа содержит два тиристорныхключа, два потенциометра, два токозадающих резистора, два ключевых диода, источник напряжения и компараторпервый выход источника напряжения,первые выводы потенциометров, выходы тиристорных ключей и первые выводы токоэадающих резисторов объединены и подключены к первому входу компаратора, второй вход которого подключен к шине нулевого потенциала,а выход компаратора является выходом модели ветви графа, второй выходисточника напряжения подключен к вторым выводам потенциометров, подвижный контакт каждого потенциометра .подключен к управляющему входу соответствующего тиристорного ключа, информационные входы тиристорных ключей являются входами модели ветвиграфа и через соответствующие ключевые диоды подключены к второмувыводу соответствующего токоэадающего резистора..1251097 нова орректо ктор И.Рыбчен илипенко Тираж 67 дписно 113 Производственно-полиграфическое предприятие, г.ужгород, ул.Проектная,4 аз 4413/4ВН оставитель Т. ехред М.Ходаи о комитета ССС и открытийРаушская наб. осударственногам изобретенийМосква, Ж,