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

 

Изобретение относится к вычислительной технике и может быть использовано для определения длины Минимального простого цикла, проходящего через любую выбранную вершину графа, при анализе сетей связи, распределенных информационно-вычислительных сетей и других сложных систем, смоделированных на графах. Цель изобретения - расширение.функциональных возможностей за счет определения длины минимального простого цикла, проходящего через любую выбранную вершину исследуемого графа. Она достигается тем, что в устройство, содержащее коммутатор 3, элемент ИЛИ 5, генератор 10 линейно изменяющегося напряжения, группу накопительных элементов 17, группу компараторов 21, дополнительно введены наборное поле 1 с моделями ветвей 2, группа переключателей 4, второй 6 и третий 7 элементы ИЛИ, суммирующий 18 и вычитающий 9 счетчики, второй генератор 11 линейно изменяющегося напряжения , первый 12 и второй 13 генераторы одиночных тпульсов, дешифратор 14, первая 15 и вторая 16 группы п-1 ключей, триггер 18, усилительформирователь 19 импульсньпс сигналов, элемент задержки 20, блок 22 измерения и индикации. 2 ил. & G iS . й«/

СООЗ СОВЕТСНИХ

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

РЕСПУБЛИН (19) (И) (5g 4 G 06 F 15/20

ГОСУДАРСТВЕННЫЙ НОМИТЕТ СССР

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИЙ (21) 4230949/24-24 (22) 17.04.87 (46) 30.10.88. Бюл. Р 40 (72) Е.И,Бороденко, А.B..Биков, В.В.Верияскин, N,В.Мельников, В.Е.Назаренко, Л.Г.Подзубанов и В.А.Синица (53) 681 ° 325 (088.8) (56) Авторское свидетельство СССР

552617, кл. G 06 G 7/122, 1977.

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

У 1241266, кл. С 06 С 7/48, 1984. (54) УСТРОЙСТВО ДЛЯ ИССЛЕДОВАНИЯ ПА"

РАМЕТРОВ ГРАФОВ (57) Изобретение относится к вычислительной технике и может быть использовано для определения длины минимального простого цикла, проходящего через любую выбранную вершину графа, при анализе сетей связи, распределенных информационно-вычислительных сетей и других сложных систем, смоделированных на графах. Цель изобретения — расширение функциональных возможностей за счет определения длины минимального простого цикла, проходящего через любую выбранную вершину исследуемого графа, Она достигается тем, что в устройство, содержащее коммутатор 3, элемент ИЛИ 5, генератор 10 линейно изменяющегося напряжения, группу накопительных элементов 17, группу компараторов

21, дополнительно введены. наборное поле 1 с моделями ветвей 2, группа переключателей 4, второй 6 и третий

7 элементы ViJIH, суммирующий 18 и вычитающий 9 счетчики, второй генератор 11 линейно изменяющегося напряжения, первый 12 и второй 13 генераторы одиночных импульсов, дешифратор 14, первая 15 и вторая 16 группы п-1 ключей, триггер 18, усилительформирователь 19 импульсных сигналов, элемент задержки 20, блок 22 измерения и индикации. 2 ил.

1434452

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

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

На фиг.l изображена структурная схема устройства; на фиг. 2 - функ циональная схема коммутатора.

Устройство содержит наборное поле 1 модели ветвей 2,,коммутатор 3, груп- 20 пу переключателей 4; первый 5, второй 6 и третий 7 элементы ИЛИ, суммирующий 8 и вычитающий 9 счетчики, первый 10 и второй 11 генераторы линейно изменяющегося напряжения, 25 первый 12 и второй 13 генераторы оди" ночных импульсов, дешифратор 14, первую 15 и вторую 16 группы ключей, группу накопительных элементов 17, триггер-18, усилитель-формирователь 30

19 импульсных сигналов, элемент задержки 20, группу компараторов 21, блок 22 измерения и индикации.

Наборное поле l представляет собой панель с контактами, приспособленною для подключения моделей ветвей исследуемого графа в соответствии с его топологией, Модели ветвей представляют собой

4-полюсники, включающие в себя регулируемые линии задержки. При помощи таких регулируемых линий задержки, соединенных в соответствии с тополо гней графа, задаются "aeca ветвей 45 исследуемого графа.

Коммутатор 3 содержит аналоговые ключи 23 и 24, инверторы 25 и вентильные диоды 26.

Переключатели 4 предназначены для набора на них двоичного числа, на единицу большего количества ветвей, инцидентных выбранной вершине исследуемого графа. Это могут быть, напри" мер, двухпоэиционные переключатели, которые в одном положении соединяют соответствующие информационные входы вычитающего счетчика 9 (см.фиг.l) с, потенциалом "0", а в другом поло жении — с потенциалом "1", Первый 10 и второй 11 генераторы линейно изменяющегося напряжения предназначены для выдачи линейно нарастающего напряжения при подаче на нх вход запуска импульса. Причем при приходе на их вход останова импульса нарастание напряжения на их выходе прекращается. Уровень данного напряжения в дальнейшем остается постоянным до прихода следующего импульса запуска, после чего напряжение на выходе генератора линейно изменяющегося напряжения начинает опять нарастать с нуля.

Первый генератор 12 одиночных импульсов предназначен для генерации зондирующего импульса при подаче на его вход импульса запуска с выхода третьего элемента ИЛИ 7.

Генератор представляет собой одновибратор, вырабатывающий импульс с некоторой задержкой, за время которой в коммутаторе 3 устанавливаются необходимые соединения.

Вторая группа !6 кличей предназначена для соединения в определенные моменты времени "земли" с контактами наборного поля (вершинами) с целью прекращения всех процессов распространения электрических сигналов в схеме, собранной из моделей ветвей в соответствии с топологией графа.

Усилитель-формирователь 19 импульсных сигналов предназначен для восстановления и усиления формы первого импульса (отклика), пришедшего с исследуемой схемы, составленной из моделей ветвей 2 в соответствии с, топологией графа.

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

На наборном поле I с помощью моделей ветвей 2 собирается схема в соответствии с топологией графа. В каждой модели ветви устанавливается ее

"вес" с помощью соответствующей регулируемой линии задержки. Входы-выходы моделей ветвей графа, инцидентных выбранной вершине, через контакты наборного поля 1 подключаются к входам-выходам коммутатора 3, На переключателях 4 набирается число, на единицу большее количества ветвей, инцидентньгх выбранной верз 14 шине, в двоичном коде. После этого на вход сброса устройства подается импульс сброса, который, проходя через второй элемент ИЛИ 6, устанавливает суммирующий счетчик 8 в нулевое состояние. Тот же импульс записывает в вычитающий счетчик 9 число, набранное на переключателях 4, На этом подготовительная часть завершается.

Работа устройства начинается с подачи на пусковой вход устройства импульса запуска, который, проходя через третий элемент ИЛИ 7, одновременно поступает на счетные входы вычитающего 9 и суммирующего 8 счетчиков, на входы запуска второго генератора 11 линейно изменяющегося напряжения и первого генератора 12 одиночных импульсов °

При этом состояние вычитающего счетчика 9 уменьшается на единицу, а суммирующего 8 увеличивается на единицу. Состояние суммирующего счетчика 8 в двоичной форме подается на входы дешифратора 14 ° На соответствующем выходе дешифратора 14 появляется потенциал логической единицы, поступающий на соответствующий управляющий вход коммутатора 3, в результате чего происходит коммутация. Остальные входы-выходы настраиваются на прием электрических сигналов от схемы, набранной на наборном поле.

После этого с первого генератора 12 одиночных импульсов на первый вход коммутатора 3 поступает зондирующий импульс и, пройдя через скоммутированное соединение коммутатора 3, поступает на соответствующий вход-выход последнего, а далее через контакты наборного поля I в исследуемую модель графа.

Проходя через все возможные пути, зондирующий импульс задерживается на величину, эквивалентную сумме "весов" ветвей графа, входящих в простые циклы, проходящие через выбранную вершину графа, Так как простые циклы имеют различный суммарный "вес" ("веса" некоторых циклов будут совпадать, что несущественно), то в моделях ветвей 2 графа, подключенных через контакты наборного поля 1 к входам-выходам коммутатора 3, появляются разнесенные по времени импульсы (отклики зондирующего импульса) . Время, прошедшее с момента подачи зондирующего импульса до момента поступления

34452

1О

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

его форму. Поступая на вход останова второго генератора 11 линейно изменяющегося напряжения, который был запущен в момент подачи зондирующего импульса, данный импульс останавливает его. На выходе второго генератора ll линейно изменяющегося напряже" ния будет зафиксировано напряжение, эквивалентное полученному промежутку времени. Соответствующий ключ из первой группы 15 ключей открывается потенциалом логической единицы с со-. ответствующего выхода дешифратора !4 по управляющему входу, что обеспечивает поступление через его аналоговый вход линейно изменяющегося напряжения с выхода второго генератора 11 линейно изменяющегося напряжения на соответствующий накопительный элемент 17, заряжающийся до напряжения, присутствующего на выходе второго генератора ll линейно изменяющегося напряжения н момент останова. Тем же импульсом, пришедшим с выхода усилителя-формирователя 19, в единичное состояние устанавливается триггер 18, который через вторую группу 16 ключей подключает к "земле" все вершины исследуемого графа, кроме выбранной, тем самым исключая появление на группе Z входов-выходов коммутатора 3 остальных разнесенных во вре> мени, импульсов.

Этот же импульс запускает второй генератор 13 одиночных импульсов, с выхода которого сформированный импульс поступает на вход элемента 20 задержки. С выхода элемента 20 задержки задержанный импульс поступает на вход установки в "0" триггера 18, который отключает от "земли все вершины исследуемого графа, тем самым обеспечивая следующий цикл вычислений. Этот же импульс, пройдя через второй вход третьего элеменно изменяющееся напряжение, которое поступает на вторые входы группы компараторов 21, на первые входы которых поступают напряжения с выходов еоответствующих накопительных элементов 17. Как только напряжение с выхода первого генератора 10 линейно изменяющегося напряжения сравняется с напряжением какого-либо из накопительных элементов 17 (с наименьшим из всех всех напряжений), на выходе соответствующего компаратора 21 появляется импульс, который, пройдя через первый элемент ИЛИ 5, поступает на вход останова первого генератора 1О линейно изменяющегося напряжения. На выходе последнего фиксируется напряжение, соответствующее длине минимального цикла, проходящего через выбранную вершину исследуемого графа. Данное напряжение поступает на вход блока 22 измерения и индикации и выдается на его индикатор в удобной для обработки форме. формула изобретения устройство для исследования параметров графов, содержащее коммутатор, группу компараторов, группу накопительных элементов, первый генератор линейно изменяющегося напряжения, элемент ИЛИ, выход которого соединен с входом останова первого генератора линейно изменяющегося напряжения, выход каждого накопительного элемента группы соединен с первым входом соответствующего компаратора группы, выход которого соединен с соответствующим входом элемента ИЛИ, вторые входы компараторов группы соединены с выходом генератора линейно изменяющегося напряжения, о т л и ч а ю,щ е е с я тем, что, с целью расширения функциональных возможностей за счет определения длины минимального простого цикла, проходящего через любую выбранную вершину исследуемого графа, в него введены второй и третий элементы ИЛИ, группа переключателей, суммирующий и вычитающий счетчики, наборное поле моделей ьетвей, дешифратор, первый и второй генераторы одиночных импульсов, второй генератор линейно изменяющегося напряжения, первая и вторая группы xmoчей, триггер, усилитель-формирователь импульсных сигналов, элемент задержки, блок измерения и индикации, По достижении вычитающим счетчиком 9 нулевого состояния, на его вы- 80 коде появляется импульс, который,проходя через второй вход второго элемента ИЛИ 6, сбрасывает в "О" состояние суммирующего счетчика, тем самым устраняя все соединения в коммутаторе 3. Этот же импульс поступает на вход запуска первого генератора 10 линейно изменяющегося напряжения. На

его выходе начинает нарастать линей5 1ц344 та ИЛИ 7, одновременно поступает на счетные входы вычитающего 9 и суммирующего 8 счетчиков и на входы запуска второго генератора 11 линейно из5 меняющегося напряжения и первого генератора 12 одиночных импульсов.

Вновь состояние вычитающего 9 и суммирующего 8 счетчиков изменяется ° На выходе дешифратора 1ч появляется со- 10 ответствующий управляющий сигнал, и в коммутаторе 3 устанавливаются соответствующие соединения, Исследуемой становится следующая по порядку ветвь графа..Зондирующий импульс с запус- 15 тившегося первого генератора 12 одиночных импульсов, пройдя через скоммутированное соединение коммутатора 3 на соответствующий иэ группы вход- выход коммутатора 3, через контакты 20 наборного поля I поступает в очередную исследуемую модель ветви. Далее весь процесс вычислений идет аналогично описанному выше, в результате чего заряжается следующий элемент из груп- 25 пы накопительных элементов 17. Напряжение на нем равно напряжению на выходе второго генератора 11 линейно изменяющегося напряжения в момент его останова и соответствует длине мини- 30 мального цикла, содержащего данную очередную исследуемую ветвь, инцидентную выбранной вершине исследуемого графа. Данные циклы вычислений повторяются до тех пор, пока состояние вычитающего счетчика 9 не станет равным нулю. В этот момент на всех накопительных элементах 17 в виде напряжений содержится информация о длинах минимальных циклов, содержа- 40 щих все соответствующие им ветви, инцидентные выбранной вершине графа.

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

1434452 вход которого соединен с выходом первого генератора линейно изменяющегося напряжения, вход запуска которого соединен с выходом признака равенства нулю содержимого вычитающего счетчика и первым входом второго элемента

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

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

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

1434452

Фцг. 2

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

Редактор Л.Веселовская Техред М.Дидык Коррек тор Л. Пилипенко

Заказ 5557/52 Тираж 704 Подписное

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

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

Производственно-полиграфическое предприятие, r. Ужгород, ул. Проектная, 4