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

 

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

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

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

РЕСПУ БЛИН

„„Я0„„14 2548 А 1 (51)4 С 06 Р 15 20

ВСЕ 1;;11 j g.y g списочник изоБ стени =

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

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

К Д BTGPCHOIVIY СВИДЕТЕЛЬСТВУ (21) 4216846/24-24 (22) 30.03.87 (46) 23.10.88. Бил. 9 39 (72} О.Г.Алексеев, В.А.Иильков и Н.И.Ячкула (53) 681.333 (088.8) (56) Авторское свидетельство СССР

Р 1193685, кл. С 06 F 15/20, 1984.

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

В 1339582, кл. G 06 F 15/20, 1986. ду с путями экстремальной пропускной способности также путей экстрамаль-. ной длины (массы). Устройство состоит из модели графа 1 и блока управления

2. Модель графа 1 содержит модели ветвей 3 (ИВ), каждая из которых состоит из счетчика, трех ключей, элемента индикации, диода, элемента

ИЛИ. Блок управления содержит генератор импульсов 11, счетчик 12, три ключа 13, 14, 15 и два диода 20, 21.

Работа устройства основана на последовательном"включении" ИВ в соответствии с алгоритмом определения экстремальных путей, пока "включение" одной или нескольких ИВ не обеспеЯ чит путь из начальной вершины через

"включение .. ИВ в конечную вершину графа. Топология пути индицируется элементами индикации ИВ, а пропускная способность или длина (масса) пути определяется по счетчику блока управления. 2 ил. (54} УСТРОЙСТВО ДЛЯ ОПРЕДЕЛЕНИЯ

ЭКСТРЕИАЛЬНЫХ ПУТЕЙ СЕТЕВЫХ ГРАФОВ (57) Изобретение относится к вычислительной технике и позволяет решать задачи определения путей с экстремальной пропускной способностью и путей экстремального веса (длииы) на сетевых графах, не содержащих кратных дуг. Цель изобретения — расширение функциональных возможностей устройства за счет определения наря1432548

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

Цель изобретения — расширение

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

На фиг.1 приведена функциональная .схема устройства; на фиг.2 — функ:циональная схема модели ветви, Устройство содержит модель графа

1 и блок 2 управления. Модель графа

1 предназначена для задания топологии и пропускных способностей (длин) .дуг моделируемого графа, а также индикации определяемого пути. Модель графа 1 содержит модели ветвей 3 .. .у1 Ф

i=0 n-1, 1 =1+1, nó где (n +1 ) число вершин исследуемого графа (индексы модели ветви соответствуют индексам дуги, соединяющей i-ю вершину с j-й).

Все модели ветвей одинаковы, и ij-я модель ветви содержит счетчик 4 импульсов, ключ 5, элемент 6 индикации (светодиод), диод 7, элемент

ИЛИ 8, ключ 9 и ключ 10. .Блок 2 предназначен для фиксирования значения пропускной способнос" ги или длины найденного экстремального пути, задания режима работы

И подачи сигнала на.начало решения.

Блок 2 содержит генератор 11 импульсов, счетчик 12, ключи 13" 15, выключатель 16, кнопочный вьп лючатель

17, выключатели 18 и 19 и,циоды 20 и 21

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

: путей.

Перед определением пути с максимальной пропускной способностью счетчики 4 моделей ветвей 3 устанавливаются в состояние V;; равное или пропорциональное пропускной способности i,j-й дуги, если она есть в исследуемой графе, или в состояние Ч.. =О, если i,j-я дуга в графе отсутствует. В блоке управления включается выключатель 19, чем определяется выбор первого режима работы устройства. При этом напряжение от шины питания поступает че.рез контакты выключателя 19 на управляющий вход ключа 15 и катод диода 20, с анода которого напряжение поступает на соответствующий выход блока управления и далее через вход модели графа на соответствующий вход моделей ветвей 3„, j = 1,п.

Решение начинается включением выключателя 16 блока 2. При этом напряжение от шины питания через контакты выключателя 16 поступает на информационный вход ключа 13. С информационного выхода ключа 13 напряжение поступает на управляющий вход генератора ill импульсов, который при этом начинает вырабатывать импульсы, поступающие с выхода генератора на счетный вход счетчика 12 и информационные входы ключей 14 и

15. С информационного выхода ключа

15 импульсы через соответствующие выход блока 2 и вход модели графа 1 поступают на один вход элементов

ИЛИ 8 всех моделей ветвей 3;

=О,п-1, j = 1,п. С выходов элементов ИЛИ 8 всех моделей, ветвей импульсы поступают на счетный вход счетчиков 4 этих моделей ветвей.

При поступлении на счетчик 4 модели ветви 3 " (N-V " ) импульсов (N — ему 1) кость счетчиков 4) на выходе счетчи ка этой модели ветви появляется сигнал высокого уровня, сигнализирующий о его переполнении. Это сигнал поступает на управляющий вход ключа

5 данной модели ветви, а через разделительный диод 7- - на ключ 9 этой модели ветви и всех остальных моделей ветвей, соответствующих дугам моделируемого графа, входящим в j-ю вершину. При этом вход модели ветви

3; через светодиод 6 и информацион1 1 ную цепь ключа 5 соединяется с ее соответствующим выходом, что свидетельствует о включении данной модели ветви. По мере включения все большего числа моделей ветвей включение одной или нескольких моделей ветвей обеспечивает с ранее включенными моделями ветвей путь из начальной вершины в конечную. При этом создается цепь, соединяющая шину пимационного выхода которого напряжение поступает на управляющий вход генератора 11 импульсов. Последний начинает вырабатывать импульсы, поступающие через информационную цепь ключа 14 и соответствующий выход блока 2 на входы моделей ветвей Зо., 1

j =1, и, соответствующих дугам, исходящим из начальной вершины моделируемого графа. На другой вход этих моделей ветвей поступает напряжение с выхода блока 2..Это напряжение через информационную цепь ключа 9 моделей ветвей поступает на управляющий вход ключа 9. Импульсы от генератора импульсов через информационную цепь ключа 9 поступают на один из входов элементов И77И 8, а с его выхода — на счетный вход счетчика 4 моделей ветвей. При поступлении на счетчик 4 модели ветви

3 " (N-P " ) импульсов на выходе счет-, 1 чика появляется сигнал переполнения, поступающий на управляющий вход ключа 5 этой модели ветви, а через разделительный диод 7 модели ветви— на управляющий вход ключа 9 этой модели ветви и остальных моделей ветвей, соответствующих дугам моделируемого графа, входящим в 1-ю вершину. При этом соответствующий вход модели ветви 3 ° через элемен1 i ты 6 индикации и информационную цепь ключа 5 соединяется е ее вторым выходом, размыкается информационная цепь ключей 9 всех моделей ветвей 3 °, =0 j-1 снимается сигЭ Р нал с управляющего входя ключей 10 этих моделей ветвей и размыкается цепь подачи импульсов на счетные входи их счетчиков 4. Кроме того, сигнал высокого уровня с выхода счетчика 4 модели ветви 3; через разделительный диод 7 и первый выход модели ветви поступает на информационный вход ключей 9 моделей ветвей 3;+7, 1 = i+2 ï. С выходов

7+71 7 ключей 9 этих моделей ветвей сигнал поступает на управляющий вход ключа

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

По мере включения все большего числа моделей ветвей включение одной или нескольких из них обеспечивает цепь, соединяющую шину питания че-3 1432548 тания через разделительный диод 20 блока 2, элементы 6 индикации и информационные цепи ключей 5 некоторых включенных моделей ветвей 3; ° модели графа 1 с управляющим входом ключа

13 блока управления. При поступлении напряжения от шины питания по этой цепи на управляющий вход ключа

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

Счетчик 12 блока 2 при этом фикси-: рует величину, соответствующую максимальной пропускной способности, а горящие светодиоды моделей ветвей .индицируют топологию соответствующего ей пути (путей).

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

i,j-я дуга есть в исследуемой графе, и в нулевое состояние, если

i,j-я дуга отсутствует.

Для возврата схемы в исходное состояние выключаются выключатели

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

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

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

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

i j-й дуги, если она есть в моделируемом графе, и в состоянии Р; =0, если х, -я дуга в графе отсутствует.

Как и в первом режиме, работа во втором режиме начинается включением 55 выключателя 16. При, этом напряжение от шины питания поступает на информационный вход. ключа 13, с инфорУстройство для определения экстремальных путей сетевых графов, содержащее модель графа и блок управл ния, состоящий из генератора импульсов, счетчика и ключа, модель гфафа содержит модели ветвей, каждая из которых содержит счетчик ключ и элемент индикации, выход счетчика мфдели ветви соединен с управляющим входом ключа модели ветви, информационный вход ключа соединен с выходом элемента индикации, вход которого является входом модели ветви, выход ключа является выхоцом модели ветви, входы моделей ветви нулевой строки модели графа объединены и соединены с входом модели графа, входы модеией ветви i-й стронл (х=1,...п1, где n — количество модечей ветви нулевой строки), принадлежащих столбцам от второго до п-го модели графа, объединены и соединены с qr объединенными выходами (j-1)-го "ь столбца (j=2,...,n), принадлежащих

5 1Д рез контакты выключателя 18, разделительный диод 21 выход блока 2, вход модели графа 1, элемент Ь индикации и ключи 5 некоторых включенНых моделей ветвей, выход модели графа t и вход блока 2 с управляющим

Входом ключа 13 блока 2. Информационная цепь ключа 13 при этом размыкается, и снимается напряжение с

)управляющего входа генератора им1 ульсов, .-.îòîðûé прекращает вырабатывать импульсы. Счетчик 12 блока фиксирует величину, соответствую-!

Шую длине (массе) критического пути из начал, ной вершины в конечную ершику графа, а горящие светодиоды моделей ветвей индицируют топологию этого пути.

Аналогичным образом устройство

Работает в этом режиме и при опреде 1ении кратчайшего пути с тем отличием, что перед работой счетчика 4 моЦелей ветвей 3 устанавливаются в остояние (М-p; ) если i, j -я дуга сть в моделируемом графе, а по окончании работы показания счетчика !

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

Возврат схемы в исходное состоя":ние осуществляется так же, как в первом режиме.

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

32548 6 строкам от нулевой до (i-1)-й модели графа, выходы всех моделей и-го столбца модели графа соединены с вы5 ходом модели графа, который соединен с управляющим входом ключа блока управления, информационный вход клю ча блока управления является входом запуска устройства, выход ключа соединен с управляющим входом генератора импульсов, выход которого подклю 1 чен к счетному входу счетчика блока управления, вход установки в "О" счетчика блока управления является входом установки начального состояния устройства, управляющие входы моделей ветви модели графа объединены и соединены с управляющим входом модели графа, о т л и ч а ю щ ее с я тем, что, с целью расширения ,функциональных возможностей устройства за счет определения наряду с путями экстремальной пропускной способности также путей экстремальной дли

25 ны (массы), в каждую модель ветви модели графа введены второй и третий ключи, элементы ИЛИ и диод, а в блок управления введены второй и третий ключи, первый и второй диоды, первый вход элемента ИЛИ модели ветви соединен с управляющим входом модели ветви, второй вход элемента ИЛИ соединен с выходом второго ключа, информационный вход которого соединен с вторым управляющим входом модели ветви, управляющий вход второго ключа соединен с выходом третьего ключа, информационный вход которого являет-. ся информационным входом модели вет40 ви, управляющий вход третьего ключа модели ветви соединен с катодом диода и является вторым выходом модели ветви, информационные входы моделей ветви нулевой строки модели графа объединены и соединены с информацион45 ным входом модели графа, информационные входы моделей ветви i-й строки (* =1,...,n-1), принадлежащих столбцам от второго до и-го модели графа, 50 объединены и соединены с объединенными вторыми выходами моделей ветви (j-1)-ro столбца (j-2,...,й) „принадлежащих строкам от нулевой до (iJ)-й модели графа, вторые выходы моделей ветви п-ro столбца модели графа объединены, вторые управляющие

55 входы моделей ветви объединены и соединены с вторым управляющим входом юдели графа, выход генератора

Составитель С.Кошелев

Техред А.Кравчук Корректор N.Ïîæî

Редактор О.Юрковецкая

Заказ 5443/43

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

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

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

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

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

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