Устройство для обнаружения циклов на графе

G Л K--А Й- -И - Е

ИЗОБРЕТЕН Ия

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

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

Респ;Слик

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

Заявлено 05.VI.1969 (№ 1334628/18-24) с присоединением заявки №вЂ”

Приоритет—

Опубликовано 28.IX.1970. Бюллетень № 30

Дата опубликования описания 13.I.1971

К,л, 42m, 7/48

Комитет по делам изобрс1еиий и отKpb!THY при Совете Микис ров

GCCP

1Ц(К б 06 7/48

УДК 681.333(088.8) Автор изобретения

Э. 3. Трайнин

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

Заявитель

УСТРОЙСТВО ДЛЯ ОБНАРУЖЕНИЯ ЦИКЛОВ НА ГРАФЕ

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

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

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

Схема устройства показана на чертеже.

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

1, связанные с вертикальными и горизонтальными шинами матрицы. Диагональными элементами последней являются источники тока

2, соединенные с первичными обмотками 3, 4 грансформаторов 5. Вторичные обмотки 6, 7 трансформаторов связаны со входами разделительной схемы 8,:выход которой соединен со схемой 9 сигнализации или управления. Управление ключами осуществляется генератором импульсов 10 и схемой распределителя 11.

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

На каждом такте генератора импульсов замыкается один из ключей в электрической цепи матричной структуры. Это состояние

5 ключа сохраняется после окончания такта с помощью са моблокировкн реле нли другим способом.

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

На i-том шаге генератора при замыкании к 110 13, который В совок1 пности с ранее заыкнутымп ключамн образует контур, через nepI3Hчные обмотки соответствующих трансфор15 маторов протекает ток. При этом во вторичных обмотках этих трансформаторов нндуцнруются импульсы напряжения, которые поступают на соответствующие входы разделительной схемы 8.

20 Импульс с выхода разделительной схемы пос1упает на вход схемы 9, используемой для сигнализации или для выдачи команды на запирание последнего в выбранной последовательности кл!оча.

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

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

Составитель А. Вейц

Редактор Ю. Полякова Техред Л. Я. Левина

Корректоры М. Ф. Иванова и Г. С. Мухина

Заказ б494/9 — 70 Тираж 480 Подписное

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

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

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