УСТРОЙСТВО ДЛЯ МОДЕЛИРОВАНИЯ ПУТЕЙ НА ГРАФЕ Советский патент 1972 года по МПК G06G7/122 G06G7/52 

1 I

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

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

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

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

фиг. 2 - схема устройства управления, входящего в предлагаемое устройство; на фиг. 3 - блок-схема моделей ветвей; на фиг. 4 - блоксхема моделей узлов; на фиг. 5 -- фрагмент

графа.

Предлагаемое устройство содержит генератор импульсов 1, устройство управления 2, блок моделей ветвей 3, блок моделей узлов 4. Устройство управления содержит узел управления 5, узел сравнения 6, задатчик 7 допустимых значений длины искомого пути, счетчик импульсов 8 и 9, блок 10 индикации отсутствия решения. Узел управления 5 связан со входами счетчиков 8, 9 с узлом сравнения 6, а также полюсами //, 12, 13 соответственно с генератором импульсов, блоком моделей ветвей 3, блоком моделей узлов 4. Узел сравнения 6 соединен с выходами задатчика допустимых значений

длины искомого пути 7 и счетчиков 8, 9, выход переполнения последнего из которых соединен с блоком индикации отсутствия решения 10.

Блок моделей ветвей 5 содержит отдельные

модели ветвей, выполненные, например, по схеме на фиг. 3, где изображены сдвиговый регистр 14, триггер 15, двухвходовые схемы совпадения 16 и 17, трехвходовая схема 12 совпадения, диоды 19 и 20, двухвходовая схеВход 22 регистра 14, емкость которого соответствует длине ветви, является функциональным входом модели ветви, а его выход соединен с первыми входами схем совпадения 16, 17, 18. Единичный вход триггера 15 подключен к выходу схемы совпадения 18, а его единичный выход соединен со вторым входом схемы совпадения 17 и через диоды 19, 20 с полюсами 23, 24 модели ветви. Вторые входы схем совпадения 16, 17 образуют полюсы 25, 26 модели ветви, соединенные с полюсами 12 узла управления 5, а третий вход схемы совпадения 18 - полюс модели ветви 27. Выходы схем совпадения 16, 17 через схему разделения 21 образуют функциональный выход модели ветви 28. Блок моделей узлов 4 содержит отдельные модели узлов, выполненные, например, по схеме изображенной на фиг. 4, в которые входят триггер 29, двухвходовые схемы совпадения 30, 31, 32 и двухвходовая схема разделения 33. Вход 34 схемы разделения 33 является функциональным входом модели узла, а второй вход указанной схемы разделения подключен к выходу схемы совпадения 32. Единичный выход триггера 29 соединен с одним из входов схемы совпадения 32, а его единичный и нулевой входы - соответственно с выходами схем совпадения 30, 31. Две пары входов схем совпадения 30, 31, единичный выход триггера 29, а также второй вход схем совпадения 32 образуют соответственно полюсы 35, 36, 37, 38, 39, 40 модели узла. Выход 41 схемы разделения 33 является функциональным выходом модели узла. Модели ветвей и модели узлов, число которых соответственно равно числу ветвей и узлов графа, коммутируются между собой в соответствии с топологией графа. Пример коммутации моделей узлов 42 и моделей ветвей 43 для фрагмента графа, данного на фиг. Ь,а, изображен на фиг. 5, б. Предлагаемое устройство работает следующим образом. В исходном состоянии триггер 29 модели конечного узла искомого пути установлен в единичное состояние, все остальные триггеры 15, 29, регистры 14 и счетчики 8, 9 моделей ветвей, моделей узлов и устройства управления находятся в нзлевом состоянии. Кроме того, на задатчике пределов длины пути 7 устанавливаются коды, соответствующие минимальному и максимальному заданным допустимым значениям длины и искомого пути на графе. (В случае однозначно заданной длины искомого пути эти два значения совпадают). При пуске на полюс 25 моделей ветвей «з устройства управления подается разрешающий потенциал, а на вход 34 модели начального узла искомого пути - одиночный импульс, синхронизированный с импульсами генератора /. Одновременно узел управления 5 разрешает поступление импульсов генератора 4 . . . / на вход счетчика Р и по совпадению с разрешающим потенциалом единичного выхода триггера 29 модели конечного узла искомого пути - на вход счетчика 8. При отсчете числа импульсов, соответствующего заданному минимально допустимому значению длины искомого пути, узел сравнения 5, осуществляя сравнение кода счетчика импульсов 9 и кода заданного минимального значения длины искомого пути задатчика пределов длины пути 7, выдает сигнал в узел управления. По совпадению указанного сигнала с разрешающим потенциалом единичного выхода триггера 29 модели конечного узла искомого пути, узел управления выдает разрешающий нотенцйал на полюс 26 моделей ветвей, тем самым- разрешая по одному входу прохождение сигналов через схему совпадения 18 моделей ветвей. Так как на вторых входах схем совпадения 18 моделей ветвей, входящих в конечный узел искомого пути, имеется разрешающий потенциал с единичного выхода триггера 29 модели конечного узла, появление в последующий момент времени импульса переноса на выходе регистра 14 модели любой из указанных ветвей приводит к установке триггера 15 через схему совпадения 18 в единичное Состояние, регистрируя тем самым принадлежность соответствующей ветви искомому пути. Этот же импульс, проходя последовательно схему совпадения 16, схему разделения 21 модели указанной ветви, схему разделения 33 модели конечного узла поступает в узел управления 5, который при этом запрещает поступление импульсов генератора 1 на входы счетчиков S, 9 и подает запрещающие потенциалы- на полюсы 25, 26 моделей ветвей. В результате в указанных счетчиках устройства управления записано число импульсов, соответствующее известной лежащей в заданных пределах допуска длине пути, проходящего через первую найденную ветвь, входящую в конечный узел искомого пути. Затем узел управления осуществляет сброс в нулевое состояние счетчика 9 в устройстве управления и регистре 14 моделей ветвей, а также выдает импульс, синхронизированный с импульсами генератора 1, на полюс 36 Моделей узлов и, сдвинутый относительно- первого, второй импульс - на полюс 37 моделей узлов. При этом, в соответствии с коммутацией моделей ветвей и моделей узлов (см. фиг. 5) первый указанный импульс установит в единичное состояние триггер 29 модели начального узла первой найденной ветви, а второй-сбросит в нулевое состояние триггер 29 модели конечного узла упомянутой ветви (который, в данном случае, совпадает конечным узлом искомого пути), так как на входе 55-схемы совпадения 30, управляющей единичным входом триггера 29 модели первого упомянутого узла и на.входе 55 схемы совпадения 31, управляющей нулевым входом триггера 29 модели второго узла, имеется разрещающий по

дели первой найденной ветви, соединяющей эти узлы. Далее узел управления подает одиночный импульс, синхронизированный с импульсами генератора 1, на полюс 40 моделей узлов и одновременно разрешает поступление импульсов генератора / на вход счетчика 9 в устройстве управления. Указанный импульс проходит последовательно схему совпадения 32, схему разделения 33 модели начального узла первой найденной ветви, триггер 29 которой разрешает прохождение импульса потенциалом единичного выхода, н поступает на входы 22 регистров 14 лгоделей ветвей, выходяш,их из данного узла. Импульс переноса с выхода регистра 14 модели первой найденной ветви по разрешенугю потенциаиТа единичного выхода триггера 15 нроходит через схему совпадения /7 и далее через схему разделения 21 модели указанной ветвИ, схему разделения 33 модели конечного узла искомого пути поступает в узел управления 5, который при этом запрещает поступление импульсов на вход счетчика 9 устройства управления.

В результате последний регистрирует число импульсов, соответствующее длине первой найденной ветви искомого пути.

В следующий момент времени узел управления осуществляет сброс регистров 14 и нодает разрешающий потенциал на полюс 25 моделей ветвей. Затем узел управления разрешает поступление импульсов генератора / на вход счетчика 9 и одновременно посылает одиночный импульс, синхронизированный с указанными, на вход 34 модели начального узла искомого пути.

По сигналу совпадения кодов счетчиков 8, 9 регистрируемому узлом сравнения 6. узел управления 5 выдает импульс на полюс 26 моделей ветвей и запрещает поступление импульсов на вход счетчика 9. Так как при этом содержимое счетчика 9 дополняется разностью между известной длиной искомого пути и длипой первой най.аенной ветви, ему пвинадлсжащей, то описанному моменту времени подачи импульса на полюс 26 моделей ветвей соответствзет появление импульса переноса на выходе регистра 14 модели одной из ветвей, входящих в начальный узел первой найденной ветви. Совпадение указанных импульсов с разрешающим потенциалом единичного выхода триггера 29 модели упомянутого узла приводит к установке триггера 15 соответствующей модели ветви « регистрации, таким образом, ВТОРОЙ ветви, принадлежащей искомому пути. Процесс определения последующих ветвей протекает аналогично описанному циклу определения второй ветви искомого пути. В каждом таком цикле определения новой ветви, перед «опросом модели графа с помощью одиночного импульса, засылаемого в модель начального узла искомого нути, в единичное состояние устанавливается триггер 29 модели только того узла, в котором оканчивается искомая ветвь, а в счетчик 9 устройства управления заносится число импульсов.

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

В случае отсутствия искомого пути, при совпадении в первом цикле решения кода счетчика импульсов 9 и кода заданного максимального допустимого значения длины искомого пути задатчика пределов длины пути

7, регистрируемого узлом сравпения 6, узел управления выдает запрещающий потенциал на полюс 26 моделей ветвей, разрешая, однако, поступление импульсов на вход счетчика 9 устройства управления. Импульс перепо.лнения счетчика 9 воздействует на блок индикации отсутствия решения.

Предмет изобретения

Устройство для моделирования путей на

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

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

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

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

двухвходовых схем совпадения через схему разделения подключены к выходу блока моделей ветви, jвыxoд трехвходовой схемы совпадения соединен с единичным входом триггера, а модель узла блока моделей узлов выполнепа на триггере, трех схемах совпадения и схеме разделения, причем один из входов схед1Ы разделения соединен со входом модели узла, а другой -с выходом одной из схем совпадения, входы которой подключены к упединичному выходу триггера, входы триггера соединены с выходами двух других схем совпадений, входы которых подключены к входам моделей узлов.

iPuz 1

Off

о о о 37 36 39 W