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

 

337792

О ПИИЗОБРЕТЕНИЯ

Союз Советски

Социалистических

Республик

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ

Зависимое от авт. свидетельства №

Заявлено 26.Х.!970 (№ 1485210/18-24) с присоединением заявки _#_Приоритет

Опубликовано 05.Ч.1972. Бюллетень № 15

Дата опубликования описания 16ХШ.1972

М. Кл. G 06_#_ 7/48

G 06g 7/52

Комитет по делам изобретений и открытий ори Совете Министров

СССР

УДК 681.333.001(088.8) Авторы изобретения

В. В. Васильев, А. Г. Додонов и С. Е. Прозоров

Институт кибернетики АН Украинской ССР

Заявитель

УСТРОЙСТВО ДЛЯ МОДЕЛИРОВАНИЯ ПУТЕЙ НА ГРАФЕ

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

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

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

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

5 графа.

Предлагаемое устройство содержит генератор импульсов 1, устройство управления 2, блок моделей ветвей 8, блок моделей узлов 4.

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

Узел управления 5 связан со входами счет15 чиков 8, 9 с узлом сравнения б, а также полюсами 11, 12, 18 соответственно с генератором импульсов, блоком моделей ветвей 8, блоком моделей узлов 4. Узел сравнения б соединен с выходами задатчика допустимых значений

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

25 модели ветвей, выполненные, например, по схеме на фиг. 3, где изображены сдвиговый регистр 14, триггер 15, двухвходовые схемы совпадения 1б и 17, трехвходовая схема 12 совпадения, диоды 19 и 20, двухвходовая схе30 ма 21 разделения.

337792

Вход 22 регистра 14, емкость которого соответствует длине ветви, является функциональным входом модели ветви, а его выход соединен с первыми входами схем совпадения 16, 17, 18. Единичный вход триггера 15 подключен к выходу схемы совпадения 18, а его единичный выход соединен со вторым входом схемы совпадения 17 и через диоды 19, 20 с полюсами 23, 24 модели ветви.

Вторые входы схем совпадения 16, 17 образуют полюсы 25, 26 модели ветви, соединенные с полюсами 12 узла управления 5, а третий вход схемы совпадения 18 — полюс модели ветви 27. Выходы схем совпадения 16, 17 через схему разделения 2(образуют функциональный выход модели ветви 28.

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

80, 81,,82 и двухвходовая схема разделения 83.

Вход 84 схемы разделения 88 является функциональным входом модели узла, а второй вход указанной схемы разделения подключен к выходу схемы совпадения 82. Единичный выход триггера 29 соединен с одним из входов схемы совпадения 82, а его единичный и нулевой входы — соответственно с выходами схем совпадения 80, 31. Две пары входов схем совпадения 30, 31, единичный выход триггера 29, а также второй вход схем совпадения 82 образуют соответственно полюсы 85, 86, 87, 88, 89, 40 модели узла. Выход

41 схемы разделения 88 является функциональным выходом модели узла.

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

48 для фрагмента графа, данного на фиг. 5, а, изобра>кен на фиг. 5, б.

Предлагаемое устройство работает следующ им образом.

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

15, 29, регистры 14 и счетчики 8, 9 моделей ветвей, моделей узлов и устройства управления находятся в нулевом состоянии.

Кроме того, на задатчике пределов длины пути 7 устанавливаются коды, соответствующие минимальному и максимальному заданным допустимым значениям длины и искомого пути на графе. (В случае однозначно заданной длины искомого пути эти два значения совпадают) . При пуске на полюс 25 моделей ветвей из устройства управления подается разрешающий потенциал, а на вход 34 модели начального узла искомого пути — одиночный импульс, синхронизированный с импульсами генератора 1. Одновременно узел управления 5 разрешает поступление импульсов генератора

1 на вход счетчика 9 и по совпадению с разрешающим потенциалом единичного выхода триггера 29 модели конечного узла искомого пути — на вход счетчика 8. При отсчете числа

5 импульсов, соответствующего заданному минимально допустимому значению длины искомого пути, узел сравнения 6, осуществляя сравнение кода счетчика импульсов 9 и кода заданного минимального значения длины ис10 комого пути задатчика пределов длины пути 7, выдает сигнал в узел управления. ?To совпадению указанного сигнала с разрешающим потенциалом единичного выхода триггера 29 модели конечного узла искомого пути, узел уп15 равления выдает разрешающий потенцйал на полюс 26 моделей ветвей, тем самым. разрешая по одному входу прохождение сигналов через схему совпадения 18 моделей ветвей.

Так как на вторых входах схем совпадения

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

zs регистра 14 модели любой из указанных ветвей приводит к установке триггера 15 через схему совпадения 18 в единичное состояние, регистрируя тем самым принадлежность соответствующей ветви искомому пути. Этот же чо импульс, проходя последовательно схему совпадения 16, схему разделения 21 модели указанной ветви, схему разделения 88 модели конечного узла поступает в узел управления 5, который при этом запрещает поступление импульсов генератора 1 на входы счетчиков 8, 9 и подает запрещающие потенциалы на полюсы

25, 26 моделей ветвей. В результате в указанных счетчиках устройства управления записано число импульсов, соответствующее изве4р стной лежащей в заданных пределах допуска длине пути, проходящего через первую найденную ветвь, входящую в конечный узел искомого пути.

Затем узел управления осуществляет сброс

4 в нулевое состояние счетчика 9 в устройстве управления и регистре 14 моделей ветвей, а также выдает импульс, синхронизированный с импульсами генератора 1, на полюс 36 моделей узлов и, сдвинутый относительно первого, второй импульс — на полюс 87 моделей узлов.

При этом, в соответствии с коммутацией моделей ветвей и моделей узлов (см. фиг. 5) первый указанный импульс установит в единичное состояние триггер 29 модели начального узла первой найденной ветви, а второй — сбросит в нулевое состояние триггер 29 модели конечного узла упомянутой ветви (который, в данном случае, совпадает конечным узлом искомого пути), так как на входе 85 схемы совпадения 80, управляющей единичным входом триггера 29 модели первого упомянутого узла и на входе 88 схемы совпадения 81, управляющей нулевым входом триггера 29 модели второго узла, имеется разрешающий по

65 тенциал с единичного выхода триггера 15 мо3 37792

15

20 дели первой найденной ветви, соединяющей эти узлы. Далее узел управления подает одиночный импульс, синхронизированный с импульсами генератора 1, на полюс 40 моделей узлов и одновременно разрешает поступление импульсов генератора 1 на вход счетчика 9 в устройстве управления. Указанный импульс проходит последовательно схему совпадения

82, схему разделения 88 модели начального узла первой найденной ветви, триггер 29 которой разрешает прохождение импульса потенциалом единичного выхода, и поступает на входы 22 регистров 14 моделей ветвей, выходящих из данного узла. Импульс переноса с выхода регистра 14 модели первой найденной ветви по разрешению потенциала единичного выхода триггера 15 проходит через схему совпадения 17 и далее через схему разделения

21 модели указанной ветви, схему разделения

88 модели конечного узла искомого пути поступает в узел управления 5, который при этом запрещает поступление импульсов на вход счетчика 9 устройства управления.

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

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

По сигналу совпадения кодов счетчиков 8, 9 регистрируемому узлом сравнения б, узеч управления 5 выдает импульс на полюс 2б моделей ветвей,и запрещает поступление импульсов на вход счетчика 9. Так как прн этом содержимое счетчика 9 дополняется разностью между известной длиной искомого пути и gëèной первой найденной ветви, ему поинадлсжащей, то описанном моменту времени подачи импульса на полюс 2б моделей ветвей сооТветствует появление импульса переноса на выходе регистра 14 модели одной нз ветвей, входящих в начальныи узе.ч первой найденной ветви. Совпадение указанны импульсов с разрешающим потенциалом единичного выхода триггера 29 модели упомян "того узла приводит к установке триггера 15 соответствующей модели ветви и регистрации, таким образом, втопой ветви, принадлежащей искомому пути. Процесс определения последующих ветвей протекает аналогично описанному циклу опоеделения второй гетви искомого пути. В каждом таком цикле определения новой ветви, перед «опросом» мочели графа с noMoIIJbIo одиночного импульса, засылаемого в модель начального узла искомого пути, в единичное состояние устанавливается триггер 29 модели только того узла, в котором оканчивается искомая ветвь, а в счетчик 9 устройства управления заносится число импульсов, г5

З0

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

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

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

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

Устройство для моделирования путей на графе, содержащее блок моделей ветвей, блок моделей узлов, связанные между собой в соответствии с топологией сети, и соединенное с ними устройство управления, ко входу которого подключен генератор импульсов, отлачающееся тем, что, с целью определения пути заданной длины на графе, оно содержит два счетчика, блок индикации отсутствия решения, задатчик допустимых значений длины искомого пути и узел сравнения, причем устройство управления соединено со входами двух счетчиков, входы которых подключены ко входам узла сравнения, третий вход которого соединен с задатчиком допусти IbIx значений lIJIHны искомого пути, а выход — с устройством управления, к выходу одного из счетчиков подключен блок индикации отсутствия решения; модель ветви блока моделей ветвей содержит сдвиговый регистр„две двухвходовые схемы совпадения, схему разделения, триггер, трехвходовую схему совпадения и разделительные диоды, причем вход сдвнгового регистра подключен ко входу блока моделей, а выхоч — к одному из входов схем совпадения, второй вход одной нз двухвходовых схем совпадения соечинен с единичныM выходом триггера н чеоез разделительные диоды — с полюсами модели ветви, другие входы остальных схем совпа; ения подключены к управляющим входам блока моделей ветвей. выходы двухвхо",0âüï схем совпадения через схему разделения подключены к выходу блока моделей ветви, выход трехвходовой схемы совпадения соединен с единичным входом триггера, а модель узла блока моделей уз.чов выполнена на триггере, трех схемах совпадения и схеме разделения, причем один нз входов схемы разделения соединен со входом модели узла, а другой — с вы одом одной из схем совпадения, входы которой подключены к управляющим входам блока моделей узлов и к

337792

Уиг 1

Фи8. 2

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

337792

37 38 Л О

@иг. е

Составитель С. Белан

Техред Л. Богданова

Корректор Т. Гревцова

Редактор Е. Гончар

Типография, пр. Сапунова, 2

Заказ 2484/7 Изд. № 1021 Тираж 448 Подписное

ЦНИИПИ Комитета по делам изобретений и открытий при Совете Министров СССР

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