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

11339582

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

10

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

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

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

Устройство содержит блок 1 модели графа и блок 2 фиксирования и запуска.

Блок 1 предназначен для задания топологии и пропускных способностей дуг моделируемого графа, а также индикации путей с экстремальной пропускной способностью, Влок содержит 25 модели ветвей Згз ,1 071г- 1, ,n, где (n+l) - количество вершин в моделируемом графе (индекс модели ветви соответствует индексу дуги (ij), соесли дуга (ij) есть в моделируемой графе, или в-состояние , если дуга (ij) в моделируемой графе отсутствует, а счетчик 13 блока 2 устанавливается в нулевое состояние кратковременным нажатием кнопочного выключателя 12,

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

чика 13, и на вход 8 блока 1, С входа 8 импульсы поступают на счетные входы счетчиков всех моделей ветвей, При поступлении на счетчик 4 модели ветви 3ij (N-Vij) импульсов (N - емкость счетчиков) на выходе этого счетчика появляется сигнал высокого уровня, сигнализирующий о его переполнении. Этот сигнал поступает на управляющий вход ключа 5ij и его информационная цепь соединяет соответствующий вход единяющей i-ю вершину с j-й). Все мо- зо модели ветви 3ij с ее выходом, что дели ветвей одинаковы и L j -я модель свидетельствует о включении данной

ветви содержит счетчик 41j импульсов, ключ 5ij и светодиод 6ij. Блок 1 содержит, кроме того, полюса 8 и 7, являющиеся управляющим входом и выхо- 5 дом блока соответственно, а полюс 9 является его выходом.

Блок 2 предназначен для фиксирования значения экстремальной пропускной способности пути и подачи сигнала на начало решения. Блок 2 содержит ключ 10 SWB-типа, выключатель 11, кнопочный выключатель 12, счетчик 13 пропускной способности и генератор 14 импульсов„

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

45

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

Аналогичным образом устройство работает и при определении пути с минимальной пропускной способностью, за тем отлинием, что перед работой счетчики 4ij моделей ветвей 3ij устанавких из них не обеспечит составление с ранее включенньши путем ( путями) из начальной О-й вершины в конечную fi-ю вершину.

Перед определением пути с максимальной пропускной способностью счет- чики 41j моделей ветвей 31j, ,п-1, ,n устанавливаются в состояние Vij, равное или пропорциональное dij,

55

если дуга (ij) есть в моделируемой графе, или в-состояние , если дуга (ij) в моделируемой графе отсутствует, а счетчик 13 блока 2 устанавливается в нулевое состояние кратковременным нажатием кнопочного выключателя 12,

Решение начинается включением выключателя 11 блока 2, При этом напряжение от источника напряжения через замкнутые контакты выключателя 11 постз ает на вход 7 блока 1, а через контакты выключателя 11 и информа- ционную цепь ключа 10 на вход генератора 14 импульсов. Генератор 14 импульсов начинает вырабатывать импульсы, поступающие на счетный вход счетчика 13, и на вход 8 блока 1, С входа 8 импульсы поступают на счетные входы счетчиков всех моделей ветвей, При поступлении на счетчик 4 модели ветви 3ij (N-Vij) импульсов (N - емкость счетчиков) на выходе этого счетчика появляется сигнал высокого уровня, сигнализирующий о его переполнении. Этот сигнал поступает на управляющий вход ключа 5ij и его информационная цепь соединяет соответствующий вход о модели ветви 3ij с ее выходом, что свидетельствует о включении данной

5

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

5

31339582 . 4

ливаются в состояние (N-Vij), еслитой же модели ветви, вход которого

дуга (ij) есть в моделируемом графе,является входом модели ветви, причем

и - в нулевое состояние, если дугавходы моделей ветви нулевой строки

(ij) в моделируемом графе отсутст-модели графа объединены и соединены

вует.с входом модели графа, входы моделей

Фбрмулаизобретенияветви i-й строки (,..,,п, где п количество моделей ветви нулевой

Устройство для определения путистроки , принадлежащих j-м столбцам экстремальной пропускной способности ю(J i+l «««ri) модели графа, объеди- ориентированного графа, содержащеенены и соединены с объединенными вы- генератрр импульсов и модель графа,ходами моделей ветви (j-1) столбца состоящую из моделей ветви, каждая(,...,n), принадлежапщх строкам от из которых содержит элемент индика-нулевой до -1 модели графа, а выхо- ции и ключ, отличающееся -твДЫ всех моделей ветви п-го столбца тем, что, с целью упрощения устройст-модели графа соединены с выходом нова и расширения функциональных воз-дели графа, который соединен с управ- можностей за счет определения экстре-ляющим входом ключа, информационный мапьной пропускной способности ори- -вход которого является входом поло- ентированного графа, в него введены 20жительного напряжения устройства и счетчик пропускной способности исоединен с входом модели графа, а вы- ключ, а в каждую модель ветви введенход ключа - с управляющим входом ге- счетчик, выход которого соединен снератора импульсов, выход которого управляющим входом ключа той же моде-подключен к счетному входу счетчика ли ветви, выход ключа модели ветви 25пропускной способности и к управляю- является выходом модели ветви, инфор-щему входу модели графа, с которым мационный вход ключа модели ветвисоединены счетные входы счетчиков соединен с выходом элемента индикациивсех моделей ветви модели графа.

Изобретение относится к вычислительной технике, к цифровым вычислительным машинам для обработки информации специального назначения с точки зрения конструкции вычислительного устройства и может быть использовано при построении спеЬ,иализирован- ных вычислительных устройств для решения задач на ориентированных графах. Изобретение позволяет упростить устройство и распшрить его функциональные возможности за счет определения экстремальной пропускной способности ориентированного графа. Для этого в устройство для определения экстремальной пропускной способности ориентированного графа, содержащее генератор импульсов 14 и модель графа 1, состоящую из моделей ветви 3, каждая из которых содержит элемент индикации 6 и ключ 5, дополнительно включены счетчик пропускной способности 13 и ключ 10, а в. каждую модель ветви введен счетчик 4. 1 ил. i (Л