Устройство для определения характеристик кратчайших путей на графе Советский патент 1986 года по МПК G06G7/122 

fO

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

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

Устройство для определения характеристик кратчайших путей содержит модели основных ветвей исследуемого графа 1, состоящие из переменных резисторов 1 и порогового элемента, выполненного на реле 3, модели вспомогательных ветвей исследуемого графа 4, состоящие из блоков 5 индикации, нормально разомкнутые контакты реле 6, источник 7 напряжения, ис- ,точник 8 тока, индикатор 9 тока, анапогово-цифровой преобразователь 1 и , группа элементов И-НЕ 11, п групп из m элементов И 12, группа регистров 13 памяти, выход 14 устройства.

Устройство для определения характеристик кратчайших путей работает следующим образом.

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

Этот процесс продолжается до тех пор, пока из блоков 5 индикации и контактов 6 пороговых элементов 3 не будет создана электрическая цепь для источника 8 тока, В результате ток источника 8 протечет не по всем вет- 5 вям, отмеченным пороговыми элементами 3, а только по тем из них, которые создали замкнутый путь для источника 8 тока,

В момент протекания тока через блоки 5 индикации, составляющие кратчайший путь, они вырабатывают и выдают с второго- выхода на первый вход соответствующих элементов Й-НЕ 11 постоянный единичный потенциал. Индикатор 9 тока в этот момент выдает одиночный импульс, который, поступая на вторые входы элементов И-НЕ 11, проходит только через те из них, на первые входы которых не подан постоянный единичный потенциал, т,е, через те элементы И-НЕ, соответствующие которым ветви не входят в состав кратчайшего пути. Импульс индикатора 9 то ка, пройдя через отдельные элементы

20

25

30

ны в начальный момент времени (напри- 35 И-НЕ 11, поступает на входы установмер, автоматически)., В начальный А и конечный В узлы исследуемого пути подключают регулируемый источник 7

т )

напряжения, в.точки А и В , соответствующие узлам А и В основного гра- фа, на индикационном графе подключают последовательно соединенные источник 8 тока и индикатор 9 тока. Пр начальном напряжении регулируемого источника 7 напряжения,подключенный к нему параллельно аналого-цифровой преобразователь 10 вырабатывает код, соответствующий началу отсчета.

При линейном увеличении напряжения источника 7 токи в ветвях увели- чиваются пропорционально сопротивлениям ветвей (весу ветви),

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

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

Этот процесс продолжается до тех пор, пока из блоков 5 индикации и контактов 6 пороговых элементов 3 не будет создана электрическая цепь для источника 8 тока, В результате ток источника 8 протечет не по всем вет- вям, отмеченным пороговыми элементами 3, а только по тем из них, которые создали замкнутый путь для источника 8 тока,

В момент протекания тока через блоки 5 индикации, составляющие кратчайший путь, они вырабатывают и выдают с второго- выхода на первый вход соответствующих элементов Й-НЕ 11 постоянный единичный потенциал. Индикатор 9 тока в этот момент выдает одиночный импульс, который, поступая на вторые входы элементов И-НЕ 11, проходит только через те из них, на первые входы которых не подан постоянный единичный потенциал, т,е, через те элементы И-НЕ, соответствующие которым ветви не входят в состав кратчайшего пути. Импульс индикатора 9 тока, пройдя через отдельные элементы

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

После считывания полученных данных из регистров 13 памяти выполняется кратковременное снятие общего напряжения питания (для разблокировки) , устройство возвращается в исходное состояние и готово к слецуюпа м измерениям.

Формул

изобретения

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

312

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

дам источника напряжения, каждый i-й вьгход аналого-цифрового преобразователя подключен к первому входу i-ro элемента И каждой из групп (i 1, 2., .m), вторые входы элементов И каждой j-й группы (где j 1,2...п) объединены и через второй нормально разомкнутый контакт реле j-й модели основной ветви исследуемого графа подключены к {первому информационному выходу блока индикации j-й модели вспомогательной ветви; выходы каждого i-ro элемента И каждой j-й группы подключены к входу i-ro разряда j-ro регистра памяти группы, выходы регистров памяти группы являются группой выходов устройства, второй информационный выход блока индикации j-й модели вспомогательной ветви подключен к первому входу j-ro элемента И-НЕ группы, выход которого подключен к (т+1)-му разряду j-ro регистра памяти блока памяти, вторые входы всех элементов И-НЕ группы объединены и подключены к выходу индикатора тока, выход индикатора тока подключен к входам установки в О регистров памяти группы.

Cmpoff . fy jif

Составитель Т.Сапунова Редактор А.Маковская Техред л.Олейник Корректор 0.Луговая

Заказ 55Тираж 671Подписное

ВНИИПИ Государственного комитета СССР

по делам изобретений и открытий 113035, Москва, Ж-35, Раушская наб., д. 4/5

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

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