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

 

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

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

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

РЕСПУБЛИК (19) (11) А1 ш 4 С 06 F 15/20

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

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ

М АВТОРСИОМУ СВИДЕТЕЛЬСТВУ.(21) 4164473/24-24 (22) 16.12.86 (46) 30.09.88, Бюл. У 36 (72) E.È.Bîðîäåíêî, В.Е.Назаренко, Л.Г.Подзубанов, Б,И.Нагорнов, В.А.Синица и В.В.Верияскин (53) 681.333 (088.8) (56) Авторское свидетельство СССР

У 553628, кл. G 06 G 7/122, 1977, Авторское свидетельство СССР

У 1241266, кл. G 06 G 7/48, 1986. (54) УСТРОЙСТВО ДЛЯ ИССЛЕДОВАНИЯ ПАРАМЕТРОВ ГРАФОВ (57) Изобретение относится к вычислительной технике и может быть использовано для решения задач на графах, связанных с определением абсолютного внешнего центра графой, являющихся математическими моделями сетей связи, информационно-расчетных систем и т.д. Цель изобретения — расширение функциональньщ возможностей устройст1427379 ва за счет определения абсолютного внешнего центра графов. Устройство содержит модели ветвей 1, второй генератор 2 линейно изменяющегося напряжения, дифференцирующую цепочку 3, второй элемент ИЛИ 4, первый счетчик

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

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

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

Устройство содержит модели ветвей графов 1, второй генератор 2 линейно- 20 изменяющегося напряжения, дифференцирующий элемент 3, второй элемент ИЛИ

4 первый счетчик 5, первый дешифратор 6, группу четырехканальных ключей 7, третий элемент ИЛИ 8, первый элемент И 9, второй счетчик 10, второй дешифратор 11, первую группу ключей 12, второй элемент И 13, третий счетчик 14, третий дешифратор 15, вторую группу ключей 16, первый генератор 17 линейно изменяющегося напряжения, группу накопительных элементов 18, группу компараторов 19, первый элемент ИЛИ 20, блок 21 отобра " жения.

Модель ветви содержит диоды 22...

25, тиристоры 26...29, генератор 30 линейно изменяющегося напряжения, накопительный элемент 3 1, инвертор 32, элемент ИЛИ 33, первый компаратор 34, элемент 35 задержки, второй компара- 40 тор Зб, блок 37 задания веса ветви. второй счетчик 10, второй дешифратор

11, второй элемент И 13, третий счетчик 14, третий дешнАратор 15, группы ключей 12„-12„, 16 <-16<, первый гене-, ратор 17 линейно изменяющегося напряжения, группу накопительных элементов 18, -18, группу компараторов 19»19, первый элемент 20 ИЛИ, блок отображения 2 1. 4 ил.

Устройство работает следующим образом.

Из моделей ветвей 1 собирается схема в соответствии с топологией графа. В каждой модели ветви устанавливается ее вес с помощью блоков 37 задания веса ветви.

Счетчики обнуляются, а накопительные элементы разряжаются (шины сброса счетчиков и цепи разряда накопительных элементов не показаны как второс "пенные).

В исходном положении выход генератора 2 линейно изменяющегося напряжения через ключ 7< подключен к первой модели ветви 1, а вершина графа через ключ 12, подключена последовательно через ключ 16» к накопительному элементу 18<.

По команде "Старт" на входе пуска устройства (Vs на фиг,2) генератор увеличивает напряжение до определенного уровня, при котором в определенный момент времени происходит переключение тиристоров принаддежащихцепи, для которой . Б =шЫ вЂ” это ми1-1 нимальное напряжение, при котором начинает протекать ток по одному кратчайшему пути иэ множества возможных путей между точкой j первой модели ветви и вершиной графа а. Накопительный элемент 18» зарядится до уровня, пропорционального сумме весов ветвей, входящих в кратчайший путь иэ точки

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

12, и включение ключа 12>, т.е. подключение к цепи вершины графа Ь. Аналогично к цепи подключаются все и вершин графа, а накопительный элемент

18, зарядится до максимального значения, соответствующего самому длинному из всех кратчайших путей между точкой j и одной из и вершин графа.

При комбинации сигнала о включении ключа 12„ и сигнала с выхода дифференцирующего элемента 3 на выходе элемента И 13 появится импульс (см.

U íà фиг.2), который поступает на вход останова генератора 2, вход пуска модели ветви и информационный вход счетчика 14. Этим мы выбираем следующую точку на модели ветви rpaAa u подключаем к цепи следующий накопительный элемент 18. При получении с выхода модели ветви команды "Стоп" на третий вход элемента ИЛИ 8 работа схемы повторяется как по команде

"Старт".

При получении с выхода окончания работы модели ветви команды ™Конец", что соответствует перебору всех точек на данной модели ветви, происходит через счетчик 5 и дешифратор 6 вклю30 чение очередного ключа 7, т.е. подключение к цепи очередной модели ветви, и работа повторяется как по команде "Старт".

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

При комбинации сигнала о включении ключа 7 и сигнала "Конец" от модели ветви на выходе элемента И 9 появится импульс, который поступает через элемент ИЛИ 4 на вход останова гене- 45 ратора 2 и вход пуска генератора 17 линейно изменяющегося напряжения. На вторые входы компараторов 19 начинает поступать линейное возрастающее напряжение от 0 до какого-то опреде50 ленного значения, которое соответствует минимальному напряжению, поданному на первый вход одного из компараторов 19 с соответствующего накопительного элемента 18. Как только эти напряжения станут равными, на выходе соответствующего компаратора появится напряжение "1", которое поступит на соответствующий вход элемента ИЛИ 20 и блока 21 отображения.

Единичный сигнал с выхода элемента

ИЛИ ?О подается на вход останова генератора 17 и запрещает дальнейшее увеличение напряжения на его выходе (с целью предотвращения отображения ложных абсолютных внешних центров) .

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

Модель ветви работает следующим образом. На выходе блока 37 задания веса ветви (см. Фиг.3) устанавливается напряжение U при котором в базовой цепи тиристоров 26 и 27 устанавливается ток I> что создает условия для открывания тиристоров 26 и

27 при напряжении на их анодах, пропорциональном весу ветви. В базовой цепи тиристоров 28 и 29 протекает ток спрямления, и тиристоры находятся в проводящем состоянии, .В этом состоя.нии вес модели ветви задан первым плечом,. второе плечо имеет нулевой .вес, т.е. точка j совпадает с вершиной графа k. При подаче сигнала

"Пуск" на вход пуска модели ветви (см. Фиг.4,в) происходит запуск генератора 30 линейно изменяющегося напряжения, выход которого пбдключен к накопительному элементу 31 и первому компаратору 34. В момент времени, когда напряжение на выходе генератора 30 превысит напряжение на выходе накопительного элемента 31,.на выходе первого компаратора 34 появится импульс, поступающий на вход элемента

35 задержки, с выхода которого он попадает через элемент ИЛИ 33 на вход сброса генератора 30 и выход модели ветви (" Стоп" ). За это время при увеличении базового тока тиристоров 26 и 27, управляемого выходным напряжением накопительного элемента 31, и одновременном уменьшении на такую же величину базового тока тиристоров

28 и 29, управляемого выходным напряжением с инвертора 32, линейно уменьшается напряжение включения первого плеча и линейно увеличивается напряжение включения второго плеча, напряжение включения ветви .ik остается неизменным, пропорциональным заданному "весу" ветви графа.

Таким образом, моделируется перемещение точки j по ветви графа в направлении k i, Интервал перемещения

1427379 точки j задается элементом 35 задержки. При уменьшении на выходе инвертора 32 напряжения до уровня, равного срабатывает второй компаратор

36, выход которого подключен через элемент ИЛИ 33 к входу сброса генератора 30 и к выходу окончания работы модели ветви (конец).

Аналогично моделируется движение точки по ветви графа в обратном направлении.

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

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

1 компараторов, первые входы которьм объединены и соединены с выходом пер- "0 вого генератора линейно изменяющегося напряжения второй вход i-го компаратора (i=1,1) соединен с выходом i-го накопительного элемента (i=1,1), выход i-го компаратора является 1-м вы- 45 ходом центра графа устройства (i=1,1) и соединен с i-м входом первого элемента ИЛИ, вход пуска первого генератора линейно изменяющегося напряжения соединен с выходом первого элемента 50

И и с первым входом второго элемента

ИЛИ, выход которого соединен с входом останова второго генератора линейно изменяющегося напряжения, вход пуска которого соединен с выходом третьего 55 элемента ИЛИ, первый вход которого является входом пуска устройства, вто- рой вход третьего элемента ИЛИ соединен с третьими выходами четырехканальных ключей группы и с информационным входом первого счетчика, выход которого соединен с входом первого дешифратора, k-й выход которого соединен с управляющим входом k-ro четырехканального ключа (k=1,m) группы а m-й выход первого дешифратора сое.» динен с первым входом первого элемента И, второй вход которого соединен с третьим входом третьего элемента ИЛИ и с четвертыми выходами четырехканальним ключей группы, первые исполнительные входы которых соединены с выходом второго генератора линейно изменяющегося напряжения и через дифференцирующий элемент — с входом сброса второго генератора линейно изменя ющегося напряжения, с информационным входом второго счетчика и с первым входом второго элемента И, вьмод которого соединен с вторым входом вто" рого элемента ИЛИ, с вторыми исполнительными входами четырехканальных ключей группы, с входом установки в

"0" второго счетчика и с информационным входом третьего счетчика, выход которого соединен с входом третьего решифратора, i-й выход которого соединен с управляющим"входом i-ro ключа (i=1 1) второй группы, выход которого соединен с входом i-го накопительного элемента (i=1,1) группы, исполнительные входы ключей второй группы объединены и соединены с выходами ключей первой группы управляющий вход j-ro ключа (j 1,n) первой группы соединен с j-м выходом дешиф ратора, вход которого соединен с выходом второго счетчика, управляющий вход m-ro ключа первой группы, кроме того, соединен с вторым входом второго элемента И, исполнительный вход

j-ro ключа (j=1,n) первой группы соединен с j-й вершиной моделей ветвей графа, вход k-й модели ветви (k=1,m) графа соединен с первым выходом k-го четырехканального ключа группы, второй выход которого соединен с входом пуска k-й модели ветви графа, выход которой соединен с третьим исполнительным входом k-го четырехканального ключа группы, четвертый исполнительный вход которого соединен с выходом окончания работы 1с-й модели ветви графа.

2. Устройство по п.1, о т л ич а ю щ е е с я тем, что модель вет«

1427379 иUg

Пуск

Ц

Стал ахеи и!7

Ugy ви графа содержит с первого по четвертый тиристоры, с первого по четвертый диоды, генератор линейно изменяющегося напряжения, накопительный элемент, инвертор, элемент ИЛИ, два

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

Ф Ф \ л ф с

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

1427,379

8epdoe nnevn

8rnnpae nnevo

Руся ие, Редактор О.Спесивых

Заказ 4854/46 Тираж 704 Подписное

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

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

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

Стю кснец

uqq йи

use

Канщ

Составитель С.Кошелев

Техред И.Ходанич Корректор C.Шекмар