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

(54) УСТРОЙСТВО ДЛЯ ОПРЕДЕЛЕНИЯ КРАТЧАЙШИХ ПУТЕЙ НА ГРАФЕ

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

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

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

Недостаток такого устройства состоит в низком быстродействии.

Целью изобретения является гювышенИе быстродействия устройства.

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

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

Оно содержит две различные электрические цепи, идентично соединенные согласно топологии исследуемого графа. Первая цепь, содержащая переменные резисторы 1, пороговый элемент 2, на который подается напряжение с измерительных резисторов 3, и регулируемый источник ЭДС 4, служит для определения ветвей исследуемой сети с максимальным током.

Вторая цепь содержит нормально разомкнутые контакты 5 порогового элемента 2, блоки индикации но числу ветвей графа, (в данном случае блоком индикации 6, принадлежащим кратчайшему

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

Устройство работает следующим образом. На коммутационном табло из элементов ветви: 3HCTOjpoB 1, 3, пороговых элементов 2, контактов 5 и лампочки накаливания 6 собирается схема, по топологии аналогичная исследуемому графу.

На переменных резисторах 1 устанавливают значения, пропордаональные длине ветви графа (расстоянию между вершинами, стоимости связывающей линии и т.п.).

к исследуемым точкам графа, между которыми определяется кратчайший путь (точки 10-11 и 12-13) подключают исто1тик э.д.с. 4 и источник тока 7 соответственно. При линейном увеличении напряжения источ1шка э.д.с. 4 от О до Емак токи в ветвях увеличиваются пропорционально сопротивлениям ветвей RIJ (длине ветви).

В отдельных ветвях цепи ток достигает значения Y , при котором срабатывает пороговый элемент 2, замыкающий свой контакт 5 в соответствующей ей параллельной цепи до тех пор, пока из лампочек 6 и контактов 5 пороговых элементов 2 не будет создана электрическая цепь для источника тока 7. В результате ток течет не по всем ветвям, отмеченным пороговыми элементами 2, а только nq тем из них, которые создали сквозную цепь для источника тока 7. Лампочки в зтих ветвях горят, отмечая кратчайший пут. между заданными точками 12-13, причем ток в этой цепи не зависит от числа последовательно включенных ламп (в цепи с источником тока величина тока не зависит от величины нагрузки). Наличие тока в цепи с лампами накалива1шя (12-13) отмечается реле 8, которое отключает от цепи (10-11) источник э.д.с. 4, что предотвращает дальнейшее увеличение тока и пО

явление ложных цепей кратчайшего пути. Пороговые элементы 2 при этом остаются заблокированными.

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

Преимущество предлагаемого устройства состоит в том, что для определения кратчайшего пути не требуется перебор и поставленная задача решается практически мгновенно.

Кроме того, в предлагаемом устройстве использованы на всю схему один источник э.д.с. и один ИСТОЧ1ШК тока.

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

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

Источники информации, принятые во внимание при экспертизе:

/

/

/ , У

/

т -

/

N

X у V

/

/ /

/X/