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

 

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

(19) (Н) (51) 4 G 06 F 15/20 ф ,,1 (:Я т СОЮЗ СОВЕТСНИХ & "--=., СОЦИАЛИСТИЧЕСНИХ

,) РЕСПУБЛИН

) ГОСУДАРСТВЕННЫЙ НОМИТЕТ СССР

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИЙ (21) 3827576/24-24 (22) 19.12.84 (46) 15.08.86. Бюл. ¹ 30 (72) Е.И.Бороденко, В.Е.Назаренко, В.Д.Степанов, Б.И.Нагорнов и С.Г.Семененко (53) 681.. 333 (088. 8) (56) Авторское свидетельство СССР № 842842, кл. G 06 С 7/122, 1981.

Авторское свидетельство СССР

¹ 991434, кл. G 06 G 15/20, 1983. (54) УСТРО11СТВО ДЛЯ ОПРЕДЕЛЕНИЯ ПАРАМЕТРОВ ГРАФОВ (57) Изобретение относится к области вычислительной техники и может быть использовано при решении задач на . графах, например для определения окрестностей вершин графа заданного радиуса. Изобретение позволяет упростить устройство. Устройство содержит модель 1 графа, которая состоит из моделей 2 ветвей графа, соединенных в соответствии с топологией исследуемого графа, и-разрядный регистр 3, (и — количество вершин графа), блок

4 индикации, генератор 5 линейно изменяющегося напряжения, дешифратор 6, схему 7 сравнения, счетчик 8, ключи

9,-9, блок 10 задания радиуса, группу переключателей !11-11 . Модель 2 ветви графа содержит два тиристорных ключа, два потенциометра,,цва ключе— вых диода) два токозадающих резис- р тора, источник напряжения и компаратор. 1 з.п.ф-лы, 3 ил.

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

ГЛИН 5 прекращается по входу запрета. На входах сброса и запрета

ГЛИН 5 имеются элементы задержки входных сигналов, например RC-цепочки, Время задержки выбирается такое, чтобы напряжение на выходе ГЛИН увеличилось от 0,95 П!! до UR.

В качестве элемента 7 сравнения использован, например, компаратор.

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

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

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

В математическом плане задача заключается в том, что для любой вершины х, графа G = (X, Г) пусть

К (х ) есть множество тех вершин х

1,! графа G„которые достижимы из вершин х; с помощью путей с длинами d(x х ), не превосходящими величины R

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

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

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

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

9, блок 10 задания радиуса окрестности вершины графа, группу переключателей 11< -11„. !

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

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

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

С выхода дешифратора потенциал

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

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

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

Управляемый ГЛИН вырабатывает пилообразное напряжение U< максимальная величина которого пропсрциоБ., (х ) = (х„ /d (х., х, ) ) cК, х„g Х.

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

На входные зажимы i, j модели 2 подается напряжение, изменяющееся от 0,95 U< до U< (где U — напряжение, пропорциональное заданному радиусу), при котором через любой ключевой диод 14 и токозадающий резистор 15 в зависимости от полярности приложенного напряжения начинает проз 125 текать ток I (если приложенное напряжение Б!! меньше "веса" ветви 11„, ток через модель ветви 2 не протекает). Зтот ток создает на одном из двух токозадающих резисторов 15 соответствующее падение напряжения, которое подается на первый вход компарат ра 17. Компаратор 17 срабатывает и на его выходе появляется потенциал "1". "Вес" модели ветви 2 соэ- !0 дается с помощью потенциометра 13.

Если модели ветвей составляют определенной путь, то ток-по этому пути начинает протекать только в случае, !

5 если У„> 5 Б„,, где m — количество

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

Значение радиуса задается в блоке 10 задания радиуса окрестности 20 вершины графа, автоматизация процесса вершин для проверки факта вхождения вершин в заданный радиус осуществляется с помощью ГЛИН 5, схемы

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

5, блоком 10 задания радиуса и отображается в блоке 4 индикации.

В исходном состоянии из моделей

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

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

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

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

2

4

00...0001

00...0010

00...0100

00...1000

00...10000

00...000!

00...0010

00...0011

00...0100

00...0101

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

В момент tz начинается формирование второго цикла пилообразного напряжения. В момент, когда это напряжение достигает значения 0,95 U< срабатывает схема 7 сравнения, на ее выходе появляется потенциал 1 который поступает на информационный вход счетчика 8 и вход сброса ГЛИН

5. В результате на втором выходе дешифратора 6 появляется напряжение, которое открывает второй аналоговый ключ 9, и напряжение с ГЛИН 5 поступает на вторую вершину графа (фиг.Зг) . Если напряжение Uz v U то с компаратора 17 напряжение "1" подается на второй вход регистра 3 и с второго выхода регистра 3 — на второй индикатор блока 4 индикации.

Второй светодиод светится, отображая тот факт что вторая вершина вошла в заданный радиус. Если Б с Б, то

11 1 с компара.тора 17 снимается нулевой потенциал и второй индикатор не светится.

Аналогичным образом устройство работает до л -го цикла пилообразного напряжения, вырабатываемого ГЛИН 5.

Когда напряжение h -го цикла пилообразного напряжения достигает значения 0,95 U<, с n-ro выхода дешифратора б на вход запрета ГЛИН 5 пода1251097 ется сигнал запрета, который запрещает дальнейшее генерирование пилообразных сигналов после достижения на выходе ГЛИН 5 напряжения U .

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

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

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

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

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

4gN

Составитель Т.Сапунова

Техред М.Ходаиич Корректор Л.Пилипенко

Редактор И.Рыбченко

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

ВНИИПИ Государственного комитета СССР по делам изобретений и открытий

113035, Москва, Ж-35, Раушская наб., д. 4/5

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