Устройство для определения оптимальной связывающей сети на графе

СПИ

ИЗОБРЕТЕНИЯ

28369 5 йоюз Соеетекиз

Сеомзлиетичеекиз

Рееоублиз

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

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

Заявлено ЗОХ!.1969 (№ 1342563/18-24) с присоединением заявки №

Приоритет

Опубликовано 06.Х.1970. Бюллетень ¹ 31

Дата опубликования описания 22.ХП.1970

Кл. 42m4 7/48

МПК G 06f 7/48

УДК 681.333 (088.8) Комитет ео деков изебретеиий и открытий ори Сееете Миииетрое

ССОР

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

3. 3. Трайнин

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

Заявитель

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

СВЯЗЫВАЮЩЕЙ СЕТИ НА ГРАФЕ

Изобретение относится к области электронного моделирования задач математического программирования.

Известны устройства для определения оптимальной связывающей сети на графе, выполненные на аналоговых или аналого-цифровых моделирующих устройствах.

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

Схема описываемого устройства изображен а н а чертеже.

Устройство содержит матричную структуру

1, состоящую из ключей 2, источников 8 тока и трансформаторов 4, ключи 5 и б, регулируемые источники 7 напряжения, сумматор 8 напряжений, индиктор 9 напряжения (вольтметр), индикатор 10 места неисправного сигнала (с потенциальной выдачей информации о месте экстремума), элементы ll задержки, трехстабильные элементы 12, схемы совпадения 18, разделительную схему 14 и ячейки сигнализации 15.

Расстояния между узлами графа задаются регулируемыми источниками 7.

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

При включении трехстабильные элементы

12 находятся в состоянии «011», открывая при этом ключи б. На каком-либо выходе схемы индикатора 10 появляется сигнал, устанавли10 вающий определенный элемент 12 в состояние «101».

Одновременно этот сигнал появится на входе схемы совпадения 13. Сигнал с выхода элемента 12 откроет соответствующий ключ 5 на

15 входе сумматора 8 и ключ 2 в матричной структу.ре 1. Если íà i-том шаге этот ключ 2 в совокупности с ранее замкнутыми ключами образует контур, то через первичные обмотки соответствующих трансформаторов протекает

20 ток. При этом во вторичных обмотках этих трансформаторов индуцируются импульсы напряжения, поступающие на соответствующие входы разделительной схемы 14. Импульс с выхода разделительной схемы поступает на

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

10, перебросит элемент 12 в состояние «110».

Прп этом ключи 5 и 2 установятся в первона30 чальное состояние. Ключ б независимо от но283695 (OCTBBHTCJIb A. В. Вейган

Техред Л. В. Куклина Корректор Т. А. Абрамова

Редактор Н. Поздняк

2аказ 3589)8 Тираж 480 Подписное

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

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

Типография, пр. Сапунова, 2 його состояния трехустойчивого элемента («101» или «110») запирается через время, равное длительности задержки элемента 11, после чего соответствующий источник 7отключается от индикатора 10, Таким образом, рассматирваемый элемент исключается и индикатор 10 выбирает новый экстремальный элемент, который, в свою очередь, проверяется на матричной структуре 1 на наличие циклов и затем отключается и т.д.

Если включение выделенного с помощью индикатора 10 элемента не вызывает возникновения подциклов, соответствующий элемент

12 остается в состоянии «101». При этом остаются замкнутыми ключ 2 в матричной структуре 1 и ключ б, передающий информацию на сумматор 8 напряжений.

Трехстабильный элемент, установленный в состояние «101» и не сброшенный затем в состояние «110», включает ячейку сигнализации

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

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

Устройство для определения оптимальной связывающей сети на графе, заданном с помощью матрицы расстояний, отличающееся

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

20 трансформаторов.