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

 

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

союз советсних

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

РЕСПж ЛИК (g,) 4 G 06 F 15/20 г г

ГОСУДАРСТВЕННОЙ КОМИТЕТ пО изовРетениям и отнРцтил>1 пРИ Гннт сссР (21) 4300421/24-24 (22) 24,.08.87 (46) 07.08.89. Бюп. г1"- ?9 (72) В.гг. Балакирев и А,Г. Луценко (53) 68 1.325(088.8) (56) Авторское свидетельство СССР

Р 830409, кл. С 06 G 7/122, 1979.

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

Р 553617, кл. G 06 С 7/122, 1975. (54) УСТРОЙСТВО ДЛЯ ИССЛЕДОВАНИЯ

ГРАФОВ (57) Изобретение относится к области вычислительной техники и может быть

Изобретение относится к вычислительHO. I Tÿõíèêå и может бьгть использовано для исследования параметров графов.

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

На чертеже представлена функциональная схема устройства. ,Устройство содержит модель 1 графа из моделей 2 ветвей, каждая из которых состоит .гз первого 3, второго третьего 5 и четвертого 6 разделительных диодов, тиристора 7, переменного резистора 8 и источника 9 IIoстоянного напряжения, группу 10 переключателеи, генератор 11 импульсов и распредели-.åëü 12 импульсов, элемент 13 задержки, триггер 14, коммутатор 15, первый 16- и второй 17 исиспользовано для исследования параметров графов, Цель изобретения расширение функциональных возможностей — достигается за счет того, что в устройство, содер>кащее модель графа, модели ветвей, источник регулируемого напряжения, введены группа переключателей, генератор импульсов, распределителs импульсов, элемент задержки, триггер, коммутатор, второй источни регулируемого напряжения, элемент ИЛИ, группа на груз очных резисторов, группа комм тагоров, две группы триггеров, и группы ключей. 1 ил. точники регулируемого напряжения, элемент ИЛИ 18, группу нагруэ очных резисторов 19, группу коммутаторов

20, первую 21 и вторую 22 группы триггеров, первую 23, вторую ?4 и третью 25 группы ключей.

Перед началом работы в нулевое состояние приводятся распределитель

12 и триггеры 14, 21 и 22. С помощью источников 16 и 17 устанавливаются напряжен я, пр опор ционал ьные зада иным радиусам К < и К . У коммутатора

15 к выходу подключен первый информационный вход, у коммутаторов ?О информационные входы соединены с первы— ми выходами. В каждой модели 2 с помощью переменного резистора 8 уста— навливают напря>кение, обеспе пгнающее такой ток в управляющей цепи тиристора 7, который соответствует напряжению пробоя этого тирис", ора, пропорциональному весу ветви.

9368 4 второй информационный вход, а также

° на управляющие входы коммутаторов

20, которые подключают свои информационные входы к вторым выходам. Далее распределитель 12, выполненный по схеме кольцевого счетчика, автоматически начинает выдачу импульсов на первый, второй и т.д. выходы, и устройство работает аналогично, только вместо Е, в вершине графа поочередно подаются напряжения Е, а факт пробоя путей между вершинами графа и начальной А-й вершиной фиксируется в триггерах 22. При этом каждый ключ

25 открыт лишь в том случае, если соответствующий триггер 21 находится в нулевом состоянии (с его инверсного выхода снимается единичный по2Q тенциал) . Если соответствующий триг-" гер "2 перешел в единичное состоян к-, то единичный сигнал с его выхода проходит через открытый ключ 25 íà соответствующий выход вершин устройст

25 ва, сигнализируя, что вершина графа лежит между радиусом К, (исключительно) и радиусом К (включительно), Через время задержки, равное времени протекания одного цикла распре-.

30 делителя 12, элемент 13 задержки выдает сигнал на вход останова генератора 11, прекращая. работу устройства, и сигнал на выход окончания работы устройства. По единичным сигналам на выходах Вершин устройства судят о номерах вершин, лежащих между двумя заданными радиусами.

3 149

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

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

Например, импульс. с второго выхода распределителя 12 (Б -вторая вершина) открывает ключи 23 и 24, и напряжение Е< проходит через коммутатор 15 и открытый ключ 23 и переключатель 10 в вершину Б модели далее через модели 2 кратчайшего (или/и других) пути между вершинами

Б и А (если напряжение Е, достаточно для пробоя соответствующих тиристоров 7) в вершину А и затем через переключатель 10< (1 соответствует

А) и нагрузочный резистор 19 на корпус. Напряжение с первого вывода резистора 194 через элемент ИЛИ 18 проходит через ключ 24 и коммута-! тор 20 на вход триггера 21 и перебрасывает его в единичное состояние.

Импульс с последнего выхода распределителя 12 перебрасывает в единичное состояние триггер 14, единичный сигнал с выхода которого поступает на управляющий вход коммутатора

15, который подключает к выходу свой

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

Устройство для исследования графов, содержащее первый источник регулируемого напряжения, модель графа, состоящую из моделей ветвей, соединенных в соответствии с топологией исследуемого графа и содержащих источник постоянного напряжения, переменный резистор, ключевой элемент, выполненный на тиристоре, первый и второй разделительные диоды, аноды которых соединены„ первый и второй выходы источника постоянного напряжения соединены с соответствующими выходами переменного резистора, подвижный контакт которого соединен с управляющим электродом тиристора, о т л и ч а ю щ е е с я тем, что, с целью расширения функциональных возможностей за счет определения мн 1499368 жества вершин, лежащих между двумя заданными радиусами, оно содержит группу переключателей, генератор импульсов, распределитель импульсов, 5 элемент задержки, триггер, коммутатор, второй источник регулируемого напряжения, элемент ИЛИ, группу нагрузочных резисторов, группу коммутатОрОВ, первую и Вторую Группы триггеров, с первой по третью группы ключей, кроме того, каждая модель ветви содержит третий и четвертый разделительные диоды, катоды которых соединены с анодом тиристора, катод которого соединен с анодами первого и второгз разделительных диодов и вторым выходом источ -лка постоянного напряжения. катод первого разделительного диода соединен с анодом тре-д тьего разделительного диода и является первым входом-выходом модели ветви, катод второго разделительного диода соединен с анодом четвертого разделительного диода и является вто- рым входом-выходом модели ветви, вход каждого переключателя группы соединен . соответствующим узлом модели графа, выход генератора импульсов соединен с входом распредели- ЗО теля HMIjjrrbcoB> выходы которого соединены с управляющими входами соответствую|цих ключей первой и второй групп, выход старшего разряда распределителя импульсов соединен с входом установки в "1" триггера, прямой выход которого соединен с управляющим. входами коъя|утатора и группы коммутаторов и входом элемента задержки, выход которого соединен с входом останова генератора импульсов, вход запуска которого является входом запуска устройства, первый и второй информационные входы коммутатора соединены с выходами первого и второго источников регулируемого напряжения соответственно, выход коммутатора соединен с информационными входами ключей первой группы, информационные выходы которых соединены с первыми выходами соответствующих гереключателей группы, вторые выходы которых соединены с первыми входами соответствующих нагрузочных резисторов и с соответствующими входами элемента

ИЛИ, выход которого соединен с информационными входами ключей второй группы|, выходы КОТОрых соединены с информа|в|онными входамн соответствующих коммутаторов группы, первые и вторые информационные выходы которых соединены с входами установки в "1" соответствуюп чх триггеров первой и второй групп, инверсные Выходы триггеров первой группы и прямые выходы триг-еров второй группы соединены с информационными и управляющими входами соответствующих ключей третьей группы, информационные выходы которых являются соответственно информационныъж выходами устройства, вторые выходы нагрузочных резисторов группы соединены с входом нулевого потенциала устройства.

1499368

Составитель О, Гречухина

Техред Л. Сердюкова Корректор Т.Малец

Редактор В. Петраш

Заказ 4696/49 Тираж 668 Подписное

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

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

Производственно-издательский комбинат Патент, r.Ужгород, ул. Гагарина, 101