МОДЕЛИРУЮЩЕЕ УСТРОЙСТВО ДЛЯ НАХОЖДЕНИЯ ОПТИМАЛЬНОЙ СВЯЗЫВАЮЩЕЙ СЕТИ Советский патент 1970 года по МПК G06G7/122 

Изобретение относится к области счетно-решающей техники. Известны счетно-решающие устройства, содерл ащие соединенные между собой в соответствии с топологией сети модели ее ветвей на счетчиках импульсов, триггерах, ключах и логически.к элементах. Известные устройства не обеспечивают нахождения оптимальной связывающей сети. Устройство отличается от известных тем, что в нем счетчик имнульсов каждой модели ветви через двухвходовую и трехвходовую схемы «И подключен соответственно к нулевому и единичному входам триггера с ключом на выходе, причем входы счетчиков имнульсов всех моделей-ветвей объединены и подключены к схеме пуска и регенерации устройства, вторые входы всех двухвходовых схем «И подключены к генератору имнульсов тактовой частоты, сдвинутых относительно счетных импульсов, вторые входы трехвходовых схем «И. подключены к генератору тактовых нмпульсов, сдвинутых относительно счетных импульсов и импульсов тактового питания двухвходовых схем «И, а третьи входы трехвходовых схем «И соединены с выходом схемы «ИЕ -И, подключенной своими входами к точкам соединения ключей, одна из которых соединена с выходом источника напряжения. На фиг. 1 приведена схема Модели ветвн графа; на фиг. 2 - схема устройства в целом. Предлагаемое устройство содержит ключ /, триггер 2, схемы «И 3 и 4, счетчик 5 импульсов, условное обозначение модели ветви-элемент 6, входы и выходы (полюсы) 7-/7 модели, источник /5 напряжения, условное обозначение модели графа-цепь 19, полученной соединением ее элементов 6 между собой в соответствни с топологней сети, схему «ПЕ-И 20, схему «И 21, счетчик 22 импульсов, триггер 23 цепи управления и входы и выходы (полюсы) 24 - 35 элементов устройства. В исходном состоянии триггеры 2 моделей ребер (см. фиг. 1) находятся в единичном состоянни. Сигналы единичных выходов 7 триггеров управляют ключами }, удерживая их в замкнутом состоянии. В этом состоянии полюсы 8 и 9 замкнуты между собой. В счетчики 5 предварительно заносятся количества импульсов, пропорциональные величннам мер ребер / (/, /) в прямом коде, еслн предполагается рещнть задачу о нахождении кратчайшей связывающей сети, и в дополнительном коде, если нужно решать задачу о нахождении длиннейшей связывающей сети. К схеме устройства должен быть подключен генератор трехтактного импульсного питания, вторая и третья фазы которого соединены с tla полюсы 14 схем «И подключены выходы счетчиков 5 импульсов. На полюсы 17 подается сигнал нарушения связности графа. Входы 13 всех счетчиков 5 объединены и подключены к схеме пуска и регенерации информации, содерн :ащей триггер 23, схему «И 21 и счетчик 22, находящийся перед началом работы схемы в нулевом состоянии (см. фиг. 2). Ключи 1 соединяются между собой в соответствии с топологией графа. К одному из узлов получившейся электронной цепи 19 подключается источник напряжения 18, изображающий сигнал логической единицы. Все остальные узлы подключаются к входам 24 - 27 схемы «НЕ-И 20, которая выполняет в данном случае роль индикатора связности графа, моделью которого является цепь 19. Сигнал на выходе схемы «НЕ-И 20 появляется в том случае, если хотя бы в одном узле цени 19 исчезает сигнал лопиеской единицы, что будет говорить о нарушении связности графа. В исходном состоянии все ключи 1 замкнуты, н сигнал источника 18 имеется на всех узлах цени 19. При нодаче сигнала пуска на полюс 34 триггер 23 устанавливается в единичное состояние иподает разрещающий сигнал на вход 33 схемы «И 21. Импульсы первой фазы генератора тактового пнтания, подключенного к входу 29, схемы «И 21, начинают поступать на входы счетчиков моделей ребер н счетчика 22 регенерации. Триггер 23 сбрасывается в пулевое состояние сигналом переполнения счетчика 22. В счетчики 5 поступает, таким образом, количество импульсов, равное их полной емкости, что обеспечивает восстановление предварительно записанной в них информации. В некоторый момент времени, синхронный с первой фазой тактового генератора, переполняется один из счетчиков 5, соответствующий ребру графа с максимальной мерой. Выходной сигнал этого счетчика подает разрешение на полюс 14 схем «И 3 н 4, которое будет деиствовать в течение одного периода тактового питания. Имнульс второй фазы генератора устанавлнвает триггер 2 в нулевое состояние по входу 11, ключ размыкается и исключает из рассмотрения такую ветвь. Если нри этом не нарущается связность графа, схема «НЕ-И 20 не выдает разрешающего потенциала на нолюсе 17, и имнульс третьей фазы (полюс 16) не изменяет состояния триггера. Описанный процесс будет продолжаться до тех пор, пока выключение очередного ребра не приведет кнарущению связности графа. В этом случае ребро, выключенное по снгналу с нолюса 15, будет снова включено по сигналу с полюса 16, который проходит но схеме «И 4 на вход установки единицы триггера 2. Таким образом, за один цикл работы схемы пуска и регеперации выключаются и останутся в этом состоянии модели ребер графа, не составляющие искомой оитимальной сети. Сигналы, свидетельствующие о принадлежности ребра искомой сети, будут находиться на полюсах 7. Величина полной меры (суммарной длины) полученной сети может быть получена ойросом содержимого счетчиков сети с помощью накопительного счетчика (на фигурах не показан). Предмет изобретения Моделирующее устройство для нахождения оптимальной связывающей сети, содерл ащее соединенные между собой в соответствии с топологией сети модели ее ветвей на счетчиках импульсов, триггерах, ключах и логических элементах, отличающееся тем, что, с целью упрощения схемы устройства, в нем счетчик импульсов каждой модели ветви через двухвходовую и трехвходовую схемы «И подключен соответственно к нулевому и единичному входам триггера с ключом на выходе, причем входы счетчиков импульсов всех моделей ветвей объединены и подключены к схеме пуска н регенерации устройства, вторые входы всех двухвходовых схем «И подключены к генератору импульсов тактовой частоты, сдвинутых относительно счетных импульсов, вторые входы трехвходовых схем «И подключены к генератору тактовых импульсов, сдвинутых относительно счетных импульсов и импульсов тактового питания двухвходовых схем «И, а третьи входы трехвходовых схем «И соедииены с выходом схемы «НЕ-И, подключенной входами к точкам соединения ключей, одна из которых соединена с выходом источника напряжения.

I с