Моделирующее устройство для нахождения оптимальной связывающей сети

ойсоюзнатр| па о > скате

О П И C "À - - НЧФ Е

ИЗОБРЕТЕН И Я

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

276538

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

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

Республик

+3ф ф ф

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

Заявлено 11.||.1969 (1т1 1321042/18-24) с присоединением заявки №

Приоритет

Опубликовано 14.VII.1970. Бюллетень № 23

Дата опубликования описания 29.X.1970

Кл. 42m4, 7/62

МПК С 06g 7/62

УДК 681.333.51 (088.8) Комитет по делам изобретений и открытий при Совете Министров

СССР

Автор изобретения

В. В. Васильев

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

Заявитель

МОДЕЛИРУЮЩЕЕ УСТРОЙСТВО ДЛЯ НАХОЖДЕНИЯ

ОПТИМАЛЬНОЙ СВЯЗЫВАЮЩЕЙ СЕТИ

Изобретение относится к области счетно-решающей техники.

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

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

«И» подключен соответственно к нулевому и единичному входам триггера с ключом на выходе, причем входы счетчиков импульсов всех моделей ветвей объединены и подключены к схеме пуска и регенерации устройства, вторые входы всех двухвходовых схем «И» подключены к генератору импульсов тактовой частоты, сдвинутых относительно счетных импульсов, вторые входы трехвходовых схем «И. подключены к генератору тактовых импульсов, сдвинутых относительно счетных импульсов и импульсов тактового питания двухвходовых схем «И», а третьи входы трехвходовых схем «И» соединены с выходом схемы

«НŠ— И», подключенной своими входами к точкам соединения ключей, одна из которых соединена с выходом источника напряжения.

На фиг. 1 приведена схема модели ветви графа; на фиг. 2 — схема устройства в целом.

Предлагаемое устройство содержит ключ 1, триггер 2, схемы «И» 3 и 4, счетчик 5 импульсов, условное обозначение модели ветви — элемент 6, входы и выходы (полюсы) 7 — 17модели, источник 18 напряжения, условное обозначение модели графа — цепь 19, полученной соединением ее элементов 6 между собой в соот10 ветствни с топологией сети, схему «НŠ— И» 20, схему «И» 21, счетчик 22 импульсов, триггер

28 цепи управления и входы и выходы (полюсы) 24 — 85 элементов устройства.

В исходном состоянии триггеры 2 моделей

15 ребер (см. фиг. 1) находятся в единичном состоянии. Сигналы единичных выходов 7 триггеров управляют ключами 1, удерживая их в замкнутом состоянии. В этом состоянии полюсы 8 и 9 замкнуты между собой. В счетчики 5

20 предварительно заносятся количества импульсов, пропорциональные величинам мер ребер

1 (т, j) в прямом коде, если предполагается решить задачу о нахождении кратчайшей связывающей сети, и в дополнительном коде. если

25 нужно решать задачу о нахождении длиннейшей связывающей сети.

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

30 полюсами 15 и 16 схем «И» 8 и 4, 25 Моделирующее устройство для нахождения оптимальной связывающей сети, содержащее соединенные между собой в соответствии с топологией сети модели ее ветвей на счетчиках импульсов, триггерах, ключах и логических

З0 элементах, отличающееся тем, что, с целью упрощения схемы устройства, в нем счетчик импульсов каждой модели ветви через двухвходовую и трехвходовую схемы «И» подключен соответственно к нулевому и единичному

З5 входам триггера с ключом на выходе, причем входы счетчиков импульсов всех моделей ветвей объединены и подключены к схеме пуска и регенерации устройства, вторые входы всех двухвходовых схем «И» подключены к генера40 тору импульсов тактовой частоты, сдвинутых относительно счетных импульсов, вторые входы трехвходовых схем «И» подключены к генератору тактовых импульсов, сдвинутых относительно счетных импульсов и импульсов

45 тактового питания двухвходовых схем «И», а третьи входы трехвходовых схем «И» соединены с выходом схемы «НŠ— И», подключенной входами к точкам соединения ключей, одна из которых соединена с выходом источника

50 напряжения.

На полюсы 14 схем «И» подключены выходы счетчиков 5 импульсов. На полюсы 17 подается сигнал нарушения связности графа. Входы

18 всех счетчиков 5 объединены и подключены к схеме пуска и регенерации информации, содержащей триггер 28, схему «И» 21 и счетчик

22, находящийся перед началом работы схемы в нулевом состоянии (см. фиг. 2).

Ключи 1 соединяются между собой в соответствии с топологией графа. К одному пз узлов получившейся электронной цепи 19 подключается источник напряжения 18, изображающий сигнал логической единицы. Все- остальные узлы подключаются к входам 24 — 27 схемы «НŠ— И» 20, которая выполняет в данном случае роль индикатора связности графа, моделью которого является цепь 19. Сигнал на выходе схемы «HE — И» 20 появляется в том случае, если хотя бы в одном узле цепи 19 исчезает сигнал логической единицы, что будет говорить о нарушении связности графа.

В исходном состоянии все ключи 1 замкнуты, и сигнал источника 18 имеется на всех узлах цепи 19.

При подаче сигнала пуска на полюс 84 триггер 28 устанавливается в единичное состояние и подает разрешающий сигнал на вход 88 схемы «И» 21. Импульсы первой фазы генератора тактового питания, подключенного к входу

29, схемы «И» 21, начинают поступать на входы счетчиков моделей ребер и счетчика 22 регенерации. Триггер 28 сбрасывается в нулевое состояние сигналом переполнения счетчика 22.

В счетчики 5 поступает, таким образом, количество импульсов, равное их полной емкости, что обеспечивает восстановление предварительно записанной в них информации.

В некоторый момент времени, синхронный с первой фазой тактового генератора, переполняется один из счетчиков 5, соответствующий ребру графа с максимальной мерой. Выходной сигнал этого счетчика подает разрешение на полюс 14 схем «И» 8 и 4, которое будет действовать в течение одного периода тактового питания. Импульс второй фазы генератора устанавливает триггер 2 в нулевое состояние по входу 11, ключ размыкается и исключает из рассмотрения такую ветвь. Если при этом не нарушается связность графа, схема «НŠ— И»

20 не выдает разрешающего потенциала на полюсе 17, и импульс третьей фазы (полюс

1б) не изменяет состояния триггера.

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

5 приведет к нарушению связности графа. Б этом случае ребро, выключенное по сигналу с полюса 15, будет снова включено по сигналу с полюса 1б, который проходит по схеме «И» 4 на вход установки единицы триггера 2.

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

15 ребра искомой сети, будут находиться на полюсах 7.

Величина полной меры (суммарной длины) полученной сети может быть получена опросом содержимого счетчиков сети с помощью

20 накопительного счетчика (на фигурах не показан).

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