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

О П И 1 Г."-А"НЧФ ЕИЗОБРЕТЕНИЯК АВТОРСКОМУ СВИДЕТЕЛЬСТВУ 276838 Союз Советских Социалистических,1 т 1 е 1321042/18-24 Кл, 42 ттт 4, 7/6 с присоединением заявкиПриоритет 1 ПК С 06 Я 7 Ковтитет по дел изобретений и открыт при Совете Министре СССРЛвторнзобрете В. В. Васильев нститут кибернетики АН Украинской ССРявител ОДЕЛИРУЮЩЕЕ УСТРОЙСТВО ДЛЯ НАХОЖД ОПТИМАЛЬНОЙ СВЯЗЪВАЮЩЕЙ СЕТИ ИЯ Изобретение отно шающей техники.Известны счетно- держащие соединен ветствии с тополоп на счетчиках импул логических элемент не обеспечивают нах зывающей сети. птся к области счетно решающие устр ные между соб ей сети модели ьсов, триггерах, ах. Известные ождения оптима оиства, соой в соотее ветвейключах и устройства льной свяУстройство отличается от известных тем, что в нем счетчик импульсов каждой модели ветви через двухвходовую и трехвходовую схемы И подключен соответственно к нулевому и единичному входам триггера с ключом на выходе, причем входы счетчиков импульсов всех моделей ветвей объединены и подключены к схеме пуска и регенерации устройства, вторые входы всех двухвходовых схем И подключены к генератору импульсов тактовой частоты, сдвинутых относительно счетных импульсов, вторые входы трехвходовых схем И. подключены к генератору тактовых импульсов, сдвинутых относительно счетных импульсов и импульсов тактового питания двухвходовых схем И, а третьи входы трехвходовых схем И соединены с выходом схемы НЕ - И, подключенной своими входами к точкам соединения ключей, одна из которых соединена с выходом источника напряжения. На фнг, 1 приведена схема модели ветвиграфа; на фиг. 2 - схема устройства в целом.Предлагаемое устройство содержит ключ 1,триггер 2, схемы И 3 и 4, счетчик 6 импульсов, условное обозначение модели ветви - элемент 6, входы и выходы (полюсы) 7 - 17 модели, источник 18 напряжения, условное обозначение модели графа - цепь 19, полученной соединением ее элементов 6 между собой в соот 10 ветствни с топологией сети, схему НЕ - И 20,схему И 21, счетчик 22 импульсов, триггер23 цепи управления и входы и выходы (полюсы) 24 - 36 элементов устройства.В исходном состоянии триггеры 2 моделей15 ребер (см. фиг. 1) находятся в единичном состоянии. Сигналы единичных выходов 7 триггеров управляют ключами 1, удерживая их взамкнутом состоянии. В этом состоянии полюсы 8 и 9 замкнуты между собой. В счетчики 620 предварительно заносятся количества импульсов, пропорциональные величинам мер ребер1 (т, 1) в прямом коде, если предполагается решить задачу о нахождении кратчайшей связывающей сети, и в дополнительном коде. если25 нужно решать задачу о нахождении длиннейшей связывающей сети.К схеме устройства должен быть подключенгенератор трехтактного импульсного питания,вторая и третья фазы которого соединены с30 полюсами 16 и 16 схем И 3 и 4,25 Моделирующее устройство для нахожденияоптимальной связывающей сети, содержащее соединенные между собой в соответствии с топологией сети модели ее ветвей на счетчиках импульсов, триггерах, ключах и логических 30 элементах, отличающееся тем, что, с цельюупрощения схемы устройства, в нем счетчик импульсов каждой модели ветви через двухвходовую и трехвходовую схемы И подключен соответственно к нулевому и единичному 55 входам триггера с ключом на выходе, причемвходы счетчиков импульсов всех моделей ветвей объединены и подключены к схеме пуска и регенерации устройства, вторые входы всех двухвходовых схем И подключены к генера тору импульсов тактовой частоты, сдвинутыхотносительно счетных импульсов, вторые входы трехвходовых схем И подключены к генератору тактовых импульсов, сдвинутых относительно счетных импульсов и импульсов 45 тактового питания двухвходовых схем И, атретьи входы трехвходовых схем И соединены с выходом схемы НЕ - И, подключенной входами к точкам соединения ключей, одна из которых соединена с выходом источника 50 напряжения,На полюсы 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, и импульс третьей фазы (полюс 1 б) не изменяет состояния триггера.Описанный процесс будет продолжаться дотех пор, пока выключение очередного ребра не 5 приведет к нарушению связности графа. Б этомслучае ребро, выключенное по сигналу с полюса 15, будет снова включено по сигналу с полюса 1 б, который проходит по схеме И 4 на вход установки единицы триггера 2.10 Таким образом, за один цикл работы схемыпуска и регенерации выключаются и останутся в этом состоянии модели ребер графа, не составляющие искомой оптимальной сети. Сигналы, свидетельствующие о принадлежности 15 ребра искомой сети, будут находиться на полюсах 7.Величина полной меры (суммарной длины)полученной сети может быть получена опросом содержимого счетчиков сети с помощью 20 накопительного счетчика (на фигурах не показан). Предмет изобретения