Устройство для определения маршрута максимальной пропускной способности исследуемой сети

Устройство для определения маршрута максимальной пропускной способности исследуемой сети

Иллюстрации

Показать все

Реферат

 

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

СОЮЗ СОВЕТСНИХ

СОЦИАЛИСТИЧЕСНИХ

РЕСПУБЛИК (51)4 G 06 F 15 20 фЯГ,;0 11 h Я

)) ОПИСАНИЕ ИЗОБРЕТЕНИЯ

6mr

ГОСУДАРСТВЕННЫЙ НОМИТЕТ СССР

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИЙ

К ABTOPCHOMY СВИДЕТЕЛЬСТВУ (21) 3973385/24-24 (22) 10. 11.85 (46) 23.11.87. Бюл. Р 43 (72) Г.С.Колесник (53) 681.333 (088.8) (56) Авторское свидетельство СССР

Ф 940179, кл. G 06 G 7/122, 1980.

Авторское Свидетельство СССР

Р 1256042, кл. G 06 F 15/20, 1985.

„„SU 1354 1 А1 (54) УСТРОЙСТВО ДЛЯ ОПРЕДЕЛЕНИЯ МАРШРУТА МАКСИМАЛЬНОЙ ПРОПУСКНОЙ СПОСОБНОСТИ ИССЛЕДУЕМОЙ СЕТИ (57) Изобретение . относится к вычислительной технике и может быть использовано для решения на графах транспортных задач, задач оптимизации по сетям и т.п. Целью изобретения является повышение точности. Устройство

13 содержит вход 1, генератор 2 импуль-сов, распределитель 3 импульсов, блок

4 выбора максимального напряжения, группу элементов И 5, группу ключей

6, первый элемент ИЛИ 7, коммутатор

8, наборное поле 9, группу элементов

ИЛИ 10, группу индикаторных счетчиков 11, источник тока 12, реле 13, группу моделей 14 ребер„ в состав каждой из которых входит элемент индикации 15, группу выходов 16 номера последнего ребра, группу выходов 17 ребер одинаковой пропускной способности, группу информационных входов 18 устройства, второй элемент

ИЛИ 19. Существо изобретения состоит в нахождении единственного маршрута максимальной пропускной способности в случае отсутствия циклов в подграфе, индицированного элементами индикации 15, а в случае наличия циклов—

54201 в нахождении ребер, принадлежащих всей совокупности маршрутов максимальной пропускной способности и указания (с помощью счетчиков 11) вершин, участвующих в циклах подграфа, что позволяет пользователю при необходимости находить единственный маршрут по мнемосхеме графа. Кроме тог o устройство позволяет находить ребра одинаковой пропускной способности с последним включенным в топо-, логию графа ребром и затем находить другие маршруты такой же максимальной пропускной способности, заменяя модель последнего ребра поочередно другими ребрами такой же пропускной способности. Решение этих задач необходимо, например, при оптимизации распределения потоков информации по сетям связи, потоков транспорта по городским улицам и т.п. 1 ил.

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

Цель изобретения — повышение точности

На чертеже приведена функциональная схема устройства °

Устройство содержит вход 1 запуска устройства, генератор 2 импульсов, распределитель 3 импульсов, блок 4 выбора максимального напряжения, группу элементов И 5, группу ключей 6, первый элемент ИЛИ 7, коммутатор 8, наборное поле 9, группу элементов

ИЛИ 10, группу индикаторных счетчиков

11, источник 12 тока, реле 13, группу моделей 14 ребер, в состав каждой из которых входит элемент 15 индикации, группу выходов 16 номера последнего ребра, группу выходов 17 ребер одинаковой пропускной способности, группу информационных входов 18 уст26 ройства, второй элемент ИЛИ 19.

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

30 счетчики 11. В наборном поле 9 выход каждого i-ro (i=1,m, где m — число ребер графа) элемента И 5 соединяют с входами к-го и г-го элементов ИЛИ

10 (к и r — вершины i-го ребра гра- фа). При подаче на входы блока 4 постоянных напряжений положительной полярности он выдает на выход максимального напряжения напряжение положительной полярности, пропорциональное максимальному из входных напряжений, на тот из информационных выходов идентификации максимальных напряжений, который соответствует входу с наибольшим из входных напряжений,— напряжение положительной полярности, а на все остальные выходы — напряжение отрицательной полярности.

Предположим, что первоначально максимальным из входных напряжений является напряжение Е, приложенное на вход 18, тогда на т-м выходе группы информационных выходов идентификации максимальных напряжений блока 4 действует положительное напряжение, на остальных выходах группы — отрицательные напряжения, на выходе максимального напряжения блока 4 — напряжение, пропорциональное

3 135

Е . Соответственно иэ всех элементов

И 5 лишь на втором входе элемента

И 5„ присутствует разрешающий потенциал.

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

5„ и обусловливает включение ключа

6 . Ключ 6 срабатывает, выключает ключ 6,, отключая напряжение Е от входа блока 4, и замыкает ключ 6,, подключая т-е ребро графа в его топологию. Кроме того, импульс, с выхода элемента И 5 проходит через наборное поле 9 и элементы ИЛИ 10, соответствующие вершинам т-ro ребра, на входы соответствующих счетчиков

11, которые увеличивают свои показания на 1. После отключения напряжения Ет блок 4 выбирает следующее максимальное напряжение и выдает положительное напряжение уже на другой выход группы, а напряжение на выхбде максимального напряжения блока 4 скачком уменьшается »а величину, пропорциональную разности между величинами Е и очередного максимального напряжения. По мере работы устройства все большее число ребер подключается в топологию графа и, наконец, после срабатывания некоторого ключа 6 и подключения ребра 14П образуется цепь протекания тока источника 12.

Тогда зажигаются элементы 15 индикации и индицируют ребра маршрута максимальной пропускной способности,так как среди оставшихся невключеннымиребер ни одно не имеет большую пропускную способность. Срабатывает реле 13 и замыкает свои контакты, поэтому скачок с выхода максимального напряжения блока 4 поступает на вход останова генератора 2, останавливая работу устройства.

Кроме того, импульс с выхода элемента И 5„ прямоугольной формы и достаточной длительности успевает пройти через замкнувшийся контакт

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

4201

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

Iнз вход octGHQBG генератора 2 через элемент ИЛИ 19.

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

25 участвуют в циклах (например, если показания счетчика 11< равны двум, то начальная вершина учаСтвует в цикле) .

Если в графе остались не включенgp ные в топологию ребра с пропускной способностью, равной пропускной способности последнего (и-го) ребра, то в исследуемом графе могут быть и другие маршруты такой же максимальной пропускной способности. При необходимости их нахождения вначале определяют ребра равной пропускной способности с пропускной способностью последнего ребра, для чего вновь

40 подают сигнал на вход 1, и генератор

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

55 блока 4 не меняется, причем до тех пор, пока не будет отключено послед-. нее из максимальных (равных по величине) входных напряжений.

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

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

И, группу иэ m ключей, группу из m

5 13542

Поэтому при произведенном ранее отключении от входа напряжения Е„, соответствующего и-му ребру, включенному в топологию графа последним исУ

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

Поэтому при дальнейшей работе устройства импульсы распределителя 3 проходят через те элементы И 5, на вторые входы которых поступают положительные напряжения. Эти импульсы через замкнутые контакты 13 поступают на соответствующие информационные входы коммутатора 8 И проходят на соответствующие выходы 17, указывая номера ребер равной пропускной способности с п-м ребром. Когда при срабатывании определенного в-ro реле (в — последнее иэ напряжений, равных Е„) от входов блока 4 оислю- 25 чено напряжение Е, последнее среди. равных напряжений, на выходе максимального напряжения блока 4 происходит скачок напряжения, равный разности между Е„=Е и величиной следующего максимального напряжения. Этот скачок напряжения через замкнутый контакт 13 и элемент ИЛИ 19 проходит на вход останова генератора 2, прекращая работу устройства. Поступившие

35 при этом на соответствующие выходы

17 импульсы указывают ребра равной пропускной способности. Далее для нахождения новых маршрутов такой же максимальной пропускной способности отключают модель 14„ ребра и вместо нее по очереди оставляют включенной одну из моделей 14, соответствующих найденным ребрам одинаковой пропускной способности: при образовании цепи протекания тока источника 12 элементы 15 индикации отображают ребра другого маршрута максимальной пропускной способности.

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

i-го (i=1,2,...m) элемента И, второй вход которого подключен к 1-му информационному выходу блока выбора максимального напряжения, каждый

i-и информационный вход которого подключен к выходу х-го ключа группы, информационный вход которого является i-м входом группы информационных входов устройства, первый вывод управляющей обмотки реле через источник тока подключен к входам моделей ребер, образующих начальную вершину/ исследуемого графа, о т л и ч а ющ е е с я тем, что, с целью повыше= ния точности, в него введены коммутатор, наборное попе и группа индикаторных счетчиков, выход первого элемента ИЛИ подключен к управляющему входу коммутатора и к первому входу второго элемента ИЛИ, выход которого подключен к входу останова генератора импульса, выход окончания выбора блока выбора максимума через (ш+1) замыкающий контакт реле подключен к второму входу второго элемента ИЛИ, каждый i-й выход первой группы информационных выходов коммутатора подключен к i ìó входу группы входов первого элемента ИЛИ и является i-м выходом группы выходов определения номера последнего ребра исследуемого графа, каждый 1-й выход второй группы информационных выходов коммутатора является i-м выходом группы выходов определения номеров ребер одинакового веса, выход каждого i-ro элемента И группы подключен. к управляющему входу i-го ключа группы, к i-му входу группы входов наСоставитель Т.Сапунова

Техред А.Кравчук Корректор А.Обручар

Редактор Н.Тупица

Заказ 5695/44

Тираж 671 Подписное

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

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

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

7 1354201

8 борного поля.и к управляющему входу ходов наборного поля подключен к i-му ключа i-й модели ребра группы, вто- входу j-ro элемента ИЛИ группы (j= рой вывод управляющей обмотки реле =1,2,...,n, где и — число вершин исподключен к выходам моделей ребер, следуемого графа), выход каждого

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