Устройство для определения экстремальных путей сетевых графов Советский патент 1988 года по МПК G06F15/173 

4

СО

to

00

Изобретение относится к вычислительной технике и может быть использовано при построении специализированных вычислительных устройств для решения -задач определения экстремальных путей (пути с минимальной пропускной способностью, пути с максимальной пропускной способностью, пути минимальной массы, кратчайшего, и критического пути) в ориентирован- :ных сетевых графах, ; Цель изобретения расширение Iфункциональных возможностей устройст :ва за счет определения наряду с путя ;МИ экстремальной пропускной способ- юности также пути экстремальной дли- ;ны (массы).

; На фиго1 приведена функциональная iсхема устройства; на фиг„2 - функ- |ционапьная схема модели ветвио j Устройство содержит модель графа И и блок 2 управления. Модель графа :1 предназначена для задания топологии и пропускных способностей (.длин) дуг моделируемого графа, а также индикации опред;еляемого пути. Модель графа 1 содержит модели ветвей , ,п-1, ,n, где (п +1) - число вершин исследуемого графа (индексы модели ветви соответствуют индексам |дуги, соединяющей i-ю вермину с j-й) Все модели ветвей одинаковы, и ij-я модель ветви содержит счетчик 4 импульсов, ключ 5, элемент 6 ивдика- ;ции (светодиод), диод 7, элемент ИЛИ 8, ключ 9 и ключ ТО ; Блок 2 предназначен для фиксиро |вания значения: пропускной способное |ги или длины наДценного экстремаль- ого пути, задания режима работы и подачи сигнала на.начало решения. Блок 2 содержит генератор 11 импульсов, счетчик 12, ключи 13--15, выключатель 16, кнопочный вьпслючатель 17, выключатели 18 и 19 и даоды 20 И 21 о

Устройство работает в двух режимах - режиме определения путем экстремальной пропускной способности и режиме определения экстремальных : путей.

Перед определением пути с максимальной пропускной способностью счетчики 4 моделей ветвей 3 устанавливаются в состояние V,-; , равное или пропорциональное пропускной способности дуги, если она есть в исследуемой графе, или в сос0

3

0

5

0

0

5

0

5

тояние Vj. 0, если i,j дуга в графе отсутствует, В блоке управления включается выключатель 19, чем определяется выбор первого режима работы устройства. При этом напря- . жение от шины питания поступает че- .рез контакты выключателя 19 на управляющий вход ключа 15 и катод диода 20,, с анода которого напряжение поступает на соответствующий выход блока управления и далее через вход модели графа на соответствующий вход моделей ветвей , j 1,п.

Решение начинается включением выключателя 16 блока 2. При этом напряжение от шины питания через контакты выключателя 16 поступает на инфopмaJ: иoнный вход ютюча 13 С информационного выхода ключа 13 напряжение поступает на управляющий вход генератора 11 импульсов, который при этом начинает вырабатывать импульсы, поступающие с выхода генератора на счетный вход счетчика 12 и информационные входы ключей 14 и 15 о С информационного выхода ключа 15 импульсы через соответствующие выход блока 2 и вход модели графа 1 поступают на один вход элементов liJlfjS всех моделей ветвей 3;- , i 0,п-1, j 1,п С выходов элементов ИЛИ 8 всех моделейI ветвей импульсы поступают на счетный вход счетчиков 4 этих моделей ветбей При поступлении на счетчик 4 модели ветви 3j- (N-Vjj-; и fflyльcoв (N - емкость счетчиков 4) на выходе счетчи - ка этой модели ветви появляется сигнал высокого уровня, сигнализщ)ую- щий о его переполнении. Это сигнал поступает на управляющий вход ключа 5 данной модели ветви, а через разделительный диод 7 - на ключ 9 этой модепи ветви и всех остальных моделей ветвей - соответствующих дугам моделируемого графа, входящим в j-ю вершину. При этом взгод модели ветви 3,-; через светодиод 6 и информахщон- ную цепь ключа 5 соединяется с ее соответствующим выходом, что свидетельствует о включении данной модели ветви о По мере включения вое большего числа моделей ветвей включение одной или нескольких моделей ветвей обеспечивает с ранее включенными моделями ветвей путь из начальной вершины в конечную При этом создается цепь,соединяющая шину пи

тания через разделительный диод 20 блока 2, элементы 6 индикации и информационные цепи ключей 5 некоторы включенных моделей ветвей З,-,- модел графа 1 с управляющим входом ключа 13 блока управленияо При поступлении напряжения от шины питания по этой цепи на управляющий вход ключа 13 размыкается его информационная цепь, снимается напряжение с управляющего входа генератора импульсов и он прекращает их вьфабатыватьо Счетчик 12 блока 2 при этом фикси- рует величину, соответствующую максимальной пропускной способности, а горящие светодиоды моделей ветвей индицируют топологию соответствующего ей пути (путей)

Аналогичным образом устройство работает в этом режиме и при определении пути с минимальной пропускной способностью, только перед работой счетчики 3 моделей ветвей 3 , j устанавливаются в состоянии (N-V,-j ) , если 1,3-я дуга есть в исследуег ой графе, и в нулевое состояние, если 1,3-я дуга отсутствует.

Для возврата схемы в исходное состояние выключаются выключатели 16 и 19 и кратковременно нажимается кн опочный выключатель 17 блока 2 р При этом напряжение от шины питания через контакт кнопочного выключателя 17 поступает на вход установки в исходно (нулевое) состояние счетчика 12 блока управления о

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

Для определения критического пут счетчики 4 моделей ветвей 3 ;j устанавливаются в состояние Р,-- , равное или пропорциональное массе (длине) i,j-й дуги, если она есть в моделируемом графе, и в состоянии Р.. 0, если 1,з-я дуга в графе отсутствует

Как и в первом режиме,работа во втором режиме начинается включением выключателя 16. При; этом напряжение от шины питания поступает на информационный вход, ключа 13, с инфор-

0

5

0

5

0

0

5

0

мационного выхода которого напряжение поступает на управляющий вход генератора 11 импульсов. Последний начинает вырабатывать импульсы, поступающие через информационную цепь ключа 14 и соответствующий выход блока входы моделей ветвей , ,n, соответствующих дугам, исходящим из начальной вершины моделируемого графа На другой вход этих моделей ветвей поступает напряжение с выхода блока 2 Это напряжение через информационную цепь ключа 9 моделей ветвей поступает на управ- ЛЯЮ11ЩЙ вход ключа 9. Импульсы от генератора импульсов через информационную цепь ключа 9 поступают на один из входов элементов Ш1И 8, а с его выхода - на счетный вход счетчика 4 моделей ветвей. При поступлении на счетчик 4 модели ветви 3 ,- (N-P ,-; ) импульсов на выходе счетчика появляется сигнал переполнения, поступающий на управляющий вход ключа 5 этой модели ветви, а через раз- делительньй диод 7 модели ветви - на управляющий вход ключа 9 этой модели ветви и остальных моделей ветвей, соответствующих дугам моделируемого графа, входящим в j-ю вершину При этом соответствующий вход модели ветви 3 ,s через элементы 6 индикации и информационную цепь ключа 5 соединяется е ее вторым выходом, размыкается информационная цепь ключей 9 всех моделей ветвей 3j-, ,j-1, снимается сигнал с управляющего входа ключей Ю этих моделей ветвей и размыкается цепь подачи импульсов на счетные входн их счетчиков 4. Кроме того, сигнал высокого уровня с выхода счетчика 4 модели ветви 3,- через разделительный диод 7 и первый выход модели ветви поступает на информационный вход ключей 9 моделей ветвей 3 . ; j i+2,n. С выходов ключей 9 этих моделей ветвей сигнал поступает на управляющий вход ключа 10. Информационная цепь этих ключей замыкается, и импульсы с соответствующего -входа блока поступают через- элемент ШШ 8 на счетные входы счетчиков-4.

По мере включения все большего числа моделей ветвей включение одной или нескольких из них обеспечивает цепь, соединяющую шину питания че-рез контакты выключателя 18, разделительный диод 21, выход блока 2, йход модели графа 1, элемент 6 инди- |кации и ключи 5 некоторых включен- йых моделей ветвей, выход модели Графа 1 и вход блока 2 с управляюнщм Входом ключа 13 блока 2, Информационная цепь ключа 13 при этом размыкается, и снимается напряжение с управляющего входа генератора им- упьсов, соторый прекращает выра- атывать импульсы Счетчик 12 блока фиксирует величину, соответствую- длине (массе) критического пути начал.зной вершины в конечную ершину графа, а горящие светодиоды фоделей ветвей индицируют топологию того пути.

Аналогичным образом устройство работает в этом режиме и при опреде х|ении кратчайшего пути с тем отличием, что перед работой счетчика 4 мо риелей ветвей 3j устанавливаются в состояние (N-P ,-. J , если i,j-я дуга €сть в моделируемом графе, а по скончании работы показания счетчика

12 блока 2 равны массе (.длине) крат Цайшего пути.

I Возврат схемы в исходное состояи(ие осуществляется так же, как в

цервом режиме.

. .

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

: Устройство для определения экст- р|емальных путей сетевых графов, со- д|ержащее модель графа и блок управ- , состояпщй из генератора им- п:|гльсов, счетчика и ключа, модель содержит модели ветвей, кажда .торых содержит счетчик ключ и элемент индикации, выход счетчика модели ветви соединен с управляющим входом ключа модели ветви, информационный вход ключа соединен с выхо дом-элемента индикации, вход которого является входом модели ветви, выход ключа является выхщом модели ветви, входы моделей ветви нулевой строки модели графа объединены и содинены с входом модели Грефа, входы моделей ветви i-й строк; (,i«1,, .,п1,, где п - количество модечей ветви нулевой строки), принадле-жащих столбцам от второго до модели графа, об11е;р1нены и соединены с объединенными выходами (j-1)-ro столбца (,...,п), принадлежащих

5

0

45

50

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

0

5

0

55

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

14325488

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

Изобретение относится к вычислительной технике и позволяет решать задачи определения путей с экстремальной пропускной способностью и путей экстремального веса (длины) на сетевых графах, не содержащих кратных дуг. Цель изобретения - расширение функциональных возможностей устройства за счет определения наряду с путями экстремальной пропускной способности также путей экстрамаль- ной длины (массы). Устройство состоит из модели графа 1 и блока управления 2. Модель графа 1 содержит модели ветвей 3 (МБ), каждая из которых состоит из счетчика, трех ключей, элемента индикации, диода, элемента ИЛИ о Блок управления содержит генератор импульсов 11, счетчик 12, три ключа 13, 14, 15 и два диода 20, 21, Работа устройства основана на пос- ледовательном вклгочении MB в соответствии с алгоритмом определения экстремальных путей, пока включение одной или нескольких MB не обеспечит путь из начальной вершины через включение МБ в конечную вершину графа. Топология пути индицируется элементами индикации ИВ, а пропуск- ная способность или длина (масса) пути определяется по счетчику блока управления. 2 ил. (Л

fPi/e.2