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

 

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

СОЮЗ СОВЕТСКИХ

СОЦИАЛИСТИЧЕСКИХ

РЕСПУБЛИК (5g 4 G 06 F 15/20

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ (21) 3963511/24-24 (22) 02.10.85 (46) 15.01.88. Бюл. Ф 2 (72) А.И. Бецков, Е.И. Бороденко, А.Г. Ларионов и А.Г. Зотов (53) 681.3(088.8) (56) Авторское свидетельство СССР

У 991434, кл. G 06 F 15/20, 1983.

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

Ф 1251097, кл. G 06 F 15/20, 1984. (54) УСТРОЙСТВО ДЛЯ ОПРЕДЕЛЕНИЯ ПАРАМЕТРОВ ГРАФА

„„SU„„1367019 А 1 (57) Изобретение относится к области вычислительной техники и может быть использовано при решении задач на графах, например, для определения окрестностей вершин графа заданного радиуса. Цель изобретения — повышение точности. Цель достигается введением в устройство группы элементов. . И и элемента ИЛИ. Устройство позво" ляет повысить точность при определении количества вершин графа, входящих в заданный радиус, т.к; при этом анализируются все пути, ведущие в исследуемую вершину. 3 ил.

1367019

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

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

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

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

10 задания радиуса, группу ll — 11„ переключателей, элемент ИЛИ 12, группу 13, — 13„ элементов И.

Модель 1 графа состоит из моделей

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

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

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

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

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

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

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

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

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

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

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

Вершина графа, для которого опре." деляются окрестности вершин заданного радиуса, с помощью переключателя

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

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

В математическом плане задача заключается в том, что для любой вершины х,. графа G = (Х, г), пусть К»» (х;) есть множество тех вершин х; графа G которые достижимы из вершин х» с помощью путей с длинами d (х„, ( х;),не превосходящими величины К

R„(x,.) = (х;/d(x;, х,.)) (R, х-EX

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

На входные зажимы i, j модели 2 подается напряжение, изменяющееся от

0,95 U < до U „ (где U„ - напряжение, пропорциональное заданному радиусу), при котором через любой ключевой диод 16 и токозадающий резистор 17 в зависимости от полярности приложенного напряжения начинает протекать ток

1367019

00...0010

00...0010 2

3 00...0100

00...0011

00...1000

00...10000

00...0100

00..0101

30

55

Т (если приложенное напряжение и меньше веса ветви U ток через мо".. дель ветви 2 не протекает). Этот ток создает на одном из двух токозадающих 5 резисторов 17 соответствующее падение напряжения, которое подается на первый вход компаратора 19. Компаратор 19 срабатывает и на его выходе появляется потенциал "1". Вес модели 10 ветви 2 создается с помощью потенци4 ометра 15. Если модели ветвей состав. ляют определенный путь, то ток по этому пути начинает протекать только в случае, если м

U<) . U„

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

Значение радиуса задается в блоке

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

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

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

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

00...0001 1 00...0001

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

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

5. В результате на втором выходе дешифратора 6 появляется напряжение, которое открывает второй аналоговый ключ 9, и напряжение с ГЛИН 5 поступает на вторую вершину rpaAa (фиг.Зг1.

Если напряжение U > П„, то с компаратора 19 напряжение "1" подается на второй вход элемента ИЛИ 12 и через

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

Если Г c U, то с компаратора 19 снимается нулевой потенциал и второй индикатор не засветится.

Аналогичным образом устройство работает до n""öèêëà пилообразного нап,ряжения, вырабатываемого ГЛИН 5. Когда напряжение и-го цикла пилообраэноto напряжения достигает значения

0,95 0„, с и-го выхода дешифратора 6 на вход запрета ГЛИН 5 подается сигнал запрета, который запрещает дальнейшее генерирование пилообразных 1ð сигналов после достижения на. выходе

ГЛИН 5 налряжения равного U<.

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

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

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

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

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

Ищж э Ь

t и- а жиг.У