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

СОЮЗ СОВЕТСКИСОЦИАЛИСТИЧЕСНРЕСПУБЛИК 11 4 С 06 Р 15/20 ОПИСАНИЕ ИЗОБРЕТЕНИЯМ АВТОРСИОМУ СВИДЕТЕЛЬСТВУ ногосявязи,ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССРПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИИ(56) Авторское свидетельство СССРУ 553628, кл. С 06 С 7/122, 1977,Авторское свидетельство СССРУ 1241266, кл. С 06 С 7/48, 1986.(54) УСТРОЙСТВО ДЛЯ ИССЛЕДОВАНИЯ ПАРАМЕТРОВ ГРАФОВ(57) Изобретение относится к вычислительной технике и может быть использовано для решения задач на графах,связанных с определением абсолютвнешнего центра графоВ, являющихматематическими моделями сетей синформационно-расчетных систем ит.д. Пель изобретения - расширениефункциональных возможностей устройст1427379 ва за счет определения абсолютного внешнего центра графов. Устройство содержит модели ветвей 1, второй ге" нератор 2 линейно изменяющегося напряжения, дифференцирующую цепочку 3, второй элемент ИЛИ 4, первый счетчик 5, первый дешиАратор б, группу четырехканальных ключей 7, -7 , третий элемент ИЛИ 8, первый элемент И 9,Изобретение относится к вычислительной технике и может быть использовано для решения задач на графах. связанных с определением абсолютного внешнего центра графов, являющихся математическими моделями сетей связи, информационно-расчетных систем и т.д.Цель изобретения - расширение функциональных возможностей устройст ва за счет определения абсолютного внешнего центра графов.На Аиг.1 представлена Функциональная схема устройства; на фиг.2 - временные диаграммы работы устройства, на фиг,3 - Аункциональная схема модели ветви графа 1 на фиг,4 - временные диаграммы работы модели ветви графа.Устройство содержит модели ветвей графов 1, второй генератор 2 линейно изменяющегося напряжения, дифференцирующий элемент 3, второй элемент ИЛИ 4 первый счетчик 5, первый дешифратор 6, группу четырехканальных клю-. чей 7, третий элемент ИЛИ 8, первый элемент И 9, второй счетчик 10, второй дешифратор 11, первую группу ключей 12, второй элемент И 13, третий счетчик 14, третий дешифратор 15, вторую группу ключей 16, первый генератор 17 линейно изменяющегося напряжения, группу накопительных элементов 18, группу компараторов 19 первый элемент ИЛИ 20, блок 21 бтобра" жения.Модель ветви содержит диоды 22 35 25, тиристоры 2629, генератор 30 линейно изменяющегося напряжения, накопительный элемент 31, инвертор 32, элемент ИЛИ 33, первый компаратор 34, элемент 35 задержки, второй компара тор 36, блок 37 задания веса ветви. второй счетчик 1, второй дешиФратор11, второй элемент И 13, третий счетчик 14, третий дешнАратор 15, группыключей 12 -12, 16 -16, первый гене-,ратор 17 линейно изменяющегося напряжения, группу накопительных элементов 18-18, группу компараторов 19,19, первый элемент 20 ИЛИ, блокотображения 2 1. 4 ил,Устройство работает следующим образом.Из моделей ветвей 1 собирается схема в соответствии с топологией графа, В каждой модели ветви устанавливается ее вес с помощью блоков 37 задания веса ветви."Счетчики обнуляются, а накопительные элементы разряжаются (шины сброса счетчиков и цепи разряда накопительных элементов не показаны как второс 1"пенные).В исходном положении выход генератора 2 линейно изменяющегося напряжения через ключ 7 подключен к первой модели ветви 1, а вершина графа через ключ 12, подключена последовательно через ключ 16, к накопительному элементу 18,По команде "Старт" на входе пуска устройства (08 на фиг,2) генератор увеличивает напряжение до определенного уровня, при котором в определенный момент времени происходит переключение тиристоров принаддежащих цепи, для которой Е Б =шип - это минимальное напряжение, при котором начинает протекать ток по одному кратчайшему пути иэ множества возможных путей между точкой 1 первой модели ветви и вершиной графа а. Накопительный элемент 18 зарядится до уровня, пропорционального сумме весов ветвей, входящих в кратчайший путь иэ точки 1,в вершину а. В момент переключения тиристоров на выходе дифференцирующего элемента 3 появится импульс, который поступает на вход сброса генератора 2 и информационный вход счет 1427379чика 10, таким образом, через дешифратор 11 происходит выключение ключа 12, и включение ключа 12, т.е. подключение к цепи вершины графа Ь, Аналогично к цепи подключаются все и вершин графа, а накопительный элемент 18, зарядится до максимального значения, соответствующего самому длинному из всех кратчайших путей между точкой 1 и одной из и вершин графа.При комбинации сигнала о включении ключа 12 и сигнала с выхода дифференцирующего элемента 3 на выходе элемента И 13 появится импульс (см.0. на фиг.2), который поступает на вход останова генератора 2, вход пуска модели ветви и информационный вход счетчика 14, Этим мы выбираем следующую точку намодели ветви графа и подключаем к цепи следующий накопительный элемент 18. При получении с выхода модели ветви команды "Стоп" на третий вход элемента ИЛИ 8 работа схемы повторяется как по команде "Старт".При получении с выхода окончания работы модели ветви команды "Конец", что соответствует перебору всех точек на данной модели ветви, происходит через счетчик 5 и дешифратор 6 вклю 30 чение очередного ключа 7, т.е. подключение к цепи очередной модели ветви, и работа повторяется как по команде "Старт".Таким образом, на 1 накопительных 35 элементах 18 собирается информация о самых длинных из всех кратчайших путей из каждой из 1 точек до одной из и вершин графа.40При комбинации сигнала о включении ключа 7 и сигнала "Конец" от модели ветви на выходе элемента И 9 появится импульс, который поступает через элемент ИЛИ 4 на вход останова гене ратора 2 и вход пуска генератора 17 линейно изменяющегося напряжения. На вторые входы компараторов 19 начинает поступать линейное возрастающее напряжение от 0 до какого-то опреде 50 ленного значения, которое соответствует минимальному напряжению, поданному на первый вход одного из компараторов 19 с соответствующего накопительного элемента 18. Как только эти напряжения станут равными, на выходе соответствующего компаратора появится напряжение "1", которое поступит на соответствующий вход элемента ИЛИ 20 и блока 21 отображения. Единичный сигнал с выхода элемента ИЛИ 20 подается на вход останова генератора 17 и запрещает дальнейшее увеличение напряжения на его выходе (с целью предотвращения отображения ложных абсолютных внешних центров) . На блоке 21 отображения засвечивается соответствующий светодиод, относящийся к точке графа, являющейся его абсолютным внешним центром.Модель ветви работает следующим образом. На выходе блока 37 задания веса ветви (см, Фиг.3) устанавливается напряжение Б , при котором в базовой цепи тиристоров 26 и 27 устанавливается ток , что создает условия для открывания тиристоров 26 и 27 при напряжении на их анодах, пропорциональном весу ветви, В базовой цепи тиристоров 28 и 29 протекает ток спрямления, и тиристоры находятся в проводящем состоянии, .В этом состоя.нии вес модели ветви задан первым плечом,. второе плечо имеет нулевой .вес, т.е. точкасовпадает с вершиной графа 1, При подаче сигнала "Пуск" на вход пуска модели ветви (см. Фиг.4,в) происходит запуск гене" ратора 30 линейно изменяющегося напряжения, выход которого пбдключен к накопительному элементу 31 и первому компаратору 34. В момент времени, когда напряжение на выходе генератора 30 превысит напряжение на выходе накопительного элемента 31,.на выходе первого компаратора 34 появится импульс, поступающий на вход элемента 35 задержки, с выхода которого он попадает через элемент ИЛИ 33 на вход сброса генератора 30 и выход модели ветви (" Стоп" ). За это время при увеличении базового тока тиристоров 26 и 27, управляемого выходным напряжением накопительного элемента 31, и одновременном уменьшении на такую же величину базового тока тиристоров 28 и 29, управляемого выходным напряжением с инвертора 32, линейно умень" шается напряжение включения первого плеча и линейно увеличивается напряжение включения второго плеча, напряжение включения ветви .д 1 с остаетсянеизменным, пропорциональным заданному "весу" ветви графа.1Таким образом, моделируется перемещение точки 1 по ветви графа в направлении 1 с-э , Интервал перемещенияточкизадается элементом 35 задержки, При уменьшении на выходе инвертора 32 напряжения до уровня, равногосрабатывает второй компаратор 36, выход которого подключен через элемент ИЛИ 33 к входу сброса генератора 30 и к выходу окончания работы модели ветви (конец).Аналогично моделируется движение точки по ветви графа в обратном направлении. 10 Формула изобретения151. Устройство для исследования параметров графов, содержащее ш моделей ветвей графа, соединенных согласно топологии графа, первый генератор линейно изменяющегося напряжения, первый эле мент ИЛИ, вход останова первого генератора линейно изменяющегося.напряжения подключен к выходу первого элемента ИЛИ, о т л и ч а ю щ е е с я тем, что, с целью расширения функциональных возможностей за счет определения абсолютного внешнего центра графов, в него введены второй генератор линейно изменяющегося напряжения, дифференцирующий элемент, второй и третий элементы ИЛИ, первый и второй элементы И, с первого по третий счет-, чики, с первого по третий дешифраторы, группа из ш четырехканальных ключей, первая группа из и ключей (где и - число вершин графа), вторая группа З 5 из 1 ключей (где 1 - число дискретных точек на дугах графа), группа из 1 накопительных элементов и группа из 1 компараторов, первые входы которьм объединены и соединены с выходом пер- "0 вого генератора линейно изменяющегося напряжения второй вход -го компара" тора (х=1,1) соединен с выходом -го накопительного элемента (х=1,1), выход ь-го компаратора является 1-м вы ходом центра графа устройства (=1,1) и соединен с -м входом первого элемента ИЛИ, вход пуска первого генератора линейно изменяющегося напряжения соединен с выходом первого элемента 50 И и с первым входом второго элемента ИЛИ, выход которого соединен с входом останова второго генератора линейно изменяющегося напряжения, вход пуска которого соединен с выходом третьего 55 элемента ИЛИ, первый вход которого является входом пуска устройства, вто- рой вход третьего элемента ИЛИ соединен с третьими выходами четырехканальных ключей группы и с информационным входом первого счетчика, выход которого соединен с входом первого дешифратора, 1 с-й выход которого соединен с управляющим входом К-го четырехканального ключа Э=1,ш) группы а а-й вьмод первого дешифратора соединен с первым входом первого элемента И, второй вход которого соединен с третьим входом третьего элемента ИЛИ и с четвертыми выходами четырехканальним ключей группы, первые исполнительные входы которых соединены с выходом второго генератора линейно изменяющегося напряжения и через дифФеренцирующий элемент - с входомсброса второго генератора линейно изменя ющегося напряжения, с информационным входом второго счетчика и с первым входом второго элемента И, выход которого соединен с вторым входом вто" рого элемента ИЛИ, с вторыми исполнительными входами четырехканальных ключей группы, с входом установки в "0" второго счетчика и с информационным входом третьего счетчика, выход которого соединен с входом третьего решифратора, -й выход которого соединен с управляющим"входом -го ключа (3.=1,1) второй группы, выход которого соединен с входом 1-го накопительного элемента (=1,1) группы, исполнительные входы ключей второй группы объединены и соединены с выходами ключей первой группы управляю" щий вход -го ключа Ц 1,и) первой группы соединен с 3-м выходом дешиФ- ратора, вход которого соединен с выходом второго счетчика, управляющий вход ш-го ключа первой группы, кроме того, соединен с вторым входом второго элемента И, исполнительный вход 3-го ключа (=1,и) первой группы соединен с -й вершиной моделей ветвей графа, вход 1-й модели ветви (1=1,ш) графа соединен с первым выходом 1-го четырехканального ключа группы, второй выход которого соединен с входом пуска 1-й модели ветви графа, выход которой соединен с третьим исполнительным входом к-го четырехканального ключа группы, четвертый исполнительный вход которого соединен с выходом окончания работы 1 с-й модели ветви графа.2. Устройство по п.1, о т л ич а ю щ е е с я тем, что модель вет1427379 Стал КОН иг я 2 ви графа содержит с первого по четвертый тиристоры, с первого по четвертый диоды, генератор линейно изменяющегося напряжения, накопительный элемент, инвертор, элемент ИЛИ, два5 компаратора, элемент задержки, блок задания веса ветви, анод первого тиристора соединен с входом первой вершины модели ветви и с катодом пер О вого диода, анод которого соединен с катрдами с первого по четвертый тиристоров, с анодами с второго по четвертый диодов и с входом нулевого потенциала накопительного элемента, анод второго тиристора соединен с катодами второго и третьего диодов, с анодом третьего тиристора и с входом модели ветви графа, анод четвертого тиристора соединен с катодом четвертого диода и с входом второй вершины модели ветви графа, вход пуска которой соединен с входом пуска генератора линейно изменяющегося наЭЪ ФЪл Фс пряжения, выход которого соединен спервым входом накопительного элемента и с первым входом первого компаратора, второй вход которого соеди"нен с. выходом накопительного элемента, с управляющими электродами первого и второго тиристоров и с входоминвертора, выход которого соединенс управляющими электродами третьегои четвертого тиристоров и с первымвходом второго компаратора, второйвход которого соединен с выходом блока задания веса ветви и с вторымвходом накопительного элемента, выходпервого компаратора соединен черезэлемент задержки с выходом моделиветви графа и с первым входом элемента ИЛИ, выход которого соединенс входом останова генератора линейноизменяющегося напряжения, второй входэлемента ИЛИ соединен с выходом второго компаратора и с выходом признака окончания работы модели ветви графа,а э ЪВ И 61427379 Араае плеча сарае мечаСоставитель С.Кошелев Техред М.Ходанич Коррек С,Шекмар актор О.Спесивых Заказ 4854/46 ВПроизводственно-полиграфическое предприятие, г. Ужгород, ул. Проектная Тираж 704НИИПИ Государственногопо делам изобретений13035, Москва, Ж, Рауш Подписиомитета СССРоткрытийая наб, д, 4/5