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

Старт

142

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

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

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

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

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

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

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

Модель ветви содержит диоды 22... 25, тиристоры 26...29, генератор 30 линейно изменяющегося напряжения, накопительный элемент 31, инвертор 32, элемент ИЛИ 33, первьй компаратор 34, элемент 35 задержки, второй компара- тор 36, блок 37 задания веса ветви.

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

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

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

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

По команде Старт на входе пуска устройства (Ug на фиг.2) генератор увеличивает напряжение до определенного уровня, при котором в определенный момент времени происходит переключение тиристоров, принадлежащих

к

цепи, для которой , 51 и., min - это ми- . .(

нимальное напряжение, при котором начинает протекать ток по одному кратчайшему пути из множества возможных путей между точкой j первой модели ветви и вершиной графа а. Накопительный элемент 18 зарядится до уровня, пропорционального сумме весов ветвей входящих в кратчайший путь из точки J.B вершину а. В момент переключения тиристоров на выходе дифференцирующего элемента 3 появится импульс, ко- торьй поступает на вход сброса генератора 2 и информационный вход счетчнка 10, таким образом, через дешифратор 11 происходит выключение ключа 12. и включение ключа 12„, т.е. под2

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

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

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

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

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

мента Ш1И 20 и блока 21 отображения. Единичный сигнал с выхода элемента ИЛИ 20 подается на вход останова ге- нератора 17 и запрещает дальнейшее увеличение напряжения на его выходе (с целью предотвращения отображения ложных абсолютных внешнргх центров) . На блоке 21 отображения засвечиваетQ ся соответствующий светодиод, относящийся к точке графа, являющейся его абсолютным внешним центром.

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

Q -27 при напряжении на их анодах, пропорциональном весу ветви. В базовой цепи тиристоров 28 и 29 протекает ток спрямления, и тиристоры находятся в проводящем состоянии. .В этом состоя5 НИИ вес модели ветви задан первът плечом, второе плечо имеет нулевой вес, т.е. точка j совпадает с вершиной графа k. При подаче сигнала Пуск на вход пуска модели ветви (см. фиг.4,в) происходит запуск генератора 30 линейно изменяющегося напряжения, выход которого подключен к накопительному элементу 31 и первому компаратору 34. В момент времени, когда напряжение на выходе генерато-

5 ра 30 превысит напряжение на выходе накопительного элемента 31, на выходе первого компаратора 34 появится импульс, поступающий на вход элемента 35 задержки, с выхода которого он попадает через элемент РШИ 33 на вход сброса генератора 30 и выход модели ветви (Стоп). За это время при увеличении базового тока тиристоров 26 и 27, управляемого выходным напряжением накопительного элемента 31, и одновременном уменьшении на такую же величину базового тока тиристоров 28 и 29, управляемого выходным напряжением с инвертора 32, линейно умень0 шается напряжение включения первого плеча и линейно увеличивается напряжение включения второго плеча, напряжение включения ветви ik остается неизменным, пропорциональным задан5 ному

0

0

5

весу ветви графа.

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

5

точки j задается элементом 35 задерки. При уменьшении на выходе инвертра 32 напряжения до уровня, равного УЗТ срабатывает второй компаратор 36, выход которого подключен через элемент ИЛИ 33 к входу сброса генертора 30 и к выходу окончания работы модели ветви (конец).

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

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

15

1, Устройство для исследования параметров графов,содержащее гамоделей ветвей графа,соединенных согласно топологии графа, первый генератор линейно

30

изменяющегося напряжения, первый эле-,20 ющегося напряжения, с информационным

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

г

5

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

25 , -, ы, . 35 х я о- 45 ) я 50 м 55 о- ,„40

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

л

5

0

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

cpw. 2

Лербое плечо

Второе плечо