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

союз советсииСОЦИДЛИСТИЧЕСИИРЕСПУБЛИК г 1 г 4 С 06 Р 15/2 ОПИСАНИЕ ИЗОБРЕТЕНИИ АВТОРСКОМУ СВИДЕТЕЛЬСТБУ 4- 4(21) 4300421 (22) 24,.08.8 (46) 07.08,8 (72) В,М, Б, (53) 681, 325 (56) Авторск Р 830409, кл исполь метров 9. Бюл. .лакирев (088.8) ое свидС 06 г 1". 29и А,Г. Луцен етельство СССРС 7/122, 1979.льство СССРС 7/ 122, 1975,Авторско вид ет0 06(57) Изобрете вычислительно е относится ктехники и може ла ыть Изобрегтельной т относится к вычислие и может быть испольледования параметров ни для ис овак рафо ия - расширениезможностей устройделения множества Цель изобрстеункгцгональюы в тва за счет опр ежду двумя за вершин, лежа9 по 10 пльса гог е стояк ключа и расп мент 1 гутат о ГОСУДАРСТВЕННОЙ КОМИТЕТПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМПРИ ГКНТ СССР диусами,ертеже представлена фунсхема устройства,ойство содержит модель 1 гроделей 2 ветвей, каждая изсостоит из первого 3, вьего 5 и четвертого 6 радиодов, тиристора 7, пезистора 8 и источникаго напряжения, группу елеи, генератор 11 импу веделитель 12 импульсов, элезадержки, триггер 14, ком 15, первый 16.и второй 17 80) г 49 зж зовано для исследования параграфов Цель изобретения расширение функциональных возможностей - достигается за счет того, что в устройство, содержащее модель графа, модели ветвей, источник регулируемого капряжеггггя, введены группа переключателей, генератор импульсов, распределитель импульсов элемсггт задержки, триггер, коммутатор, второй источник регулируемого напряжения, элемент ИЛИ, группа нагрузочных резисторов, группа комю тагоров, две группы триггеров, и группы ключей. 1 ил. точники регулируемого напряжения,элемент ИЛИ 18, группу нагрузочныхрезисторов 19, группу коммутаторов20, первую 21 и вторую 22 группытриггеров, первую 23, вторую 24 итретью 25 группы ключей.Перед началом работы в нулевоесостояние приводятся распределитель12 и триггеры 14,21 и 22. С помощьюисточников 16 и 17 устанавливаютсянапряжеггия, пропорциональные заданкым радиусам Ки К. У коммутатора15 к выходу подключен первый ггггформационный вход, у коммутаторов О информационные входы соединены с первы -ми выходами, В каждой модели 2 с помощью переменного резистора 8 уста -навливают напряжение, обеспе игнающеетакой ток в управляющей цепи тиристора 7, который соответствует напряжению пробоя этого тирис",ора, пропорциональному весу ветви,9368 4второй информационный вход, а такжена управляющие входы коммутаторов20, которые подключают свои информационные входы к вторым выходам. Далее распределитель 12, выполненныйпо схеме кольцевого счетчика, автоматически начинает выдачу импульсовна первый, второй и т.д, выходы, иустройство работает аналогично, только вместо Е, в вершине графа поочередно подаются напряжения Е, а фактпробоя путей между вершинами графа иначальной А-й вершиной фиксируется 15 в триггерах 22, При этом каждый ключ25 открыт лишь в том случае, еслисоответствующий триггер 21 находитсяв нулевом состоянии (с его инверсного выхода снимается единичный по О тенциал). Если соответствующий триггер 22 перешел в единичное состояние,то единичный сигнал с его выхода проходит через открытый ключ 25 на со.ответствующий выход вершин устройст 25 ва, сигнализируя, что вершина графалежит между радиусом К, (исключительно) и радиусом К (включительно),Через время задержки., равное времени протекания одного цикла распре- ЭО делителя 12, элемент 13 задержкивыдает сигнал на вход останова генератора 11, прекращая. работу устройства, и сигнал на выход окончанияработы устройства. По единичным сиг"налам на выходах вершин устройствасудят о номерах вершин, лежащих меж"ду двумя заданными радиусами. 40 45 50 55 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, на корпус. Напряжение с первого вывода резистора 19 через элемент ИЛИ 18проходит через ключ 24 и коммутатор 20 на вход триггера 21 и перебрасывает его в единичное состояние,Импульс с последнего выхода распределителя 12 перебрасывает в единичное состояние триггер 14, единичный сигнал с выхода которого поступает на управляющий вход коммутатора15, который подключает к выходу свой Формула и з обр ет ения Устройство для исследования графов, содержащее первый источник регулируемого напряжения, модель графа, состоящую из моделей ветвей, соединенных в соответствии с топологией исследуемого графа и содержащих источник постоянного напряжения, переменный резистор, ключевой элемент, выполненный на тиристоре, первый и второй разделительные диоды, аноды которых соединены первый и второй выходы источника постоянного напряжения соединены с соответствую" щими выходами переменного резистора, подвижный контакт которого соединен с управляющим электродом тиристора, о т л и ч а ю щ е е с я тем, что, с целью расширения функциональных возможностей за счет определения мн 14993 б 8жества вершин, лежащих между двумя заданными радиусами, оно содержит группу переключателей, генератор им" пульсов, распределитель импульсов,5 элемент задержки, триггер, коммутатор, второй источник регулируемого напряжения, элемент ИЛИ, группу нагрузочных резисторов, группу коммутаторов, первую и вторую группы триггеров, с первой по третью группы ключей, кроме того, каждая модель ветви содержит третий и четвертый разделительные диоды, катоды которых соединены с анодом тиристора, к=год которого соединен с анодами первого и второго разделительных диодов и вторым выходом источника постоянного напряжения, катод первого разделительного диода соединен с анодом тре- о тьего разделительного диода и является первым входом-выходом модели ветви, катод второго разделительного диода соединен с анодом четвертого разделительного диода и является вто-рым входом-выходом модели ветви, вход каждого переключателя группы соединенсоответствующим узлом модели графа, выход генератора импульсов соединен с входом распредели- Зо теля импульсов, выходы которого соединены с управляющими входами соответствующих ключей первой и второй групп, выход старшего разряда распределителя импульсов соединен с входом установки в "1" триггера, прямой выход которого соединен с управляющим: входами коммутатора и группы коммутаторов и входом элемента задержки, выход которого соединен с входом останова генератора импул ьс ов, вход з апуска которого является входом запуска устройства, первый и второйинформационные входы коммутатора соединены с выходами первого и второгоисточников регулируемого напряжениясоответственно, выход коммутаторасоединен с информационными входамиключей первой группы, информационныевыходы которых соединены с первымивыходами соответствуюшнх гереключателей группы, вторые выходы которыхсоединены с первыми входами соответствующих нагрузочных резисторов ис соответствующими входами элементаИЛИ, выход которого соединен с информационными входами ключей второйгруппы выходы которых соединены синформацонньпп 1 входамн соответствующих коммутаторов группы, первые ивторые информационные выходы которых соединены с входами установкив "1" соответствуюпчх триггеров первой и второй групп, инверсные выходы триггеров первой группы и прямые выходы триггеров второй группысоединены с информационными и управляющими входами соответствующих ключей третьей группы, информационныевыходы которых являются соответственно информационныьв выходами устройства, вторые выходы нагрузочных резисторов группы соединены с входомнулевого потенциала устройства,1499368 ечухин ставитель О, хред Л.Сердю орректор Т,Малец етраш го 8 одписное твенно-издательский комбинат Патент , г.Ужгород, ул. Гагарина, 10 произ в Заказ 469ВНИИПИ Гос 9 Тирарственного комитет 11303 5, Москва,о изобретениям 35, Раушская ы гкрьтиям при ГКНТ СССд, ч/5