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

 

(72) Авторы изобретения

Б. В. Волкодаев и А. В; Холин

t (4

3 с (71) Заявитель (54) УСТРОЙСТВО ДЛЯ ОИРЕДЕЛЕНИЯ КРАТЧАЙШИХ

ПУТEA HA ГРА Б

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

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

Однако известное устройство преднаэна чено только для определения кратчайших путей между заданной парой узлов и не позволяет проводить анализ ветвей, sxoдяших в этот путь.

Ф

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

) пути.

3 9401

Поставленная цель достигается reM, что в устройство введены формирователи одиночных сигналов, элементы И, усили.тели и дополнительные элементы индикации управляющий Выход порогоВого эле 5 мента каждой ветви через формирователь одиночных сигналов подключен к первому входу соответствующего элемента И, выход которого через усилитель соединен с входом дополнительного элемента инди- .10 кации соответствующей ветви, выход индикатора тока через . формирователь одиночного импульса подключен к;вторым входам всех элементов И.

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

На схеме показана первая граф-цепь

АВСД К, вторая граф-цепь АВ Д Й, эле- . мент 1 с регулируемым сопротивлением,, пороговый элемент 2 ветви, норыльно разомкнутый ключ 3, элемент 4 индикации ветви, входящий в кратчайший путь, регулируемый источник 5 напряжения, источник 6 тока, индикатор 7 тока, нормально замкнутые контакты 8 индикатора тока, управляющее устройство 9„ формирователь 10 одиночного сигнала, элемент И 11, усилитель 12, дополнительный элемент 13 индикации.

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

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

При этом соответствие между величиной сопротивления и "весом" ветви должно быть таким, чтобы увеличение сопротивления элемента 1 соответствовало умень шению емкости ветви, уменьшению надежности, увеличению длины, стоимости и

45 т. п.

При плавном увеличении Величины вы- ходиого напряжения . регулируемого источника 5 напряжения в моделях ветвей первой граф-цепи появляются токи, величина которых по отдельным ветвям определяет ся как топологией исследуемого графа, так и величинами сопротивлений элементов 1. По мере увеличения величины вы ходного напряжения величина тока в от- 55 дельных моделях ветвей первой граф-цепи достигает значения дср, где 3<р- величи- на тока срабатывания порогового элемен79 4 та 2. Соответствующие пороговые але- менты 2 срабатывают, обеспечивая замыкание соответствующих им ключей 3 и подачу управляющего сигнала на входы соответствующих формирователей 10 одиночных импульсов, с выхода которых одиночные импульсы поступают на входы элементов И 11. Однако пока замыкание ключей 3 не создаст замкнутую цепь для источника 6 тока, все алементы 4 индикации остаются выключенными, с обесточе = ного индикатора 7 тока не поступает управляющий сигнал на вторые входы элементов И 11, на выходах всех элемен тов И 11 отсутствует выходной сигнал.

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

3 срабатывание соответствующих элементов

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

Кроме того, индикатор 7 тока, сработав, подает управляющий сигнал на входы всех элементов И 11 управляющего устройст ва 9. В это время на вход соответствукьщего элемента И 11 с выхода формирова-. теля 10 одиночных импульсов„соответствующего пороговому элементу 2, сработавшему последним, поступает одиночный импульс. Соответствующий элемент И 11 срабатывает и подает управляющий сигнал на вход соответствующего усилителя 12, последний обеспечивает срабатывание соответствующего элемента 13 индикации.

Если под кратностью резервирования понимать отношение числа резервных элементоВ к обшему числу резервируемых (рабочих) элементов объекта, то пороговый элемент, принадлежащий максимально резервируемой ветви, сработает при бол шей величине выходного напряжения регулируемого источника напряжения, т. е. последним. Следовательно, в устройстве сработает элемент 13 индикации, принадлежащий ветви с наибольшим критерием резервирования.

5 . 9401 79 6

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

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

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

% 553628, кл. 8 06G 7/122 1976 (прототип) ИНИИПИ Заказ 4669/71 Гираж 731 Поа исное филиал ППП "Патент"; г. Ужгород, ул. Проектная, 4