Устройство для определения экстремальных путей сетевых графов

СОЮЗ СОВЕТСНИХСОЦИАЛИСТИЧЕСКИХРЕСПУ БЛИН А 1)4 С 06 Р 15 20 ОПИСАНИЕ ИЗОБРЕТЕНК Д ВТОРСКОМУ СВИДЕТЕЛЬСТВУ.Мильк ельство 15/20, ство С 15/20,СССР1984.СР1986. АФОВ ие"Фз ша стреью идлины)щих- рас- жностей я наряГОСУДАРСТ 8 ЕННЫЙ НОМИТЕТ СССР ПОДБЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИ(54) УСТРОЙСТВО ДЛЯ ОПРЕДЕЛЕЭКСТРЕМАЛЬНЫХ ПУТЕЙ СЕТЕВ(57) Изобретение относится к лительной технике и позволяет задачи определения путей с эк мальной пропускной способност путей экстремального веса ( на сетевых графах, не содержа кратных дуг. Цель изобретения ширение Функциональных возмо устройства за счет определени ду с путями экстремальной пропускной способности также путей экстрамаль-. ной длины (массы). Устройство состоит из модели графа 1 и блока управления 2. Модель графа 1 содержит модели ветвей 3 (МВ), каждая из которых состоит из счетчика, трех ключей, элемента индикации, диода, элемента ИЛИ, Блок управления содержит генератор импульсов 11, счетчик 12, три ключа 13, 14, 15 и два диода 20, 21. Работа устройства основана на последовательном"включении" МВ в соответствии с алгоритмом определения экстремальных путей, пока "включен одной или нескольких МВ не обеспечит путь из начальной вершины чере "включение МВ в конечную вершину графа. Топология пути индицируется элементами индикации МВ, а пропуск- ф ф ная способность или длина (масса) пути определяется по счетчику блока управления. 2 ил.4 ьИзобретение относится к вычислительной технике и может быть использовано при построении специализированных вычислительных устройств для решения задач определения экстремальных путей пути с минимальной пропускной способностью, пути с максимальной пропускной способностью, пути минимальной массы, кратчайшего, и критического пути) в ориентированных сетевых графах.Цель изобретения - расширение функциональных возможностей устройства за счет определения наряду с путями экстремальной пропускной способ,ности также пути экстремальной длины (массы).На фиг.1 приведена функциональная схема устройства; на фиг.2 - функциональная схема модели ветви,Устройство содержит модель графа 1 и блок 2 управления. Модель графа 1 предназначена для задания топологии и пропускных способностей 1 длин) дуг моделируемого графа, а также индикации определяемого пути. Модель графа 1 содержит модели ветвей 3 .1=0 п 1 3=1+1 пу где (и +1) - число вершин исследуемого графа (индексы модели ветви соответствуют индексам дуги, соединяющей -ю вершину с 3-й). Все модели ветвей одинаковы, и Ц-я модель ветви содержит счетчик 4 импульсов, ключ 5, элемент 6 индикации (светодиод), диод 7, элемент ИЛИ 8, ключ 9 и ключ 10.Блок 2 предназначен для Фиксирования значения пропускной способнос" ги или длины найденного экстремального пути, задания режима работы И подачи сигнала на.начало решения. Блок 2 содержит генератор 11 импульсов, счетчик 12, ключи 13" 15, выключатель 16, кнопочный вьпаючатель 17, выключатели 18 и 19 и,циоды 20 и 21.Устройство работает в двух режимах - режиме определения путем экстремальной пропускной способности и режиме определения экстремальных : путей.Перед определением пути с максимальной пропускной способностью счетчики 4 моделей ветвей 3 устанавливаются в состояние Ч, равное или пропорциональное пропускной способности ,1-й дуги, если она есть в исследуемой графе, или в состояние Ч, =О, если ,1-я дуга в графе отсутствует, В блоке управления включается выключатель 19, чем определяется выбор первого режима работы устройства, При этом напряжение от шины питания поступает че.рез контакты выключателя 19 на управляющий вход ключа 15 и катод диода 20, с анода которого напряжение поступает на соответствующий выход блока управления и далее через вход модели графа на соответствующий вход моделей ветвей 3 , 1 = 1,п.Решение начинается включением выключателя 16 блока 2. При этом напряжение от шины питания через контакты выключателя 16 поступает на информационный вход ключа 13. С информационного выхода ключа 13 напряжение поступает на управляющий вход генератора 11 импульсов, который при этом начинает вырабатывать импульсы, поступающие с выхода генератора на счетный вход счетчика 12 и информационные входы ключей 14 и 15. С информационного выхода ключа 15 импульсы через соответствующие выход блока 2 и вход модели графа 1 поступают на один вход элементов ИЛИ 8 всех моделей ветвей 3;=О,п, 1 = 1,п. С выходов элементов ИЛИ 8 всех моделей, ветвей импульсы поступают на счетный вход счетчиков 4 этих моделей ветвей.При поступлении на счетчик 4 модели ветви 3 " (И-Ч " 7 импульсов (Н - ем 1)кость счетчиков 4) на выходе счетчи ка этой модели ветви появляется сигнал высокого уровня, сигнализирующий о его переполнении. Это сигнал поступает на управляющий вход ключа 5 данной модели ветви, а через разделительный диод 7 - на ключ 9 этой модели ветви и всех остальных моделей ветвей, соответствующих дугам моделируемого графа, входящим в 3-ю вершину. При этом вход модели ветви 3; через светодиод 6 и информацион 1 1ную цепь ключа 5 соединяется с ее соответствующим выходом, что свидетельствует о включении данной модели ветви. По мере включения все большего числа моделей ветвей включение одной или нескольких моделей ветвей обеспечивает с ранее включенными моделями ветвей путь из начальной вершины в конечную. При этом создается цепь, соединяющая шину пимационного выхода которого напряжение поступает на управляющий вход генератора 11 импульсов. Последний начинает вырабатывать импульсы, поступающие через информационную цепь ключа 14 и соответствующий выход блока 2 на входы моделей ветвей Зо0 В 1=1,п, соответствующих дугам, исходящим из начальной вершины моделируемого графа. На другой вход этих моделей ветвей поступает напряжение с выхода блока 2 Это напряжение через информационную цепь ключа 9 моделей ветвей поступает на управляющий вход ключа 9. Импульсы от генератора импульсов через информационную цепь ключа 9 поступают на один из входов элементов ИЛИ 8, а с его выхода - на счетный вход счетчика 4 моделей ветвей. При поступлении на счетчик 4 модели ветви 3 " (М-Р ) импульсов на выходе счет-,11чика появляется сигнал переполнения, поступающий на управляющий вход ключа 5 этой модели ветви, а через разделительный диод 7 модели ветви - на управляющий вход ключа 9 этой модели ветви и остальных моделей ветвей, соответствующих дугам моделируемого графа, входящим в 3-ю вершину. При этом соответствующий вход модели ветви 3 через элемен 1ты 6 индикации и информационную цепь ключа 5 соединяется е ее вторым выходом, размыкается информационная цепь ключей 9 всех моделей ветвей 3 , =0 1-1 снимается сиг"11 э Рнал с управляющего входя ключей 10 этих моделей ветвей и размыкается цепь подачи импульсов на счетные входи их счетчиков 4. Кроме того, сигнал высокого уровня с выхода счетчика 4 модели ветви 3; через разделительный диод 7 и первый выход модели ветви поступает на информационный вход ключей 9 моделей ветвей 3;,1 , 1 = 1+2,п. С выходов1+11фключей 9 этих моделей ветвей сигнал поступает на управляющий вход ключа 10. Информационная цепь этих ключей замыкается, и импульсы с соответст" вующего входа блока поступают через . элемент ИЛИ 8 на счетные входы счетчиков 4.По мере включения все большего числа моделей ветвей включение одной или нескольких из них обеспечивает цепь, соединяющую шину питания че 3 1432548тания через разделительный диод 20блока 2, элементы 6 индикации и информационные цепи ключей 5 некоторыхвключенных моделей ветвей 3;моделиграфа 1 с управляющим входом ключа13 блока управления. При поступлении напряжения от шины питания поэтой цепи на управляющий вход ключа13 размыкается его информационнаяцепь, снимается напряжение с управляющего входа генератора импульсови он прекращает их вырабатывать.Счетчик 12 блока 2 при этом фикси-:рует величину, соответствующую максимальной пропускной способности,а горящие светодиоды моделей ветвей.индицируют топологию соответствующего ей пути (путей).Аналогичным образом устройствоработает в этом режиме и при определении пути с минимальной пропускнойспособностью, только перед работойсчетчикимоделей ветвей 3устанавливаются в состоянии (Н-Ч;,), еслид,3-я дуга есть в исследуемой графе, и в нулевое состояние, если.,3-я дуга отсутствует.Для возврата схемы в исходноесостояние выключаются выключатели16 и 19 и кратковременно нажимаетсякнопочный выключатель 17 блока 2,При этом напряжение от шины питаниячерез контакт кнопочного выключателя 17 поступает на вход установкив исходно (нулевое) состояние счетчика 12 блока управления.Перед определением экстремальныхпутей в графе, т.е. перед работойустройства во втором режиме, в блокеуправления включается выключатель18. Напряжение от шины питания черезконтакт выключателя 18 поступает науправляющий вход ключа 14, на соответствующий выход блока, а через разделительный диод 21 - на другой соотВетствующий выход блока.Для определения критического путисчетчики 4 моделей ветвей 3;, устанавливаются в состояние Р; , равноеили пропорциональное массе (длине)х,1-й дуги, если она есть в моделируемом графе, и в состоянии Р; =О,если х,-я дуга в графе отсутствует.Как и в первом режиме, работа вовтором режиме начинается включением 55выключателя 16. При, этом напряжениеот шины питания поступаетна информационный вход. ключа 13, с инфорУстройство для определения экстремальных путей сетевых графов, содержащее модель графа и блок управления, состоящий из генератора импульсов, счетчика и ключа, модель графа содержит модели ветвей, каждая некоторых содержит счетчикключ и элемент индикации, выход счетчика мфдели ветви соединен с управляющим входом ключа модели ветви, информационный вход ключа соединен с выходбм элемента индикации, вход которого является входом модели ветви, выход ключа является выхоцом модели ветви, входы моделей ветви нулевой строки модели графа объединены и соединены с входом модели графа, входы модеаей ветви З.-й стронл 1 х=1,п, где и - количество модечей ветви нулевой строки), принадлежащих столбцам от второго до п-го модели графа, объединены и соединены с р, объединенными выходами (1-1)-го "ь столбца Ц=2п), принадлежащих 5рез контакты выключателя 18, разделительный диод 21, выход блока 2, вход модели графа 1, элемент Ь индикации и ключи 5 некоторых включенНых моделей ветвей, выход модели графа 1 и вход блока 2 с управляющим входом ключа 13 блока 2. Информационная цепь ключа 13 при этом размыкается, и снимается напряжение с )управляющего входа генератора импульсов, который прекращает вырабатывать импульсы. Счетчик 12 блокафиксирует величину, соответствуюфую длине (массе) критического пути из начал. ной вершины в конечную ершику граФа, а горящие светодиоды моделей ветвей индицируют топологию этого пути.Аналогичным образом устройство Работает в этом режиме и при опреде 1 ении кратчайшего пути с тем отличием, что перед работой счетчика 4 моелей ветвей 3устанавливаются в остояние (В-Р; ), если ,-я дуга сть в моделируемом графе, а по окончании работы показания счетчика 1,2 блока 2 равны массе. (длине) кратЧайшего пути.Возврат схемы в исходное состоя",. ние осуществляется так же, как в первом режиме. Формула изобретения 32548 6строкам от нулевой до (1-1)-й моделиграфа, выходы всех моделей п-гостолбца модели графа соединены с вы 5ходом модели графа, который соединенс управляющим входом ключа блокауправления, информационный вход ключа блока управления является входомзапуска устройства, выход ключа соединен с управляющим входом генератора импульсов, выход которого подклю 1чен к счетному входу счетчика блокауправления, вход установки в "О" :счетчика блока управления являетсявходом установки начального состояния устройства, управляющие входымоделей ветви модели графа объединены и соединены с управляющим входоммодели графа, о т л и ч а ю щ ее с я тем, что, с целью расширения,функциональных возможностей устройства за счет определения наряду с путя"ми экстремальной пропускной способности также путей экстремальной дли.25 ны (массы), в каждую модель ветвимодели графа введены второй и третийключи, элементы ИЛИ и диод, а в блокуправления введены второй и третийключи, первый и второй диоды, первый вход элемента ИЛИ модели ветвисоединен с управляющим входом моделиветви, второй вход элемента ИЛИ соединен с выходом второго ключа, информационный вход которого соединенс вторым управляющим входом моделиветви, управляющий вход второго ключа соединен с выходом третьего ключа,информационный вход которого являет-.ся информационным входом модели ветви, управляющий вход третьего ключамодели ветви соединен с катодом диода и является вторым выходом моделиветви, информационные входы моделейветви нулевой строки модели графаобъединены и соединены с информацион 45ным входом модели графа, информационные входы моделей ветви т-й строки=1п), принадлежащих столбцам от второго до и-го модели графа,50объединены и соединены с объединенными вторыми выходами моделей ветви(1-1)-го столбца Цй) принадлежащих строкам от нулевой до И 1)-й модели графа, вторые выходы моделей ветви п-го столбца модели графа. объединены, вторые управляющие55входы моделей ветвиобъединены исоединены с вторым управляющим входом юдели графа, выход генератора1432548 8импульсов блока управления соединен блока управления, который соединен с информационными входами второго и с входом модели графа, управляющий третьего ключей, выходы которых яв- вход третьего ключа блока управлеляются первым и вторым управляющим ния соединен с анодом второго диода5выходами блока управления, управ- , блокауправления, с входом признака ляющий вход второго ключа блока уп- определения путей экстремальной проравления является входом признака .пускной способности и с информационопределения пути с максимальной про- кым входом модели графа, первый уппускной способностью устройства и 1 О равляющий выход блока управления со соединен с анодом первого диода единен с первым управляющим входом блока управления, катод первого дио- модели графа, второй управляющий да соединен с катодом второго диода выход блока управления соединен с и является информационным выходом вторым управляющим входом модели графа. оставитель С.Кошелевехред А.Кравчук К Редактор О.Юрковецка ор М.Пож аказ 543/43 Тираж 704ственногобретений-35, Рауш одписно ВНИИПИ Госуд по делам и 3035, Москва;омитета СССР открытийая наб., д. 4/ роиэводственно-полиграфическое предприятие, г, Ужгоро Проектная, 4