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

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

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

На чертеже представлена функ1дао- нальная схема устройства,

.Устройство содержит модель 1 графа из моделей 2 ветвей, каждая из которых состоит из первого 3, второго 4, третьего 5 и четвертого 6 разделительных диодов, тиристора 7, переменного резистора 8 и источника 9 постоянного напряжения, группу 10 переключателей, генератор 11 импульсов и распределитель 12 импульсов, элемент 13 задержки, триггер 14, коммутатор 15, первый 16-. и второй 17 источники регулируемого напряжения, элемент 1-ШИ 18, группу нагрузочных резисторов 19, группу коммутаторов 20, первую 21 и вторую 22 группы триггеров, первую 23, вторую 24 и третью 25 группы ключей,

Церед началом работы в нулевое состояние приводятся распределитель 12 и триггеры 14,21 и 22, С помощью источников 16 и 17 устанавливаются напряжения, пропорщ-шнальные заданным радиусам К, и К, У , татора 15 к выходу подключен первый икформа- ционньн вход, у кoм fyтaтopoв 20 информационные входы соединены с первыми выходами, В каждой модели 2 с помощью переменного резистора 8 устанавливают напряжение, обеспечивающее такой ток в управляющей цепи тиристора 7, который соответствует напряжению пробоя этого тирр стора, пропор- циональном весу ветви.

4;

СО

СО

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

С помощью соответствующего переключателя 10 через нагрузочное сопротивление 19 к нулевому потенциалу устройства подключают вершину графа, для которой требуется найти вершины, лежащие между дв.умя заданными радиусами К, и К (показано для вершины А). После подачи пускового сигнала импульсы генератора 11 поступают на вход распределите пя 12, который поочередно вьщает импульсы на свои выходы, что обуславливает поочередное открытие соответствующих ключей 23, В результате напряжение Е, с вькода источника 16 проходит через коммутатор 15, ключи 23 и переключатели 10 поочередно на все вершины графа, за исключением исходной (верщины А), Если Е равно или больше напряжения пробоя тиристоров 7 кратчайшего пути между текущей ве ршиной и вершиной А графа, то образуется цепь протекания тока от источника 16 через соответствующие модели 2 и резистор 19, напряжение с которого поступает через элемент ИЛИ 18 и открытый ключ 2А на информационный вход соответствующего коммутатора 20, с первого выхода которого сигнал поступает на вход соответствующего триггера 21 и перебрасывает его в единичное состояние. Например, импульс с второго выхода распределителя 12 (Б -вторая верщи- на) открывает ключи 23 и 2, и напряжение Е проходит через коммутатор 15 и открытый ключ 23 и пере-

ключатель 10, в вершину Б модели 1, далее через модели 2 кратчайшего (или/и других) пути между вершинами Б и А (если напряжение Е достаточно для пробоя соответствующих тиристоров 7) в вершину А и затем через переключатель lOj (1 соответствует А) и нагрузочный резистор 19j на корпус. Напряжение с первого вывода резистора 19( через элемент ИЛИ 18 проходит через ключ и коммутатор 20 на вход триггера 21 и перебрасывает его в единичное состояние. Импульс с последнего выхода распределителя 12 перебрасывает в единичное состояние триггер 14, единичный сигнал с выхода которого поступает на управляющий вход коммутатора 15, который подключает к выходу свой

5

второй информационный вход, а также на управляющие входы коммутаторов 20, которые подключают свои информационные входы к вторьш выходам. Далее распределитель 12, выполненный по схеме кольцевого счетчика, автоматически начинает вьщачу импульсов на первый, второй и т.д. выходы, и устройство работает аналогично, только вместо Е, в вершине графа поочередно подаются напряжения Е, а факт пробоя путей между вершинами графа и начальной А-й вершиной фиксируется в триггерах 22. При этом каждый ключ 25 открыт лишь в Totj случае, если соответствующий триггер 21 находится в нулевом состоянии (с его инверсного вькода снимается единичный потенциал) . Если соответствующий триггер 32 перешел в единичное состояшге, то единичный сигнал с его выхода проходит через открытьй ключ 25 на со ответствующий выход вершин устройст- 5 ва, сигнализируя, что вершина графа лежит между радиусом К (исключительно) и радиусом К 2 (включительно) Через время задержкиj равное времени протекания рдного цикла распределителя 12, элемент 13 задержки вьщает сигнал на вход останова генератора 11, прекращая, работу устройства, и сигнал на выход окончания работы устройства. По единичным сигналам на выходах вершин устройства судят о номерах вершин, лежащих между двумя заданными радиусами.

0

0

5

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

Устройство для исследования графов, содержащее первый источник регулируемого напряжения, модель графа, состоящую из моделей ветвей, сое диненных в соответствии с топологией исследуемого графа и содержащих источник постоянного напряжения, переменный резистор, клкиевой элемент, выполненный на тиристоре, первый и второй разделительные диоды, аноды которых соединены, первый и второй выходы источника постоянного напряжения соединены с соответствующими выходами переменного резистора, подвижный контакт которого соедине.н с управляющим электродом тиристора, отличающееся тем, что, с целью расширения функциональных возможностей за счет определения множества вершин, лежащих между двумя заданными радиусами, оно содержит группу переключателей, генератор импульсов, распределитель импульсов, элемент задержки, триггер, коммутатор, второй источгшк регулируемого напряжения, элемент ИЛИ, группу нагрузочных резисторов, группу коммута93686 торов и входом элемента задержки, выход которого соединен с входом останова генератора иьтульсов, вход запуска которого является входом запуска устройства, первый и второй информационные входы кo мyтaтopa соединены с выходами первого и второго источников регулируемого напряжения

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

торов, первую и вторую группы триг- ю соответственно, выход коммутатора

геров, с первой по третью группы ключей, кроме того, каждая модель ветви содержит третий и четвертый разделительные диоды, катоды которых соединены с анодом тиристора, которого соединен с анодами первого и второго разделительных диодов и вторым выходои источш ка постоянного 1апря)ке11ия, катод первого разделительного диода соединен с анодом тре-20 мационными вxoдa я ключей второй

тьего разделительного диода и является первым входом-выходом модели ветви, катод второго разделительного диода соединен с анодом четвертого

разделительного диода и является вто-25 соединены с входами установки рь5м входом-выходом модели ветви,

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

вход каждого перекл очателя группы соедикен i: соответствующим узлом ыодепи графа, выход генератора импульсов соединен с входом распределителя импульсов, выходы которого соединены с управляющими входами соот- ветствуюшдзс ключей первой и второй групп, выход старшего разряда распре- дeJ Штeля импульсов соединен с входом установки в 1 триггера, прямой вы- ход которого соединен с управляющимг: Злодам комз гутатора и группы коммутасоединен с информадионныг к входами ключей первой группы, информационные выходы которых соединены с первь ми вькодами соответствую5дкх переключа- телей группы, вторые которых соединены с первыми входами соответствующих нагрузочных резисторов и с соответствующими входами элемента ИЛИ, выход которого соединен с инфоргруппы, выходы которых соединены с информационными входам - соответствующих коммутаторов группы, первые и вторые информационные выходы кото соединены с входами установки

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