Устройство для определения кратчайших путей на графе

 

" > -ь "я @" гко r -: < и I : ;=. с яqyГх м»„

Соез Советскою

Социалистический

Республнк

<»>651358 (6l) Дополнительное к авт. саид-ву N 553628 (22) Заявлено 17 11.77 (21) 2545691/18-24 е присоединением заявки № (23) Приоритет

В (5l) М. Кл.

G 06 G 7/122

1 аеудврственный нюютет

СИР на делам нзебретеннй и атнрмтнй

Опубликовано 05.03.79, Бюллетень № 9 (53) УДК

681.333 (088.8) Дата опубликования описания 05.03,79 (72) Авторы изобретения

Б. В. Волкодаев, А.M. Кошель и А. В. Холин (7l) Заявитель (54) УСТРОЙСТВО ДЛЯ ОПРЕДЕЛЕНИЯ КРАТЧАЙШИХ ПУТЕЙ

НА ГРАФЕ

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

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

Однако точность работы и быстродействйе такого устройства недостаточны из-за отсутствия автоматйческого формирования и ввода весов в модели ветвей в соответствии с реальной ситуацией на моделируемой сети.

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

Структурная схема устройства представлена на чертеже.

Оно содержит две различные электрические цепи, идентично соединенные согласно топологии исследуемой сети.

Первая цепь содержит в каждой ветви пороговый элемент l, переменный резистор 2, блок 3

??НИИПИ Заказ 807/46

Тирам 779 Подписное

Филиал ППП "Патент", r Veгоpол, ул. Проектная, 4

3 6 управления весом ветви, шифратор 4 и группы датчиков 5 состояния каналов ветви.

В узловых точках первая цепь содержит источник 6 напряжения и контакт 7.

Вторая цепь содержит в каждой ветви кон. такт 8 порогового элемента 1 и блок индикации

9, а в узловых точках — источник 10 тока и индикатор тока 11.

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

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

???ифратор 4 определяет текущий вес ветви и выдает сигнал на блок 3, который изменяет величину сопротивления переменного резистора 2 в соответствии с реальным, текущим состоянием каналов ветви.

К исследуемым узловым точкам графа, между которыми определяется оптимальный путь, подключаются источники 6 н 10 соответственно.

При увеличении напряжения источника 6 токи в ветвях первой цепи увеличиваются пропорционально проводимости переменных резисторов 2.

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

Как только из блоков индикации 9 и контактов 8 элементов 1 будет создана электрическая ,у. г

l /

51358 Я цепь для источника 10 потечет ток по всем ветвям оптимального пути, блоки индикации 9 зафиксируют оптимальный путь между исследуемыми точками графа и сработает индикатор тока 11, ч который контактом 7 отключит от первой цепи источник 6, Элементы ? при срабатывании самоблокируются,поэтому для превращения устройства в исходное состояние блокировку необходимо

?О снять.

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

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

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

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