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

00 Од

Изобретение относится к области вычислительной техники и может быть использовано при решении задач на графах, например, для определения окрестностей вершин графа заданного радиуса. Цель изобретения - повьппе- ние точности. Цель достигается вне- - дением в устройство группы злементов, И и элемента ИЛИ. Устройство позволяет повысить точность при определении количества вершин графа, входящих в заданный радиус, т.к. при этом анализируются все пути, ведущие в исследуемую вершину. 3 ил.

Р

113

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

Цель изобретения - повышение точности.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Ч

R;(X,) {Xj/d(x., Xj) R,

Х-ЕХ

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

На входные зажимы i, j модели 2 подается напряжение, изменяющееся от 0,95 Up до Ug (где UR - напряжение, пропорциональное заданному радиусу), при котором через любой ключевой диод 16 и токозадающий резистор 17 в зависимости от полярности приложенного напряжения начинает протекать ток

I p (если приложенное напряжение СТр меньше веса ветви U, ток через мог дель ветви 2 не протекает). Этот ток

создает на одном из двух токозадающих резисторов 17 соответствующее падение напряжения, которое подается на первый вход компаратора 19. Компаратор 19 срабатывает и на его вьпсоде появляется потенциал . Вес модели ветви 2 создается с помощью потенциометра 15. Если модели ветвей составляют определенный путь, то ток по этому пути начинает протекать только в случае, если

,- .

где m - количество моделей ветвей, вошедших в даннъш путь.

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

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

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

Работа устройства начинается с мор яясения. В момент, когда это напряжение достигает значения 0,95 U, срабатывает блок 7 сравнения, на ее выходе появляется потенциал , ко- 40 торый поступает на информационный вход счетчика 8 и вход сброса ГЛИН 5. В результате на втором выходе дешифратора 6 появляется напряжение, которое открьшает второй аналоговый

мента поступления сигнала на вход за- 45 ключ 9, и напряжение с ГЛИН 5 посту- пуска устройства. ГЛИН 5 начинает пает на вторую вершину графа (фиг.Зг). вьфабатьгаать линейно изменяющееся Если напряжение Ug и, то с компа- напряжение (фиг.За, t,), которое поступает на вход схемы 7 сравнения и

ратора 19 напряжение 1 подается на второй вход элемента ИЛИ 12 и через

на управляющие входы ключей 9, - 9«,. которые закрыты, так как на всех вы-/ ходах дешифратора 6 нулевые потенци- алы. При достижении напряжением на выходе ГЛИН 5 значения 0,95 от напряжения, пропорционального заданному радиусу окрестности U, срабатывает Схема 7 сравнения, так как на его первом и втором входах напряжение одинаково. На выходе схемы 7 сравне

9

ния (фиг.36, t) появляется напряжение 1, которое поступает на вход сброса ГЛИН 5 и на информационный вход счетчика 8. С выхода счетчика 8 кодовая комбинация поступает на вход

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

Счетчик

00...0001

00. 00. 00.

.0010 .0011 .0100

1

2 3 4

00..0101

Дешифратор 00...0001 00...0010 00...0100 00...1000 00...10000

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

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

ключ 9, и напряжение с ГЛИН 5 посту- пает на вторую вершину графа (фиг.Зг). Если напряжение Ug и, то с компа-

ратора 19 напряжение 1 подается на второй вход элемента ИЛИ 12 и через

И 13j (так как на первый вход И I3tJ подается напряжение с второго выхода дешифратора 6) на второй выход регистра 3 И, на второй индикатор блока индикации 4. Второй светодиод

засветится, отображая тот факт, что вершина два вошла в заданный радиус. Если I d ;U, то с компаратора 19 снимается нулевой потенциал и второй индикатор не засветится.

1367019

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

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

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

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

Устройство для определения параметров графа, содержащее модель графа, группу ключей, счетчик, дешифратор, блок сравнения, генератор линей- но-изменяющегося напряжения, регистр, ЗО

- - -- 1ШМ

tf

5

0

5

О

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

Фиг.1

16

17

КЬсЬ-чгЬ-Й

17 J6

VcjivHS

tftf

H12

Ь-Й

17 J6

«J-o

(ue.Z