Устройство для поиска элементарных путей направленного графа

 

ОП ИСАНИ Е

ИЗОБРЕТЕНИЯ

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

25Î547

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

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

Республик ®х

Зависимое от авт, свидетельства М

Заявлено 12.Ч11.1967 (Эй 1172388/18-24) с присоединением заявки М

Приоритет

Опубликовано 12.VIII.1969. Бюллетень Мс 26

Дата опубликования описания 4 Ч1.1970

Кл. 42m>, 7/48

МПК 6 06g

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

СССР

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

Б. И. Блажкевич и Е. Д, Михайлова

Физико-механический институт АН Украинской ССР

Заявитель

УСТРОЙСТВО ДЛЯ ПОИСКА ЭЛЕМЕНТАРНЫХ ПУТЕЙ

НАПРАВЛЕННОГО ГРАФА

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

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

K()MMóTàöHoíHûå ключи, балластные резисторы, логические схемы «И» и «НЕ», источник питания, генератор счетных импульсов, источник единичных импульсов, пусковой переключатель, соответствующие не заходящим в начало и .не исходящим из конца путей дугам графа управляемые ключи с индикаторами включения и управляющие этими ключами рабочие триггеры, соответствующие вершинам графа, не являющимся началом или концом путей, и буфферные триггеры, причем управляющие триггеры, соответствующие дугам графа, заходящим в одну вершину, и буфферный триггер, соответсввующий этой же вершине, соединены |в кольцевые коммутаторы, первый из которых присоединен к выходу первой логической схемы «И», а последующие — с выходом последнего триггера предыдущего коммутатора, содержащее также триггер конца поиска, вход которого присоединен к выходу последнего триггера в последнем кольцевом ком5 мутаторе, а выход — к отдельному входу первой логической схемы «И», распределитель, состоящий из соответствующих отдельным вершинам графа пар вертикальны.: шин, каждая из которых через балластный резистор присо10 единена к незаземленному, а через коммутационный ключ с нормально разомкнутыми контактами — к заземленному зажимам источника питания, и пар горизонтальных шин, причем рабочие вертикальная и горизонтальная

15 шины, соответствующие одной и той же вершине графа, соединены вместе.

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

20 логические схемы «НŠ— ИСКЛЮЧАЮЩЕЕ

ИЛИ», входы которых соединены с вертикальными шинами распределителя, соответствующими этим же вершинам, а выходы — к отдельным входам второй логической с емы «И», 25 выход которой через логическую схему «НЕ присоединен к одному входу третьей логической схемы «И», второй вход которой соединен с выходом генератора счетных импульсов, а выход — с неподвижным контактом пусково30 го переключателя, второй неподвижный кон250547 такт последнего присоединен к .выходу генератора единичных импульсов, а подвижной контакт — ко второму входу первой логической схемы «И», рабочая .вертикальная шина, соогветствующая началу путей, и вспомогательная вертикальная шина, соответствующая концу путей, через соответствующие коммутационные ключи с замкнутыми, контактами присоединены,к заземленному зажиму источника питания; управляемые ключи, соответствующие отдельным дугам графа, содержат две пары контактов, соединяющих пару вертикальных шин, соответствующих вершине графа, из которой выходит данная дуга, с парой горизонтальных шин, соответствующих вершине графа, is которую эта дуга входит; вторые горизонтальные шины распределителя присоединены к заземленному зажиму источника питания.

На фиг. 1 приведен при мер направленного графа; на фиг. 2 — схема устройства для меха низированного поиска путей;,на фиг. 3 — функциональная схема дополнительной части устройства, предназначенной для автоматизации операций, связанных с поиском, путей; на фиг. 4 —.принципиальная схема стационарных блоков описываемого устройства; на фиг. 5— рабочая ячейка; .на фиг. 6 — нулевая ячейка; на фиг. 7 —,коммутационная ячейка; на фиг. 8— мостиковая ячейка.

Путем, направленного графа с и верши на ми

Х, j=1, 2, ..., и (см. фиг. 1), начинающегося в веригине Х> и кончающегося в вершине Х„ называется подмножество из т дуг (1

В соответсгвии с приведенным определением, если из,какой-то вершины Х > ФХ, исходит од на из дуг, образующих путь (Х„Х ), то из начала пути Х, в эту вершину должен вести путь (Х„Х; ), образованный этими дугами или некоторыми из них. Если же из вершины

Х, Х .не исходит ни одна из дуг, образующих путь (Х,, Х ), то путь (X„X> ), образованный упомянутым и дуга|ми, должен отсутствовать. В каждую из вершин Х> ФХ„Х может заходить .не более одной дуги, образующих,путь (Х„Х ). В состав дуг, образующих какой-либо из путей (Х,, Х„), не может входить ни одна из дуг графа, заходящих в начало пути Х, или исходящих ma конца пути Х .

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

Из дуг заданного графа .после исключения дуг, заходящих в начало пути Х; и исходящих из,пути Х, выбираются все возможные сочетания по 1, 2, ..., n — 1 дуг, в которых каждая заходит в иную вершину графа; про5

40 45

65 веряется наличие пути, образован ного выбранными дугами и ведущего нз вершины Х в вершину Х ; проверяется наличие путей, образованных выбранными ду гами и ведущих из вершины Xg Iso все:вершины, из которых исходит хотя бы одна из этих дуг; проверяется отсутствие путей, образова нных выбранными дугами и,ведущих из вершины Х, в вершины, из которых,не исходит ни одна из выбранных дуг.

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

Пусть требуется |найти все возможные элементарные:пути этого графа с началом в вершине Х и концом в вершине Х . В соответствии е этим из рассмотрения исключаем дуги а и d, заходящие в начало, путей Х,, и дуги g и l, исходящие из конца путей Х . Остальные дуги разобьем на группы, объединяющие дуги, заходящие в отдельные вершины, а именно (b, о) — дуги, заходящие в вершину Х, .(с, i) — в вершину Х>, (е, f, k) — в вершину Х»; (j, и) — в вершину Х i, (р, h, т) — в вершину Х„.

Рассмотрим некоторые сочетания из дуг, каждая из,которых принадлежит к иной группе.

Сочетание дуг (b,, е, р) представляет собой путь, так как имеется путь (XJ, ХА) в вершины Х1, Х, и Х>, из которых исходят дуги (р, 1, е), имеются пути из вершины Х,; а в вершину Хл 1, из которой не исходит ни одна из,выбранных дуг, путей из вершины Х, нет.

Сочетание дуг (b, f, и, т) пути не образуют, так как в вершинах Х, i и Х„, из.которых исходят соответственно дуги т и и, не ведут пути из .вершины Х . Не образует пути и сочетание дуг (b, i, е, 1, р), так как в вершину

Х», из которой IHB исходит ни одна из дуг данного сочетания, ведет образованный этими дугами путь из вершины Х, . Сочетание дуг (о, с, f, 1, т) образует путь, а вершины, из которых не исходили бы дуги данного сочетания, вообще .нет.

Устройство для ручного поиска путей по изложенному выше алгоритму (см. фиг. 2) IcOстоит из рабочих и вспомогательных си стем шин 1 и 2, ра бочих сдвоенных ключей 8, схем 4, выполняющих логическую операцию «НЕ—

ИСКЛЮЧАЮЩЕЕ ИЛИ», схемы совпадения5, балластных резисторов б, коммутационных ключей 7 и источника питания 8, Система ра бочих шич 1 образуется из соединенных попарно горизонтальных и вертикальных шин,,причем каждая inapa таких шин ставится в соответствие отдельной вершине графа. Система вспомогательных шинн 2 состоит из вертикальных шин, .каждая из которых соответствует отдельной вершине графа. Все вертикальные лины через отдельные балластные резисторы б присоединены к одному зажиму (например «минус») источника питания 8, а через коммутационные ключи 7 — ко второму его зажиму. Вертикальная, рабочая шина

250547

И вапомогательная шина, соответствующие одной и той же верши не графа, присоединены к двум разньгм входам отдельной схемы 4, вы полняющей логическую операцию «НЕ—

ИСКЛЮЧАЮЩЕЕ ИЛИ». На .выходе этой схемы имеется сигнал в там случае, если на ее обоих входах одновременно имеется сигнал или на обоих входах ситнал отсутствует. Выходы IcxBM 4 подключены к отдельным входам схемы совпадения 5, на выходе которой появляется сигнал только при наличии сигналов на всех без исключения ее входах.

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

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

Отдельные рабочие шины устройства (см. фиг. 2) обозначены индексами соответствующих вершин, графа;,вспомогательные шины— этими же индексами со IIITlpnxBMIH, Пары контактов рабочих ключей обозначены теми же буквами, что и дули, которым соответствуют да нные ключи, лричвм контакты,,присоединенные непосредственно к источнику ги .вспо могательным шинам, дополнительно обозначены штрихом, Раббота уст1ройства происходит таким образом, что замьгкаются рабочие сдвоенные ключи, соответствующие выбранному сочетанию дуг. Если при этом на входе схемы совпадения 5 .появляется сигнал, то все без исключения дуги данно го сочетания образуют, путь (Х <,Хг); при отсутствии такого сигнала такой путь .не существует или образуется не всеми дугами .выбранного сочетания.

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

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

Для того чтобы на выходе схемы совпадснпя имелся сигнал, необходимо, чтобы он имелся на выходе всех схвм «HE — ИСКЛЮЧАЮЩЕЕ ИЛИ», т. е., чтобы на обоих входах каждой из этих схем одновременно существовал сигнал ил и отсутствовал.

Для того чтобы не пропустить ни одного из путей заданного:графа, достаточно коммутацию сдвоенных рабочих ключей, присоединенных к шинам, производить в следующем порядке: в исходном положении замкнутым является только один ключ в горизонтальной шине, соответствующей концу, пути. Затем замыкаются по очереди ключи первой из горизонтальных шин, .причем до замыкания,последующего .ключа должен быть разсмкнут предыдущий. Следующий шаг — это выключение последнето ключа первой шины и включение первого ключа следующей горизонтальной шины. Затем снова включаются по очереди все ключи первой шины. Отключение последнего ключа первой шины совмещается с отключенивм первого ключа второй шины и включением следующего ее ключа и т. д. После ситуации, когда в нвокольких .первых горизонтальных шинах включены .последние ключи, все они вьгключаются, а,в последующей шине выключается включенный ключ (если таковой имеется) и включается следующий ло очереди ключ. Если среди упомянутых первых горизонтальных шин имеется шина, соответствующая концу пути, то одновременно,с выключением ее последнего ключа включается ее первый ключ. Поиск:путей прекращается, когда во всех горизонтальных шинах включены последние ключи.

На фиг. 3 представлена функциональная схема дополнительной части устройства, позволяющей производить автом атически выбор всех возможных сочетаний по 1, 2, ..., (n — 1) из дуг графа, которые мо гут образовывать его пути, и управлять коммутацией рабочих сдвоенных ключей 8 в соответствии с выбранным сочетанием дуг. Предполагается, что в данном случае рабочие .ключи являются управляемыми и снабжены индикаторами включения, например световыми.

Устройство состоит из рабочих триггеров 9, нулевых триггеров 10, схемы совпадения 1I с двумя входами, триггера козинца поиска 12, пускового переключателя 18, схемы совпаде,ния 14 с двумя входами генератора счетных

250547 импульсов 15, инвертора (схемы «НЕ») 16, генератора единичных импульсов 17.

Рабочие триггеры 9 подобно, как и рабочие сдвоенные ключи 8, ставятся в соответствие отдельным дугам графа, за исключением дуг, заходящих в начало путей,и исходящих из конца путей. Выход каждого рабочего триггера присоединен к цепи управления рабочего сдвоенного ключа, соответствующего той же дуге, что и сдвоенный кл|оч. Нулевые триггеры 10 ставятся в соответствие отдельным вершинам графа, за исключением вершин, являющихся началом и концом путей Х, и Х, . Нулевые трип еры 10 отличаются от рабочих только отсутствием соединения их выходов с цепями управления рабочих ключей. Триггеры, соответствующие дугам, заходящим.в одну и ту же вершину,,вместе с нулевым триггером, соответствующим данной вершине, если QHB не является концом путей, соединены по кольцевой схеме.

Первый из группы триггеров, образующих кольцевую схему, независимо от того, является он рабочим или нулевым, присоединяется к цепи сброса таким образом, что при включении этой цепи он устанавливается в рабочее состояние, характеризующееся готовностью триггера к опрокидыванию при подаче первого счетного импульса; остальные триггеры данной группы присоединены к цепи сброса таким образом, что при ее:включении переходят в нерабочее состояние. В рабочем состоянии рабочего триггера 9 с его выхода, подается в цепь управления соответствующего рабочего сдвоенного ключа 8 сигнал на замыкание обеих пар контактов и на срабатывание индикатора состояния ключей. Входы для счетных импульсов триггеров первой группы присоединяются к выходу схемы со|впадения 11, а последующей группы — к выходу последнего триггера inpeдыдущей группы. К выходу последнего триггера в последней группе триггеров присоединен вход для счетных импульсов триггера конца поиска 12, рабочий выход которого присоединен к одному из входов схемы совпадения 11; сигналом сброса триггера конца, поиска приводится в рабочее состояние. Второй вход схемы совпадения 11 через пару нормально замкнутых контактов пускового переключателя 18 присоединен к выходу схемы совпадения 14, один из входов которой подключен к выходу генератора счетных импульсов 15, а второй— через инвертор 15 — к выходу схемы совпадения 5; через, пару нормально разомкнутых контактов пускового переключателя 18 соответствующий вход схемы совпадения 11 присоединяется к выходу источника единичных импульсов 17.

Соединение рабочих и нулевых триггеров 9 и 10 и триггера конца поиска 12 (см. фиг. 3) соответствует решению задачи поиска путей графа (см. фиг. 1) с началом и концом путей

Х, и Х . Выходы отдельных рабочих триггеров 9 обозначены буквенными символами,пар контактов рабочих сдвоенных ключей, управ5

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

Работа устройства при автоматическом:поиске путей происходит таким образом, что при включенной цепи сброса первые триггеры в каждой группе триггеров находятся в рабочем состоянии, а обе пары контактов рабочих ключей 8, управляемых этими триггерами, замкнуты. Если дуги графа, соответствующие замкнутым ключам, образуют путь, то на выходе схемы совпадения 5 имеется сигнал, вследствие чего, подача счетных импульсов от генератора счетных импульсов 15 блокируется схемой совпадения 14, а состояние устройства после отключения цепи сброса остается неизменны м.

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

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

При возвращении системы триггеров 9 и 10 в исходное положение, вследствие срабатывания триггера конца поиска 12, подача счетных импульсов как от генератора счетных импульсов 15, та|к и от источника единичных .импульсов .17, прекращается ввиду отсутствия сигнала хотя бы на одном из входов схемы совпадения 11.

На фиг. 4 — 8 в,качестве .примера приведена схема одного из возможных вариантов!практического исполнения предлагаемого устройства, В этом варианте управляемые рабочие сдвоенные .ключи 8 вместе с индикаторами их включения .конструктивно объединены с управляющими этими ключами рабочими триггерами,в рабочей ячейке (см. фиг. 5), которые посредством штепсельных вилок через соответствующие разъемы присоединяются к системам рабочих и вспомогательных шин 1 и 2. Эти системы шин вместе с розетками, расположенными на пересечениях вертикальных и горизонтальных шин, образуют распределительное устройство, выделенное на фиг. 4 в виде блока 18. В виде отдельных ячеек, снабженных штепсельными вилками, выполнены и нулевые триггеры 9, схематически изображенные на фиг. 6.

Для соединения рабочих и нулевых триггеров в кольцевые схемы предусмотрены снабженные штепсельными вилками вспомогательные ячейки:,коммутационные (см. фиг. 7) и

250547

65

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

Вся схема устройства выполнена на полупроводни,ковых,приборах.

В качестве рабочих сдвоенных ключей используются полупроводниковые триоды Т1 и

Т, работающие iB ключевом режиме и управляемые,напряжением, снимаемым с коллектора тр иода Тз, .входящего IBMocTe с триодом Т4 в схему ра бочего триггера (см. фиг. 5).

В качестве индикатора включенного состояния ключей используется неоновая лампочка ./7, питаемая через трансформатор Тр от генератора на полупроводниковом триоде Т5, запускаемого тем же на пряжением, что и рабочие .сдвоенные ключи.

Схема нулевой ячейки собрана на триодах

Т6 и Т7 (см. фиг. 6) и является повторением триггерной схемы рабочей ячейки.

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

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

Благодаря этому, выход этого триггера соединяется со входом триггера конца поиска 12, собранного на триодах Ts и Т9 (см. фиг. 4).

Вход этого триггера .через инвертор на триоде Т1О присоединен к схеме совпадения 11.

Такое включение обеспечивает независимость состояния триггера, конца.поиска от потенциала шины распределителя ШСИ (шина счетных импульсов), через которую счетные импульсы подаются в кольцевую схему, образованную первой группой рабочих и нулевых триггеров. Второй вход схемы ll через пусковой переключатель 13,пр:исоединен или к схеме 14, или к генератору единичных импульсов 17 (источнику питания с последовательно включенным резистором RI).

При нажатии кноп|ки KI,переключателя 18 через резистор R I заряжаются конденсаторы С входных дифференцирующих цепочек триггеров 9 и 10 первого ряда;,при отпускании кнопки эти конденсаторы разряжаются, так как схема 14 в это время имеет потенциал земли, благодаря чему и появляется единичный положительный импульс, воздействующий на входы триггеров.

Кнапочный ключ К служит для присоединения цепи сброса к источнику питания при .подготовке устройства к а втоматической работе.

Схемы, выполняющие логическую о перацию эквивалентности «НŠ— ИСКЛЮЧАЮЩЕЕ

ИЛИ», собраны на транзисторах T« — Т,4. Сигнал (потенциал земли) на выходе этих схем, 5

1О

15 го

25 зо

ss

10 т. е. на коллекторе транзистора Т„, появляется только при наличии на обоих входах сигнала-потенциала земли, или отрицательного потенциала, т. е. при отсутствии сигнала.

Схема совпадения 5:образована транзисторами Т,5,с параллельно включенными переходами эмиттер — коллектор, работающими на общую нагрузку Rq. Схема выдает сигнал (в .данном случае отрицательный потенциал) только при наличии сигнала, т. е. потенциала земли на всех ее входах.

Схема «НЕ»,представляет собою обычный транзисторный инвертор.

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

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

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

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

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

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

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

«НŠ— ИСКЛЮЧАЮЩЕЕ ИЛИ», входы которых соединены с вертикальными шинами распределителя, соответствующими этим же sepшинам, а выходы — к отдельным входам второй логической схемы «И», выход которой через логическую схему «НЕ» присоединен .к од1р ному входу третьей лотической схемы «И», второй вход которой соединен с выходом генератора счетных им пульсов, а выход — с не подвижным:контактом пускового переключателя, второй неподвижный контакт последнего при1 соединен к выходу генератора единичных импульсов, а подвижной контакт — ко второму входу;первой логической схемы «И», рабочая вертикальная шина, соответствующая началу путей, и вспомогательная вертикальная шина, 20 соответствующая концу путей, через соответствующие коммутационные ключи с замкнутыми контактами, присоединены к заземленному зажиму и сточника питания; управляемые ключи, соответствующие отдельным ду гам графа, 2S содержат две пары контактов, соединяющих пару вертлкальных шин, соответствующих вершине графа, из которой выходит данная дуга, с парой горизонтальных шин, соответствующих вершине графа, в которую эта дуга входит;

Зр вторые горизонтальные шины распределителя присоединены к заземленному зажиму источника питания.

250547 иг Я

Ф., а

4 иг. В

Корректор О. Тюрина

Заказ 1628!2 Тираж 500 Подписное

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

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

Типография, пр. Сапунова, 2

4 иг 7

Редактор Е. Семанова

Составитель Л, Б. Дмитриева

Текрсд Л. Я. Левина