Устройство для определения маршрута максимальной пропускной способности исследуемой сети Советский патент 1987 года по МПК G06F15/173 

содержит вход 1, генератор 2 импуль-. сов, распределитель 3 импульсов, блок 4 выбора максимального напряжения, группу элементов И 5, группу ключей 6, первый элемент ИЛИ 7, коммутатор 8, наборное поле 9, группу элементов ИЛИ 10, группу индикаторных счетчиков 11, источник тока 12, реле 13, группу моделей 14 ребер, в состав каждой из которых входит элемент индикации 15, группу выходов 16 номера последнего ребра, группу выходов 17 ребер одинаковой пропускной способности, группу информационных входов/ 18 устройства,второй элемент ИЛИ 19, Существо изобретения состоит в нахождении единственного маршрута максимальной пропускной способности в случае отсутствия циклов в подграфе, индицированного элементами индикации 15, а в случае наличия циклов 1

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

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

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

Устройство содержит вход 1 запуска устройства, генератор 2 импульсов распределитель 3 импульсов, блок 4 выбора максимального напряжения, группу элементов И 5, группу ключей 6, первый элемент ИЛИ 7, коммутатор 8, наборное поле 9, группу элементов ИЛИ 10, группу индикаторных счетчико 11, источник 12 тока, реле 13, группу моделей 14 ребер, в состав каждой из которых входит элемент 15 индика- 1ЩИ, группу выходов 16 номера последнего ребра, группу выходов 17 ребер одинаковой пропускной способности, группу информационных входов 18 устройства, второй элемент ИЛИ 19.

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

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

0

5

0

5

0

счетчики 11. В наборном поле 9 выход каждого i-ro (,m, где m--число ребер графа) элемента И 5 соединяют с входами к-го и г-го элементов ИЛИ 10 (к и г - вершины i-ro ребра гра - фа). При подаче на входы блока 4 постоянных напряжений положительной полярности он выдает на выход максимального напряжения напряжение положительной полярности, пропорциональное максимальному из входных напряжений, на тот из информационных выходов идентификации максимальных напряжений, который соответствует входу с наибольшим из входных напряжений, - напряжение положительной полярности, а на все остальные выходы - напряжение отрицательной полярности.

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

R. Соответственно из всех элементов И 5 лишь на втором входе, элемента И 5 присутствует разрешающий потенциал.

Подачей сигнала на вход 1 запускают генератор 2, под воздействием импульсов которого распределитель 3 поочередно выдает на свои выходы пря- ; моугольные импульсы, из которых только импульс с т-го выхода распреде- лителя 3 проходит через -элемент И 5 и обусловливает включение ключа 6. Ключ 6 срабатывает, выключает ключ 6т, , отключая напряжение Е от входа блока 4, и замыкает ключ 6, , подключая т-е ребро графа в его топологию. Кроме того, импульс,с выхода элемента И 5 проходит через наборное поле 9 и элементы ИЛИ 10, соответствующие вершинам т-го ребра, на входы соответствующих счетчиков 11, которые увеличивают свои показания на 1. После отключения напряжения E-f блок А выбирает следующее максимальное напряжение и вьщает положительное напряжение уже на другой выход,группы, а напряжение на выхоЕсли в графе остались не включен

де максимального напряжения блока 4

скачком уменьшается на величину, про- зо ью в топологию ребра с пропускной

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

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

54201

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

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

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

Если в графе остались не включен5

0

5

0

5

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

5

Поэтому при произведенном ранее OTKnio4e niH от входа напряжения Е, , соответствующего п-му ребру, включен ному в топологию графа последним, ис чезает положительное напряжение на п-м выходе группы блока , а напряжение на выходе максимального напряжения блока 4 не изменяется при наличии на его входе нескольких таких же по величине напряжений, как Е,,. Поэтому при дальнейшей работе устройства импульсы распределителя 3 проходят через те элементы И 5, на вторые входы которых поступают положительные напряжения. Эти импульсы через замкнутые контакты 13 поступают на соответствующие информационные входы коммутатора 8 и проходят на соответствующие выходы 17, указывая номера ребер равной пропускной способности с п-м ребром. Когда при срабатывании определенного в-го реле (в - последнее из напряжений, равных Е) от входов блока 4 отжлю- чено напряжение Ец, последнее среди. равных напряжений, на выходе максимального напряжения блока 4 происходит скачок напряжения, равный разности между Е,ЕЗ и величиной следующего максимального напряжения. Этот скачок напряжения через замкнутый контакт 13 и элемент ИЛИ 19 проходит на вход останова генератора 2, прекращая работу устройства. Поступившие при этом на соответствующие выходы 17 импульсы указывают ребра равной пропускной способности. Далее для нахолодения новых маршрутов такой же максимальной пропускной способности отключают модель I4f, ребра и вместо нее по очереди оставляют включенной одну из моделей 14, соответствующих найденным ребрам одинаковой пропускной способности: при образовании цепи протекания тока источника 12 элементы 15 индикации отображают ребра другого маршрута максимальной пропускной способности.

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

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

542016

элементов ИЛИ, первый и второй элементы ИЛИ, источник тока, реле с

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

пульсов подключен к первому входу

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

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

1354201°

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

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