Устройство для исследования параметров графов Советский патент 1988 года по МПК G06F15/173 

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

Цель изобретения - распшрение функциональных возможностей за счет определения длины минимального прос- того цикла, проходящего черкез любую выбранную вершину исследуемого графа. }5 На фиг.1 изоб1Уажена структурная схема устройства; на фиг. 2 - функ циональная схема коммутатора. Устройство содержит наборное поле 1 модели ветвей 2,.коммутатор 3, груп- 20 пу переключателей 4, первый 5, вто- рой 6 и третий 7 элементы ИЛИ, суммирующий 8 и вычитающий 9 счетчики, первый 10 и второй II генераторы линейно изменяющегося напряжения, 25 первый 12 и второй 13 генераторы одиночных импульсов, дешифратор 14, первую 15 и вторую 16 группы ключей, группу накопительных элементов 17, триггер 18, усилитель-формирователь ЗО 19 импульсных сигналов, элемент задержки 20, группу компараторов 21, блок 22 измерения и индикации

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

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

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

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

потенциалом О, а в другом положении - с. потенциалом 1.

Первый 10 и второй 11 генераторы линейно изменяющегося напряжения предназначены для выдачи линейно нарастающего напряжения при подаче на их вход запуска импульса. Причем при приходе на их. вход останова импульса нарастание напряжения на их выходе прекращается. Уровень данного напряжения в дальнейшем остается постоянным до прихода след: щего импульса запуска, после чего напряжение н выходе генератора линейно изменяющегося напряжения начинает опять нарастать с нуля.

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

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

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

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

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

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

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

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

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

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

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

0

0

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

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

5 первой группы 15 кл}очей открьгоается потенциалом логической единицы с со-, ответствующего выхода дешифратора 14 по управляющему входу, что обеспечивает поступление через его аналоговый вход линейно из меняющегося напряжения с выхода второго генератора 11 линейно изменяющегося напряжения на соответствующий накопительный элемент 17, заряжающийся до напряжения, присутствующего на выходе второго генератора 11 линейно изменяющегося напряжения в момент останова. Тем же импульсом, пришедшим с выхода усилителя-формирователя 19, в единичное состояние устанавливается триггер 18, который через вторую группу 16 ключей подключает к земле все верши-, ны исследуемого графа, кроме выбранной, тем самым исключая появление на группе Z входов-выходов коммутатора 3 остальных разнесенных во времени, импульсов.

Этот же импульс запускает второй генератор 13 одиночных импульсов, с выхода которого сформированный импульс поступает на вход элемента 20 задержки. С выхода элемента 20 задержки задержанный импульс поступает на вход установки в О триггера 18,

g который отключает от земли все

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

0

0

5

та ИЛИ 7, одновременно поступает на счетные входы вычитающего 9 и сзшми- рующего 8 счетчиков и на входы запуска второго генератора 11 линейно изменяющегося напряжения и первого генератора 12 одиночных импульсов. Вновь состояние вычитающего 9 и суммирующего 8 счетчиков изменяется. На выходе дещифратора 14 появляется соответствующий управляющий сигнал, и в коммутаторе 3 устанавливаются соответствующие соединения, Исследуемой становится следующая по порядку ветвь графа..Зондирующий импульс с запустившегося первого генератора 12 одиночных импульсов, пройдя через ском- мутированное соединение коммутатора 3 на соответствующий из группы входко изменяющееся -напряжение, которое поступает на вторые входы группы компараторов 21J на первые входы кото- g рых поступают напряжения с выходов соответствующих накопительных элементов 17, Как только напряжение с выхода первого генератора 10 линейно изменяющегося напряжения сравняется с

10 напряжением какого-либо из накопительных элементов 17 (с наименьщим из всех всех напряжений), на выходе соответствующего компаратора 21 появляется импульс, который пройдя через первый

15 элемент ИЛИ 5, поступает на вход останова первого генератора 10 линейно изменяющегося напряжения. На выходе последнего фиксируется напряжение, соответствующее длине минималь выход коммутатора 3 через контакты 20 ного цикла, проходящего через выбран- наборного поля 1 поступает в очеред- ную верщину исследуемого графа. Данную исследуемую модель ветви. Далее ное напряжение поступает на вход бло- весь процесс вычислений идет аналогич- ка 22 измерения и индикации и вьщает- но описанному выше, в результате чего ся на его индикатор в удобной для об- заряжается следующий элемент из груп- 5 работки форме. пы накопительных элементов 17. Напряжение на нем равно напряжению на выходе второго генератора 11 линейно из меняющегося напряжения в момент его

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

Устройство для исследования параметров графов, содержащее коммутатор.

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

По достижении вычитающим счетчиком 9 нулевого состояния, на его выходе появляется импульс, который проходя через второй вход второго эле- мента ИЛИ 6, сбрасывает в О состояние суммирующего счетчика, тем самым устраняя все соединения в коммутаторе 3. Этот же импульс поступает на вход запуска первого генератора О лнейно изменяющегося напряжения. На его выходе начинает нарастать линейко изменяющееся -напряжение, которое поступает на вторые входы группы компараторов 21J на первые входы кото- рых поступают напряжения с выходов соответствующих накопительных элементов 17, Как только напряжение с выхода первого генератора 10 линейно изменяющегося напряжения сравняется с

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

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

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

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

Устройство для исследования параметров графов, содержащее коммутатор.

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

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

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

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

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

Фиг. 2

Изобретение относится к вычислительной технике и может быть использовано для определения длины Минимального простого цикла, проходящего через любую выбранную вершину графа, при анализе сетей связи, распределенных информационно-вычислительных сетей и других сложных систем, смоделированных на графах. Цель изобретения - расширение.функциональных возможностей за счет определения длины минимального простого цикла, проходящего через любую выбранную вершину исследуемого графа. Она достигается тем, что в устройство, содержащее коммутатор 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 . й«/