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

337792 О ПИ- ИЗОБРЕТЕНИЯ Союз Соеетекиа Социалистических РеспубликК АВТОРСКОМУ СВИДЕТЕЛЬСТВУ ависимое от авт. свидетельствааявлено 26.Х.970 ( 1485210/18-24). б 06 д 7/4 6 06 д 7/5 присоединением заявкииоритет Комитет по делам изобретений и открытий ори Совете Министров СССРУДК 681,3,33,001(088,8) Опубликовано 05.Ч.1972. Бюллетеньата опубликования описания 16.Ч 111,1972 Авторыизобретения онов и С. Е, Прозо. В. Васильев,Заявитель ститут кибернетики АН Украинской ОЙСТВО ДЛЯ МОДЕЛИРОВАНИ РАФЕ Е Изобретение относится к области электронного моделирования и может быть использовано при построении специализированных вычислительных машин для решения задач о потоках в сетях.Известны устройства, содержащие блоки моделей ветвей, блоки моделей узлов, связанные между собой в соответствии с топологией сети и соединенные с ними устройство управления и генератор импульсов, предназначенные для определения кратчайших и длиннейших путей на графе.,Однако при использовании, известных устройств нельзя решить задачу определения пути заданной длины на сетевом графе, сущность которой заключается в следующем; задан однонаправленный граф с известными длинами ветвей и необходимо определить совокупность ветвей, образующих путь заданной длины между двумя узлами графа.Требуемый положительный эффект в предлагаемом устройстве достигается путем изменения схемы известного устройства, содержащего блок моделей ветвей, блок моделей узлов, устройство управления и генератор импульсов. Такое, изменение схемы устройства позволяет определить пути заданной длины на графе.На фиг, 1 изображено предлагаемое устройство для моделирования путей на графе; на фиг. 2 - схема устроиства управления, входящего в предлагаемое устройство; на фиг, 3 -блок-схема моделей ветвей; на фиг. 4 - блоксхема моделей узлов; на фиг, 5 - фрагмент5 графа,Предлагаемое устройство содержит генератор импульсов 1, устройство управления 2,блок моделей ветвей 3, блок моделей узлов 4.Устройство управления содержит узел уп 10 равления б, узел сравнения б, задатчик 7 допустимых значений длины искомого пути, счетчик импульсов 8 и 9, блок 10 индикации отсутствия решения.Узел управления б связан со входами счет 15 чиков 8, 9 с узлом сравнения б, а также полюсами 11, 12, И соответственно с генераторомимпульсов, блоком моделей ветвей 8, блокоммоделей узлов 4. Узел сравнения б соединен свыходами задатчика допустимых значений20 длины искомого пути 7 и счетчиков 8, 9, выход переполнения последнего из которых соединен с блоком индикации отсутствия решения 10,Блок моделей ветвей 3 содержит отдельные25 модели ветвей, выполненные, например, посхеме на фиг, 3, где изображены сдвиговыйрегистр 14, триггер 1 б, двухвходовые схемысовпадения 1 б и 17, трехвходовая схема 12совпадения, диоды 19 и 20, двухвходовая схе 30 ма 21 разделения.Вход 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, 3132 и двухвходовая схема разделения 33.Вход 34 схемы разделения 33 являетсяфункциональным входом модели узла, а второй вход указанной схемы разделения подключен к выходу схемы совпадения 32. Единичный выход триггера 29 соединен с однимиз входов схемы совпадения 32, а его единичный и нулевой входы - соответственно с выходами схем совпадения 30, 31. Две парывходов схем совпадения 30, 31, единичный выход триггера 29, а также второй вход схемсовпадения 32 образуют соответственно полюсы 35, 36, 37, 38, 39, 40 модели узла. Выход41 схемы разделения 33 является функциональным выходом модели узла.Модели ветвей и модели узлов, число которых соответственно равно числу ветвей и узлов графа, коммутируются между собой всоответствии с топологией графа. Пример коммутации моделей узлов 42,и моделей ветвей43 для фрагмента графа, данного на фиг. 5, а,изобракен на фиг. 5, б.Предлагаемое устройство работает следующим образом.В исходном состоянии триггер 29 моделиконечного узла искомого пути установлен вединичное состояние, все остальные триггеры15, 29, регистры 14 и счетчики 8, 9 моделейветвей, моделей узлов и устройства управления находятся в нулевом состоянииКроме того, на задатчике пределов длиныпути 7 устанавливаются коды, соответствующие минимальному и максимальному заданным допустимым значениям длины и искомого пути на графе. (В случае однозначно заданной длины искомого пути эти два значениясовпадают) .При пуске на полюс 25 моделей ветвей изустройства управления подается разрешающий потенциал, а на вход 34 модели начального узла искомого пути - одиночный импульс, синхронизированный с импульсами генератора 1. Одновременно узел управления 5разрешает поступление импульсов генератора 41 на вход счетчика 9 и по совпадению с разрешающим потенциалом единичного выхода триггера 29 модели конечного узла искомого пути - на вход счетчика 8. При отсчете числа 5 импульсов, соответствующего заданному минимально допустимому значению длины искомого пути, узел сравнения 6, осуществляя сравнение кода счетчика импульсов 9 и кода заданного минимального значения длины ис комого пути задатчика пределов длины пути 7,выдает сигнал в узел управления, По совпадению указанного сигнала с разрешающим потенциалом единичного выхода триггера 29 модели конечного узла искомого пути, узел уп равления выдает разрешающий потенцйал наполюс 26 моделей ветвей, тем самым разрешая по одному входу прохождение сигналов через схему совпадения 18 моделей ветвей.Так как на вторых входах схем совпадения 20 18 моделей ветвей, входящих в конечный узелискомого пути, имеется разрешающий потенциал с единичного выхода триггера 29 модели конечного узла, появление в последующий момент времени импульса переноса на выходе 25 регистра 14 модели любой из указанных ветвей приводит к установке триггера 15 через схему совпадения 18 в единичное состояние, регистрируя тем самым принадлежность соответствующей ветви искомому пути, Этот же 50 импульс, проходя последовательно схему совпадения 16, схему разделения 21 модели указанной ветви, схему разделения 33 модели конечного узла поступает в узел управления 5, который при этом запрещает поступление имз 5 пульсов генератора 1 на входы счетчиков 8, 9и подает запрещающие потенциалы на полюсы 25, 26 моделей ветвей. В результате в указанных счетчиках устройства управления записано число импульсов, соответствующее изве стной лежащей в заданных пределах допускадлине пути, проходящего через первую найденную ветвь, входящую в конечный узел искомого пути.Затем узел управления осуществляет сброс 45 в нулевое состояние счетчика 9 в устройствеуправления и регистре 14 моделей ветвей, а также выдает импульс, синхронизированный с импульсами генератора 1, на полюс 36 моделей узлов и, сдвинутый относительно первого, второй импульс - на полюс 37 моделей узлов.При этом, в соответствии с коммутацией моделей ветвей и моделей узлов (см. фиг. 5) первый указанный импульс установит в единичное состояние триггер 29 модели начального узла первой найденной ветви, а второй в сбросит в нулевое состояние триггер 29 модели конечного узла упомянутой ветви (который, в данном случае, совпадает конечным узлом искомого пути), так как на входе 35 схемы совпадения 30, управляющей единичным входом триггера 29 модели первого упомянутого узла и на входе 38 схемы совпадения 31, управляющей нулевым входом триггера 29 модели второго узла, имеется разрешающий по 65 тенциал с единичного выхода триггера 15 мо 337792дели первой найденной ветви, соединяющей эти узлы. Далее узел управления подает одиночный импульс, синхронизированный с импульсами генератора 1, на полюс 40 моделей узлов и одновременно разрешает поступление импульсов генератора 1 ца вход счетчика 9 в устройстве управления, Указанный импульс проходит последовательно схему совпадения 32, схему разделения 33 модели начального узла первой найденной ветви, триггер 29 которой разрешает прохождение импульса потенциалом единичного выхода, и поступает на входы 22 регистров 14 моделей ветвей, выходящих из данного узла, Импульс переноса с выхода регистра 14 модели первой найденной ветви по разрешению потенциала единичного выхода триггера 15 проходит через схему совпадения 17 и далее чеоез схему разделения 21 модели указанной ветви, схехтч разделения 33 модели конечного узла искомого пути поступает в узел управления Б, который при этом запрещает поступление импульсов на вход счетчика 9 устройства управления.В результате последний регистрирует число импульсов, соответствующее длине первой найденной ветви искомого пути.В следующий момент времени узеч управления осуществляет сброс регистров 14 и подает разрешающий потенциал на полюс 25 моделей ветвей, Затем узел управления разрешает поступление импульсов генератора 1 на вход счетчика 9 и одновременно посылает одиночный импульс, синхронизированный с указанными, на гход Я модели нача,чьного узла искомого пути.По сигналу совпадения кодов счетчиков 8, 9 регистрируемому узлом сравцецця б, узеч управления б выдает импульс на полюс 2 б моделей ветвей,и запрещает поступление импульсов на вход счетчика 9. Так как пои этом содержимое счетчика 9 дополняется разностью между известной длиной искомого пути и длиной первой найденной ветви, ему поицадлсжащей, то описанцот моменту времени подачи импульса ца полюс 2 б .,тоделей ветвей соответствует появление импульса переноса на выходе регистра 14 модели одной цз ветвец, входящих в начальныи узе,ч первой найденной ветви. Совпадение указанны импульсов с разрешающим потенциалом едицттчного выхода триггера 29 модели упомянутого узла приводит к установке тоиггера 1 б соответствующей модели ветви и регистрации, таким образом, втооой ветви, принадлежащей искомому пути. Процесс определеция послечующих ветвей протекает аналогично описанному циклу опоеделения второй гетви искомого пути. В каждом таком цикле определения новой ветви, перел опросом мочели графа с помощью одиночного импульса, засьтлаеътого в модель начального узла искомого пути, в единичное состояние устанавливается триггер 29 модели только того узла, в котором оканчивается искомая ветвь, а в счетчик 9 устройства управления заносится число импульсов,г 5 Зо 35 40 45 50 55 60 б 5 соответствующее сумме длин, ранее определенных ветвей, образующих конечный отрезок искомого пути, Таким образом решение задачи должно быть получено за число циклов, равное числу ветвей, составляющих искомый путь. Окончание последнего цикла регистрируется разрешающим потенциалом на единичном выходе триггера 29 модели начального узла искомого пути.В случае отсутствия искомого пути, при совпадении в первом цикле решения кода счетчика импульсов 9 и кода заданного максимального допустимого значения длины искомого пути згдатчика пределов длины пути 7, регистрируемого узлом сравнения б, узел управления выдает запрещающий потенциал на полюс 2 б моделей ветвей, разрешая, однако, поступление импульсов на вход счетчика 9 устройства управления, Импульс переполнения счетчика 9 воздействует ца блок индикации отсутствия решения. Предмет изобретенияУстройство для моделирования путей на графе, содержащее блок моделей ветвей, блок моделей узлов, связанные между собой в соответствии с топологией сети, и соединенное с ними устройство управления, ко входу которого подключен генератор импульсов, отлачающееся тем, что, с целью определения пути заданной длины ца графе, оцо содержит два счетчика, блок индикации отсутствия решения, задатчик допустимых значений длины искомого пути и узел сравнения, причем устройство управления соединено со входами двух счетчиков, входы которых подключены ко входам узла сравнения, третий вход которого соединен с задатчиком допустютых значений длины искомого пути, а выход - с устройством упоавлецця, к выходу одного из счетчиков подключен блок индикации отсутствия решецця; модель ветви блока моделей ветвей содержит сдвиговый регистрдве двухвходовые схемы совпадения, схеттг разделения, триггер, трехвходовую схему совпадения и разделителытьте диоды, причем вход сдвнгового регистра подключен ко входу блока моделей, а выхоч - к одному из входов схем совпадения, второтт вход одной цз двухвходовых схем совпадения соединен с едпнттчным выходом триггера н через разделительные диоды - с полюсами модели ветви, другие входы остальных схем совпадентия подклточеньт к управляющим входам блока моделей ветвей. выходы двухвходовых схем совпадения через схему разделения подключены к выходу блока моделей ветви, выход трехвходовой схемы совпадения соединен с единичным входом триггера, а модель узла блока моделей уз,чов выполнена на триггере, трех схемах совпадения и схеме разделения, причем один цз входов схемы разделения соединен со входом модели узла, а другой - с выходом одной из схем совпадения, входы которой подключены к управляющим входам блока моделей узлов и к337792 Уиг 1 22 2 о 27 иг единичному выходу триггера, входы триггера соединены с выходами двух других схем совпадений, входы которых подключены к входам моделей узлов.337792 Л н оррек Гонца Редак р. Сапунова, 2 ипог Заказ 24840ЦНИИПИ Комитета З 7 Щ Л аОРиг,ч ставитель С. Бела хред Л. Богданов Изд,1021 Тираж 448 Подписное елам изобретений и открытий при Совете Министров СССР Москва, Ж, Раушская иаб., д. 4/5