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

 

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

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

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

РЕСПУБЛИК

А1 (19) (11) (51) 4 G 06 Е 15/20

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

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

«Р» V

ОПИСАНИЕ ИЗОБРЕТЕНИЯ I "1,, Н А ВТОРСКОМУ СВИДЕТЕЛЬСТВУ (21) 4056050/24-24 (22) 21.04.86 (46) 23.09.87. Бюл.- № 35 (72) .О.Г.Апексеев, В.N,11аржанов и H.È.ß÷êóëà ,(53} 681.325(088.8) (56) Авторское свидетельство СССР

¹ 1179365, кл. С 06 F 15/20, 1985, Авторское свидетельство .СССР № 1193685„ кл. С 06 F 15/20, 1984. (54) УСТРОЙСТВО ДЛЯ ОПРЕДЕЛЕНИЯ ПУТИ

ЗКСТРЕ11АЛЬНОЙ ПРОПУСКНОЙ СПОСОБНОСТИ

ОРИЕНТИРОВАННОГО ГРАФА (57) Изобретение относится к вычислительной технике, к цифровым вычислительным машинам для обработки информации специального назначения с точки зрения конструкции вычислительного устройства и может быть использовано при построении специализированных вычислительных устройств для решения задач на ориентированных графах.

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

1339582

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

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

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

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

Блок 1 предназначен для задания топологии и пропускных способностей дуг моделируемого графа, а также индикации путей с экстремальной пропускной способностью. Блок 1 содержит 25 модели ветвей Çij,i=0,п-1, j =i+1,п, где (п+1) — количество вершин в моделируемом графе (индекс модели ветви соответствует индексу дуги (ij), соединяющей i-ю вершину с j-и). Все мо- 30 дели ветвей одинаковы и j -я модель ветви содержит счетчик 4ij импульсов, ключ 5ij и светодиод 6ij . Блок 1 содержит, кроме того, полюса 8 и 7, являющиеся управляющим входом и выходом блока соответственно, а полюс 9 является его выходом.

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

Работа устройства основана на последовательном включении моделей ветвей в порядке возрастания (убывания) пропускных способностей dij до момента, когда включение одной или нескольких из них не обеспечит составление с ранее включенными путем (путями ) из начальной 0-Й вершины в конечную и-ю вершину.

Перед определением пути с максимальной пропускной способностью счетчики 4ij моделей ветвей Çij, i О,п-1, j =i+1,п устанавливаются в состояние

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

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

8 импульсы поступают на счетные входы счетчиков всех моделей ветвей. При поступлении на счетчик 4 модели ветви ЗЦ (N-Vij ) импульсов (N — емкость счетчиков) на выходе этого счетчика появляется сигнал высокого уровня, сигнализирующий о его переполнении.

Этот сигнал поступает на управляющий вход ключа 5Ц и его информационная цепь соединяет соответствующий вход модели ветви Çij с ее выходом, что свидетельствует о включении данной модели ветви. Наконец, по мере включения все большего числа моделей ветвей, включение одной или нескольких моделей ветвей обеспечивает составление с ранее включенным путем (путями) из начальной вершины в конечную. При этом создается цепь, соединяющая вход 7 блока i через светодиоды и информационные цепи ключей, включенных и принадлежащих экстремальному пути моделей ветвей с выходом 9 блока 1. Напряжение от источника напряжения через эту цепь (цепи) поступает на управляющий вход ключа

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

Аналогичным образом устройство работает и при определении пути с минимальной пропускной способностью, за тем отличием, что перед работой счетчики 4ij моделей ветвей Çij устанавФормула изобретения

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

Техред М.Дидык Корректор М. Демчик

Редактор А.Ворович

Заказ 4224/40 Тираж б72 Подписное

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

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

Производственно-полиграфическое предприятие, г. Ужгород, ул. Проектная, 4, 3 1339 ливаются в состояние (N-Vij), если дуга (ij) есть в моделируемом графе, и — в нулевое состояние, если дуга (ij) в моделируемом графе отсутст5 вует.

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

582

4 той же модели ветви, вход которого является входом модели ветви, причем входы моделей ветви нулевой строки модели графа объединены и соединены с входом модели графа, входы моделей ветви i-й строки (i=1 n где n— количество моделей ветви нулевой строки, принадлежащих j-м столбцам (j=i+1 и) модели графа, объединены и соединены с объединенными выходами моделей ветви (j-1) столбца (j=2,...,n), принадлежащих строкам от нулевой до i: — 1 модели графа, а выходы всех моделей ветви и-го столбца модели графа соединены с выходом модели графа, который соединен с управляющим входом ключа, информационный вход которого является входом положительного напряжения устройства и соединен с входом модели графа, а выход ключа — с управляющим входом генератора импульсов, выход которого подключен к счетному входу счетчика пропускной способности и к управляющему входу модели графа, с которым соединены счетные входы счетчиков всех моделей ветви модели графа.