Устройство для определения параметров графов Советский патент 1986 года по МПК G06G7/122 

.

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

Целью изобретения является упрощение устройства для определения параметров графов.

На фиг.1 представлена функциональная схема устройства для определения параметров графов; на фиг,2 - функциональная схема модели ветви графа; на фиг.З - временная диаграмма работы устройства.

Устройство для определения параметров графов содержит модель i графа, модель 2 ветви графа, п-разряд- ньм регистр 3, блок 4 индикации, генератор 5 линейно изменяющегося напряжения (глин), дешифратор 6, схему 7 сравнения, счетчик выключи 9(- 9, блок 10 задания радиуса окрестности вершины графа, группу переключателей 11,-11.

Модель 1 состоит из моделей 2 ветвей графа, соединенных в соответствии с топологией исследуемого графа.

Модель 2 ветви графа содержит два тиристорных ключа 12, два потенциометра 13, два ключевых диода 14, два токозадающих резистора. 15; источник 16 напряжения и компаратор 17.

В данном устройстве использован обычный матричный дешифратор 6.

С выхода дешифратора потенциал 1 подается на управляющий вход только того ключа, номер которого соответствует номеру вершины графа, для которой происходит в данньй момент времени процесс определения в .заданный радиус. На все управляющие входы остальных ключей подается потенциал О.

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

Блок 4 индикации состоит из п све тодиодов и предназначен для отображения вершин, вошедших в окрестность заданного радиуса.

Управляемый ГЛИН вырабатывает пилообразное напряжение U,, , максимальная величина которого пропсрцио510972

нальна заданному радиусу. ГЛИН 5 запускается сигналом по входу запуска; сброс и новый цикл начинаются сигналом по входу сброса. Работа

5 ГЛИН 5 прекращается по входу запрета. На входах сброса и зашрета ГЛИН 5 имеются элементы задержки входных сигналов, например КС-цепочки. Время задержки выбирается такое,

fO -чтобы напряжение на выходе ГЛИН увеличилось от 0,95 Ujj до Ujj.

В качестве элемента 7 сравнения использован, например, компаратор. Блок 10 задания радиуса - регули 5 руемый источник постоянного напряжения, напряжение на выходе которого устанавливается пропорциональным заданному радиусу.

Устройство для определения парамет20 ров графов работает следующим образом.

Вершина графа, для которого определяются окрестности вершин заданного радиуса, с помоицзю переключателя 11 подключается к шине нулево25 го потенциала, а на все остальные вершины поочередно с ГЛИН 5 подается напряжение, пропорциональное заданно- му радиусу. Если вершина входит в за- данньш радиус, соответствующий потен30 циал по; ается на соответствующий вход регистра и происходит отображение на блоке индикации, что говорит о вхождении данной вершины в окрестности заданного радиуса. Перекомму2J тация ГЛИН 5 осуществляется автоматически при достижении напряжением на его выходе величины, пропорциональной заданному радиусу.

В математическом плане задача за40 ключается в том, что для любой вершины х; графа G (X, Г) пусть R(j (х,) есть множество тех вершин х: графа G, которые достижимы из вершин X; с помощью путей с длинами d (х;,

45 Xj) ие превосходящими величины R

R° (х;) xj /d(x;,x. )R,

xj е X.

Модель ветви графа работает следу5 ющим образом.

На входные зажимы i, j модели 2 подается напряжение, изменяющееся от 0,95 U( до и (где U - напряжение, пропорциональное заданному ра55 диусу), при котором через любой ключевой диод 14 и токозадающий резистор 15 в зависимости от полярности приложенного напряжения начинает протекать ток 1ц (если приложенное напряжение U(; меньше веса ветви Ч, ток через модель ветви 2 не протекает) . Этот ток создает на одном из двух токозадающих резисторов 15 со- ответствующее падение напряжения, которое подается на первый вход ком- парат ра 17. Компаратор 17 срабатывает и на его выходе появляется потенциал I. Вес модели ветви 2 соз- дается с помощью потенциометра 13. Если модели ветвей составляют определенной путь, то ток-по этому пути начинает протекать только в случае,

tTi

если и„ 51 и„- , где m - количество

R f- п 1 1

моделей ветвей, вошедших в данный путь,

Значение радиуса задается в блоке 10 задания радиуса окрестности вершины графа, автоматизация процесса вершин для проверки факта вхождения вершин в заданный радиус осуществляется с помощью ГЛИН 5, схемы 7 сравнения, дешифратора 6, счетчи- ка 8 и аналоговых ключей 9;-9,. Определение нахождения вершины в заданном радиусе осуществляется моделями 2 ветвей графа, регистром 3, ГЛИН 5, блоком 10 задания радиуса и отоб- ражается в блоке 4 индикации.

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

Работа устройства начинается с. момента поступления сигнала на вход запуска устройства. ГЛИН 5 начинает вырабатывать линейно изменяющееся напряжение (фиг.За, t), которое поступает на вход схемы 7 сравнения и на управляющие входы ключей которые закрыты, так как на всех выходах дешифратора 6 - нулевые потен- циалы. При достижении напряжением на выходе ГЛИН 5 значения 0,95 от напряжения, пропорционального заданному радиусу окрестности Uj, срабатывает схема 7 сравнения, так как на его первом и втором входах напряжение одинаково. На выходе схемы 7 сравнения (фиг.Зб, t3) появляется

.напряжение I, которое поступает на вход сброса ГЛИН 5 и на информационный вход счетчика 8. С выхода счетчика 8 кодовая комбинация поступает на вход дешифратора на выходе его первого разряда появляется потенциал 1, разрешающий прохождение напряжения с выхода ГЛИН 5 на первую вершину графа. Это поясняется таблицей взаимных состояний счетчика 8 и дешифратора 6:

Счетчик Вершины Дешифратор

00.,

00.

00.

00.

00.

.000 .0010 .ООП .0100 .0101

1 2 3 4 5

00.,

00.

00.

00.

00.

.0001 .0010 .0100 .1000 .10000

На входе сброса ГЛИН 5 стоит элемент задержки, поэтому сброс напряжения на его выходе происходит через время ь t t4 - tj (фиг.Зб), а напряжение на его выходе в момент t4 достигает значения и,.

В момент t начинается формирование второго цикла пилообразного напряжения. В момент, когда это напряжение достигает значения 0,95Ufj, срабатывает схема 7 сравнения, на ее выходе появляется потенциал I, который поступает на информационный вход счетчика 8 и вход сброса ГЛИН 5. В результате на втором выходе дешифратора 6 появляется напряжение, которое открывает второй аналоговый ключ 92, и напряжение с ГЛИН 5 поступает на вторую вершину графа (фиг.Зг) . Если напряжение UR U, то с компаратора 17 напряжение 1 подается на второй вход регистра 3 и с второго выхода регистра 3 - на второй индикатор блока 4 индикации. Второй светодиод светится, отображая тот вторая вершина вошла в заданный радиус. Если U, то с компаратора 17 снимается нулевой потенциал и второй индикатор не све- тится..

Аналогичным образом устройство работает до п-го цикла пилообразного напряжения, вырабатываемого ГЛИН 5. Когда напряжение н-го цикла пилообразного напряжения достигает значения 0,95 и(J, с п-го выхода дешифратора 6 на вход запрета ГЛИН 3 подается сигнал запрета, который запрещает дальнейшее генерирование пилообразных сигналов после достижения на выходе ГЛИН 5 напряжения U.

На блоке 4 индикации светятся све тодиоды, отображающие, какие вершины вошли в заданный радиус для выбранной вершины.

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

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

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

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

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

MS

7 rs

l k54cH

rS 1

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

Составитель Т.Сапунова Редактор И.Рыбченко Техред М.Ходанич Корректор Л.Пилипенк о

Заказ 4413/47 Тираж 671Подписное

ВНИИПИ Государственного комитета СССР

по делам изобретений и открытий 113035, Москва, Ж-35, Раушская наб., д. 4/5

Производственно-полиграфическое предприятие, г.Ужгород, ул.Проектная,4