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

 

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

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

Республик

ОП ИСА

ИЗОБРЕТ

К АВТОРСКОМУ СВИД (б1) Дополнительное к авт. сви (22) Заявлено 04.05.75 (21) 2 с присоединением заявки № (23) Приоритет.— (43) Опубликовано 05.04.77. Бю (45) Дата опубликования опис (51) М. Кл.е 6 06 6 7/122

Государственный комитет

Совета Министров СССР оо делам изобретений и открытий (53) УДК 681.14(088.8) (72) Автор;. изобретения

А. В, Холин (71) Заявитель (541 УСТРОЙСТВО ДЛЯ ОПРЕДЕЛЕНИЯ КРАТЧАЙШИХ

ПУТЕЙ НА ГРАФЕ

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

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

Оно содержит две различные электрические

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

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

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

Известно устройство для моделирования двунаправленной ветви сетевого графика, в котором в качестве основной модели ветви предлагаются регулируемые источники э.д,с. и диодный мост (1).

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

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

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

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

ЕСЕСЭЮЗНАЯ

gypped - " щ

628

553628

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

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

На коммутационном табло из элементов ветви: резисторов 1, 3, пороговых элементов 2, контактов

5 и лампочки накаливания 6 собирается схема, по топологии аналогичная исследуемому графу.

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

К исследуемым точкам графа, между которыми определяется кратчайший путь (точки 10 — 11 и

k2 — 13) подключают источник э.д.с, 4 и источник тока 7 соответственно. При линейном увеличении напряжения источника э.д.с. 4 от 0 до Е „< токи в ветвях увеличиваются пропорционально сопротивлениям ветвей R;> (длине ветви).

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

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

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

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

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

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

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

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

1, Авторское свидетельство СССР У 344463, МКИ 606 G7/48,,1970 г.

2. Авторское свидетельство СССР Nê 329539, МКИ G 06 G 7/48, 1970 (прототип) .

Составитель С, Громова

Техред И Асталош

1 оррект" р А. Власенко

РедактоР Л. Утехина

Филиал ППП" Патент ", г. Ужгород, ул, Проектная, 4

Заказ 194/39 Тираж 509 Подписное

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

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