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

СООЗ СОВЕТСНИХСОЦИАЛИСТИЧЕСНИХРЕСПУБЛИН 9) (И) щ 4 С 06 Р 15/2 ГОСУД ПО ДЕ Вф 40 А,В,Биков,1977.ССР1984.АНИЯ ПА" сится ке и может быт еления длин го цикла, проходя- бранную вершину сетей связи, рас- ционно-вычислигих сложных систем, графах Цель 8 ЕННЫЙ НОМИТЕТ СССРИЗОБРЕТЕНИЙ И ОТНРЫТИЙ ТОРСКОМУ СВИДЕТЕЛЬСТВУ(22) 17.04.87 (46) 30.10.88. Бюл (72) Е.И,Бороденко В,В.Верияскин, М,В В.Е.Назаренко, Л.Г и В.А.Синица (53) 681325 (088.8 (56) Авторское св В 552617, кл. С 06Авторское свиде9 1241266, кл. С 0 (54) УСТРОЙСТВО РАМЕТРОВ ГРАФОВ (57) Изобретение о вычислительной тех использовано для о минимального прост щего через любую в графа, при анализе пределенных информтельных сетей и др смоделированных на изобретения - расширение функциональных возможностей за счет определения длины минимального простого цикла, проходящего через любую выбранную вершину исследуемого графа, Она достигается тем, что в устройство, содержащее коммутатор 3, элемент ИЛИ 5, генератор 10 линейно изменяющегося напряжения, группу накопительных элементов 17, группу компараторов 21, дополнительно введены наборное поле 1 с моделями ветвей 2, группа переключателей 4, второй б и третий 7 элементы ИЛИ, суммирующий 18 и вычитающий 9 счетчики, второй генератор 11 линейно изменяющегося напряжения, первый 12 и второй 13 генера торы одиночных импульсов, дешифратор 14, первая 15 и вторая 16 группы пключей, триггер 18, усилитель- формирователь 19 импульсных сигналов, элемент задержки 20, блок 22 измере- Я ния и индикации. 2 ил.Изобретение относится к вычислительной технике и может быть использовано для определения длины минимального простого цикла, проходящегочерез любую выбранную вершину графапри анализе сетей связи, распределенных информационно-вычислительных сетей и других сложных систем смоделироФванных на графах. ОЦель изобретения - расширениефункциональных возможностей за счетопределения длины минимального простого цикла, проходящего через любуювыбранную вершину исследуемого графа. 5На фиг.1 изображена структурнаясхема устройства; на фиг. 2 - функциональная схема коммутатора.Устройство содержит наборное поле 1модели ветвей 2 коммутатор 3, груп" 20пу переключателей 4; первый 5, второй 6 и третий 7 элементы ИЛИ, суммирующий 8 и вычитающий 9 счетчики,первый 10 и второй 11 генераторылинейно изменяющегося напряжения, 25первый 12 и второй 13 генераторы оди"ночных импульсов, дешифратор 14, первую 15 и вторую 6 группы ключей,группу накопительных элементов 17,триггер 18, усилитель-формирователь 3019 импульсных сигналов, элемент эа"держки 20, группу компараторов 21,блок 22 измерения и индикации.Наборное поле 1 представляет собойпанель с контактами, приспособлениямидля подключения моделей ветвей исследуемого графа в соответствии с еготопологией,Модели ветвей представляют собой 4-полюсники, включающие в себя регулируемые линии задержки. При помощи таких регулируемых линий задержки, соединенных в соответствии с тополо гней графа, задаются веса ветвей 45 исследуемого графа.Коммутатор 3 содержит аналоговые ключи 23 и 24, инверторы 25 и вентильные диоды 26.Переключатели 4 предназначены для набора на них двоичного числа, на единицу большего количества ветвей, инцидентных выбранной вершине исследуемого графа. Это могут быть, напри" мер, двухпоэиционные переключатели, которые в одном положении соединяют соответствующие информационные входы вычитающего счетчика 9 (см.фиг.1) с,потенциалом "0", а в другом положении - с потенциалом "1",Первый 10 и второй 11 генераторы линейно изменяющегося напряжения предназначены для выдачи линейно нарастающего напряжения при подаче на нх вход запуска импульса. Причем при приходе на их вход останова импульса нарастание напряжения на их выхо" де прекращается. Уровень данного напряжения в дальнейшем остается постоянным до прихода следующего импуль" са запуска, после чего напряжение на выходе генератора линейно изменяющегося напряжения начинает опять нарастать с нуля.Первый генератор 12 одиночных импульсов предназначен для генерации зондирующего импульса при подаче на его вход импульса запуска с выхода третьего элемента ИЛИ 7.Генератор представляет собой одно- вибратор, вырабатывающий импульс с некоторой задержкой, за время которой в коммутаторе 3 устанавливаются необходимые соединения. Вторая группа 6 кличей предназначена для соединения в определенные моменты времени "земли" с контактами наборного поля (вершинами) сцелью прекращения всех процессовраспространения электрических сигналов в схеме, собранной из моделейветвей в соответствии с топологиейграфа.Усилитель-формирователь 19 импульсных сигналов предназначен длявосстановления и усиления формы первого импульса (отклика), пришедшегос исследуемой схемы, составленной измоделей ветвей 2 в соответствии с,топологией граФа.Устройство работает следующим образом,На наборном поле 1 с помощью моделей ветвей 2 собирается схема в соответствии с топологией графа. В каждой модели ветви устанавливается ее"вес" с помощью соответствующей регулируемой линии задержки. Входы-выходы моделей ветвей графа, инцидентных выбранной вершине, через контакты наборного поля 1 подключаютсяк входам-выходам коммутатора 3,На переключателях 4 набираетсячисло, на единицу большее количестваветвей, инцидентных выбранной вер з 14 шине, в двоичном коде. После этого на вход сброса устройства подается импульс сброса, который, проходя через второй элемент ИЛИ 6, устанавливает суммирующий счетчик 8 в нулевое состояние. Тот же импульс записывает в вычитающий счетчик 9 число, набранное на переключателях 4, На этом подготовительная часть завершается.Работа устройства начинается с подачи на пусковой вход устройства импульса запуска, который, проходя через третий элемент ИЛИ 7, одновременно поступает на счетные входы вычитающего 9 и суммирующего 8 счетчиков, на входы запуска второго генератора 11 линейно изменяющегося напряжения и первого генератора 12 одиночных импульсовПри этом состояние вычитающего счетчика 9 уменьшается на единицу, а суммирующего 8 увеличивается на единицу. Состояние суммирующего счетчика 8 в двоичной форме подается на входы дешифратора 14На соответствующем выходе дешифратора 14 появляется потенциал логической единицы, поступающий на соответствующий управляющий вход коммутатора 3, в результате чего происходит коммутация. Остальные входы-выходы настраиваются на прием электрических сигналов от схемы, набранной на наборном поле. После этого с первого генератора 12 одиночных импульсов на первый вход коммутатора 3 поступает зондирующий импульс и, пройдя через скоммутированное соединение коммутатора 3, поступает на соответствующий вход-выход последнего, а далее через контакты наборного поля 1 в исследуемую модель графа.Проходя через все возможные пути, зондирующий импульс задерживается на величину, эквивалентную сумме "весов" ветвей графа, входящих в простые циклы, проходящие через выбранную вершину графа, Так как простые циклыимеют различный суммарный "вес" ("веса" некоторых циклов будут совпадать, что несущественно), то в моделях ветвей 2 графа, подключенных через контакты наборного поля 1 к входам-выходам коммутатора 3, появляются разнесенные по времени импульсы (отклики зондирующего импульса), Время, прошедшее с момента подачи зондирующего импульса до момента поступления34452 4 510152030 35 40 45 50 55 первого, приходящего по одной из других ветвей графа, импульса, соответствует длине минимального цикла, содержащего исследуемую ветвь, инцидентную выбранной вершине графа. Этот появившийся импульс, пройдя через коммутатор 3 на выходы, настроенные на прием сигналов от моделей ветвей, восстанавливается и усиливается усилителем-формирователем 19 импульсных сигналов, так как на электрический сигнал в моделях ветвей воздействуют переходные процессы, искажающие его форму. Поступая на вход останова второго генератора 11 линейно изменяющегося напряжения, который былзапущен в момент подачи зондирующего импульса, данный импульс останавливает его. На выходе второго генератора 11 линейно изменяющегося напряже" ния будет зафиксировано напряжение, эквивалентное полученному промежутку времени. Соответствующий ключ изпервой группы 15 ключей открываетсяпотенциалом логической единицы с со-. ответствующего выхода дешифратора 14 по управляющему входу, что обеспечивает поступление через его аналоговый вход линейно изменяющегося напряжения с выхода второго генератора 11 линейно изменяющегося напряжения на соответствующий накопительный элемент 17, заряжающийся до напряжения, присутствующего на выходе второго генератора 11 линейно изменяющегося напряжения н момент останова, Тем же импульсом, пришедшим с выхода усилителя-формирователя 19, в единичное состояние устанавливается триггер 18, который через вторую группу 16 ключей подключает к "земле" все вершины исследуемого графа, кроме выбранной, тем самым исключая появление на группе Е входов-выходов коммутатора 3 остальных разнесенных во времени, импульсов.Этот же импульс запускает второй генератор 13 одиночных импульсов, с выхода которого сформированный импульс поступает на вход элемента 20 задержки. С выхода элемента 20 задержки задержанный импульс поступает на вход установки в "0" триггера 18, который отключает от "земливсе вершины исследуемого графа, тем самым обеспечивая следующий цикл вычислений. Этот же импульс, пройдя через второй вход третьего элемен 5 1 ц 344 та ИЛИ 7, одновременно поступает на счетные входы вычитающего 9 и суммирующего 8 счетчиков и на входы запуска второго генератора 11 линейно из 5 меняющегося напряжения и первого генератора 12 одиночных импульсов. Вновь состояние вычитающего 9 и суммирующего 8 счетчиков изменяетсяНа выходе дешифратора 1 ч появляется со ответствующий управляющий сигнал, и в коммутаторе 3 устанавливаются соответствующие соединения, Исследуемой становится следующая по порядку ветвь графаЗондирующий импульс с запус Б тившегося первого генератора 12 одиночных импульсов, пройдя через скоммутированное соединение коммутатора 3 на соответствующий иэ группы вход-выход коммутатора 3, через контакты 20 наборного поля 1 поступает в очередную исследуемую модель ветви. Далее весь процесс вычислений идет аналогично описанному выше, в результате чего заряжается следующий элемент из груп пы накопительных элементов 17. Напряжение на нем равно напряжению на выходе второго генератора 11 линейно изменяющегося напряжения в момент его останова и соответствует длине мини мального цикла, содержащего данную очередную исследуемую ветвь, инцидентную выбранной вершине исследуемого графа, Данные циклы вычислений повторяются до тех пор, пока состояние вычитающего счетчика 9 не станет равным нулю. В этот момент на всех накопительных элементах 17 в виде напряжений содержится информация о длинах минимальных циклов, содержа щих все соответствующие им ветви инцидентные выбранной вершине графа. Из этих напряжений необходимо выбрать минимальное, которое будет соответствовать длине минимального цикла, 45 проходящего через выбранную вершину графа. По достижении вычитающим счетчиком 9 нулевого состояния, на его вы коде появляется импульс, который,проходя через второй вход второго элемента ИЛИ 6, сбрасывает в "О" состояние суммирующего счетчика, тем самым устраняя все соединения в коммутаторе 3. Этот же импульс поступает на вход запуска первого генератора 10 линейно изменяющегося напряжения. На его выходе начинает нарастать линейно изменяющееся напряжение, котороепоступает на вторые входы группы компараторов 21, на первые входы которых поступают напряжения с выходов еоответствующих накопительных элементов 17. Как только напряжение с выхода первого генератора 1 О линейноизменяющегося напряжения сравняется снапряжением какого-либо из накопительных элементов 17 (с наименьшим из всехвсех напряжений), на выходе соответствующего компаратора 21 появляетсяимпульс, который, пройдя через первыйэлемент ИЛИ 5, поступает на вход останова первого генератора 1 О линейно изменяющегося напряжения. На выходе последнего Фиксируется напряжение, соответствующее длине минимального цикла, проходящего через выбранную вершину исследуемого графа. Данное напряжение поступает на вход блока 22 измерения и индикации и выдается на его индикатор в удобной для обработки Форме. Формула изобретенияустройство для исследования параметров графов, содержащее коммутатор группу компараторов, группу накопительных элементов, первый генератор линейно изменяющегося напряжения, элемент ИЛИ, выход которого соединен с входом останова первого генератора линейно изменяющегося напряжения, выход каждого накопительного элемен" та группы соединен с первым входом соответствующего компаратора группы, выход которого соединен с соответствующим входом элемента ИЛИ, вторые входы компараторов группы соединены с выходом генератора линейно изменяющегося напряжения, о т л и ч а ю,щ е е с я тем, что, с целью расширения Функциональных возможностей за счет определения длины минимального простого цикла, проходящего через любую выбранную вершину исследуемого графа, в него введены второй и третий элементы ИЛИ, группа переключателей, суммирующий и вычитающий счетчики, наборное поле моделей ьетвей, дешифратор, первый и второй генераторы одиночных импульсов, второй генератор линейно изменяющегося напряжения, первая и вторая группы кщочей, триггер, усилитель-Формирователь импульсных сигналов, элемент задержки, блок измерения и индикации, 1434452вход которого соединен с выходом первого генератора линейно изменяющегосянапряжения, вход запуска которогосоединен с выходом признака равенстванулю содержимого вычитающего счетчика и первым входом второго элементаИЛИ, второй вход которого являетсявходом сброса устройства и соединенс входом записи вычитающего счетчика, 1 Оинформационные входы которого соединены с выходами соответствующих переключателей группы, а счетный входсоединен с выходом третьего элементаИЛИ, входами запуска второго генератора линейно изменяющегося напряжения и первого генератора одиночныхимпульсов, счетным входом суммирующего счетчика, вход сброса которогосоединен с выходом второго элементаИЛИ, информационные выходы суммирующего счетчика соединены с входами дешифратора, выходы которого соединеныс управляющими входами соответствующих ключей первой группы и с управляющими входами коммутатора, информационные входы которого соединеныс выходом первого генератора одиночных импульсов, информационные входывыходы коммутатора соединены с входами наборного поля моделей ветвей,выходы коммутатора соединены с входом усилителя-формирователя импульсных сигналов, выход которого соединенс входом установки триггера, входомостанова второго генератора линейноизменяющегося напряжения, входом запуска второго генератора одиночныхимпульсов, выход которого соединен спервым входом третьего элемента ИЛИ ивходом элемента задержки, выход кото"рого соединен с входом сброса триггера, прямой выход которого соединен суправляющими входами ключей второйгруппы, информационные входы. которых соединены с входом нулевого потенциала устройства, а выходы соединеныс соответствующими узлами моделируемого графа наборного поля моделейветвей, модели ветвей наборного полясоединяются между собою в соответствии с топологией исследуемого графа,модели ветвей, инцидентных выбранному узлу, соединяются с входами-выходами наборного поля моделей ветвей,выход второго генератора линейно изменяющегося напряжения соединен синформационными входами ключей первой группы, выходы которых соединеныс входами соответствующих накопительных элементов группы, второй входтретьего элемента ИЛИ является входом пуска устройства.1434452 цг Составитель О.ГречухинаРедактор Л.Веселовская Техред М,Дидык Корректор Л.Пилипенко Закаэ 5557/ сное 5 фическое предприятие, г. Ужгород, ул. Проектная, 4 Производственно-п Тираж 704НИИПИ Государственного кделам иэобретений иМосква, Ж-З 5, Раушск П митета СССР крытий наб., д.