Устройство для синтеза ациклической сети на графе

 

О П И-=C--А- Н- И E

ИЗОБРЕТЕНИЯ

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

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

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

Республик (61) Дополнительное к авт. свид-ву— (22) Заявлено 040176 (21) 2310709/18-24 с присоединением заявки РЙ (23) Приоритет— (43) Опубликовано 25.12.78. Бюллетень № (45) Дата опубликования описания 2 1278 (51) М. Кл.

Q 06 С1 7/122

Государственный комитет

Совета Министров СССР по делам изобретений и открытий (53) УДК 681. 333 (088.8) (72) Автор изобретения

Э, 3, Трайнин (71) Заявитель

Ордена Ленина институт кибернетики Академии наук украинской ССр (541 УСТРОЙСТВО ДЛЯ СИНТЕЗА АЦИКЛИЧЕСКОЙ СЕТИ

НА ГРАФЕ

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

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

Наиболее близким техническим решением к рассматриваемому является устройство для синтеза ациклической сети на графе, содержащее генератор импульсов, подключенный ко входу распре- 25 делителя импульсов, вертикальные и "оризонтальные шины, которые образуют сетку, в узлах которой, расположенных по одну сторону от главной диагонали, включены управляемые ключи, со- ЗО единяющие соответствующие вертикальные шины с горизонтальными, узлы сетки, расположенные на главной диагонали, соединены накоротко {2) .

Однако известное устройство отличается сложностью и низким быстродействием.

Цель изобретения — упрощение устройства и повышение его быстродействия.

Это достигается тем, что в устройство введены дополнительные элементы

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

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

638974

Формула изобретения

3 тальные шины матрицы, и диагональных корсткозамкнутых перемычек 7 и 8, связывающих одноименные горизонтальные и вертикальные шины матрицы . Ключи управляются с помощью элементов И 9-14„ элементов ИЛИ-НЕ 15, 1б и 17 и распределителя 19 импульсов, вход которого связан с выходом генератора 18 импульсов, а выходы 20-25 которого соединены с входами соответствующих элементов ИЛИ-HE и первыми входами элементов И.

Выходы элементов ИЛИ-НЕ соединены )0 с соответствующими горизонтальными шинами матрицы. Вторые входы элементов

И 9-14 соединены с соответствующими .вертикальными шинами матрицы.

К каждому элементу ИЛИ-HK подключе- у5 на группа тех выходов распределителя

19 импульсов, которые связаны с элементами И соответствующей строки матрицы

Так, выходы 20, 21 и 22 блока 19 заведены на входы элемента ИЛИ-HE выход которого связан с первой горизонтальной шиной матрицы. Одновременно выходы 20, 21 И 22 блока 19 соединены с первыми входами элементов И 9, 10 и 11, расположенными в первой строке матрицы. Аналогичным образом орга— низованы связи для выходов 23 и 24 и выхода 25 блока 19. устройство работает следующим образом.

На каждом такте генератора 18 импульсов на каком-либо выходе распределителя 19 импульсов появляет"я сигнал.

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

ij контур. В противном случае запрещающий сигнал на втором входе рассматриваемого элемента И отсутствует„ и на выходе этого элемента появляется импульс на замыкание соответствующего ключа в матрице. Это состояние ключа сохраняется с помощью самоблокировки реле или другим способом. Последовательность замыкания ключей выбирается по определенному критерию в зависи- 55

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

Включения любой последовательности клю- 50

ЧВЙ, за исключением циклических послеЙОВательностей. Если замыкание опрашиваемого ключа приведет к возникновению 85 цикла, этот ключ замкнут не будет, так как одновременно с разрешающим сигналом, поступающим на первый вход соответствующего элемента И, на второй вход этого элемента через систему ранее замкнутых ключей и короткозамкнутых перемычек поступит запрещающий сигнал. Благодаря инерционности ключей (реле) исключается явление гонок, т.е. замыкание ключа до прихода запрещающего сигнала. Так, если на предыдущих тактах замкнуты ключи 2, 3 и 4, уже невозможно замкнуть ключ 5 сигналом с выхода 23 распределителя 19, поскольку одновременно с разрешающим сигналом, поступающим с этого выхода на первый вход элемента И 13, на второй ее вход приходйт запрещающий сигнал по следующей цепи: выход элемента ИЛИНЕ 1б-ключ 4-вертикальная шина -ключ

2-шина -ключ 3-шина К вЂ” второй вход элемента И 13.

Если, например, на предыдущих тактах замкнуты ключи 1 и 2, уже невозможно замкнуть ключ 4, поскольку одновременно с разрешающим сигналом, поступающим с выхода 24 блока 19 на первый вход элемента И 12, на второй ее вход пройдет запрещающий сигнал по цепи: выход элемечта ИЛИ-НЕ 1б — короткозамкнутая перемычка 7 — вертикальнаа шина матрицы — ключ 1 — шина 1— ключ 2 — вертикальная шина 1, — второй вход элемента И 12.

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

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

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

Техред З.Фанта Корректор Н. Ковалева

Редактор Т. Клюкина

Заказ 7283/38 Тираж 784 Подписное

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

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

Филиал ППП Патент, r. Ужгород, ул. Проектная, 4

5 638974 дого элемента И подключен к управляющему входу соответствующего ключа. М

Источники информации, принятые во внимание при экспертизе: 9

1. Авторское свидетельство СССР

276538, кл.(j Об G 7/122, 1969.

2. Авторское свидетельство СССР

282763, кл. G Об Q 7/122, 1969 °