УСТРОЙСТВО для ПОИСКА ЭЛЕМЕНТАРНЫХ ПУТЕЙ НАПРАВЛЕННОГО ГРАФА Советский патент 1969 года по МПК G06G7/48 

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

Известно устройство для попска элементарных :путей напра/вленного графа, содержащее коммутационные ключи, балластные резисторы, логические схемы «И и «НЕ, источник питания, генератор счетных импульсов, источник единичных импульсов, пусковой переключатель, соответствующие не заходящим в начало и .не исходящим из конца путей дугам графа управляемые ключи с индикаторами включения и управляющие этими ключами рабочие триггеры, соответствующие вершинам графа, не являющимся началом или концом путей, и буф.ферные триггеры, причем управляющие триггеры, соответствующие дугам графа, заходящим в одну вершину, и буфферный триггер, соответст1вующий этой же вершине, соединены IB кольцевые коммутаторы, первый из которых присоединен к выходу первой логической схемы «И, а -последующие - с выходом последнего триггера предыдущего коммутатора, содержащее также триггер коппа поиска, вход которого присоединен к выходу последнего триггера в последнем кольцевом коммутаторе, а выход - к отдельному входу первой логической схемы «И, распределитель, состоящий из соответствующих отдельным вершинам графа лар вертикальных шин, каждая из которых через балластный резистор прпсоединена к незаземленному, а через коммутационный ключ с нормально разомкнутыми контактами - к заземленному зажимам источника Питания, я пар горизонтальных шин, причем рабочие вертикальная и горизонтальная

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

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

логические схемы «НЕ -ИСКЛЮЧАЮЩЕЕ ИЛИ, входы которых соединены с вертикальными шинами распределителя, соответствуюшими этим же вершинам, а выходы - к отдельным входам второй логической схемы «И,

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

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

Путем направленного графа с п Берщи«а1ми Xj, , 2, ..., п (см. фиг. 1), начинающегося в верщине Xj и кончающегося в вершине X , называется подмножество из т дуг ( ге-1), в которой одна дуга начинается в начале пути XI, начало последующей дуги совпадает iC КОНЦОМ предыдущей яути, а последняя т-2 дуга заходит в конец 1пути путь является элементарным, если np« прохождении пути ни одна из вершин графа не встречается более одного раза.

В соответст1вИИ с приведенным определением, если из .какой-то вершины X Х исходит одна из дуг, образующих путь (Xj, Х ),то из начала пути X в эту вершину .должен вести путь (Xf, Xj, образованный этими дугами или некоторыми из них. Бели же из вершины Х1ФХ не -исходит ни одна из дуг, образующих путь (j, , то путь (X;, Xj}, образованный упомянутьшИ дугами, должен отсутствовать. В каждую из вершин X , Х может заходить не более одной дуги, образующих путь (X i,Xk ). В состав дуг, образующих какой-либо из путей (Xi, Х), ие может входить ни одна из дуг графа, заходящих в начало пути XI или исходящих из конца пути X .

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

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

вершины Xi (ВО все верщины, из которых исходит хотя бы одна из этих дуг; проверяется отсутствие путей, образова нных -выбранными дуraiMH и ведущих из верщины Jj в вершины, из которых .не ИСХОД1ИТ ни одна из выбранных дут.

Выбранное сочетание дуг является элеме.нтарным путем, ведущим из ве ршины Xi в вершину Х только при позитивных результатах проверки. Пусть требуется найти все возможные элементарные пути этого графа с началом в вершине XI и концом в вершине X,,. Ъ соответств ви с этим из рассмотрения исключаем дуги and, заходящие в начало путей Xi, и дуги g и I, исходящие из конца путей Х. Остальные

дуги разобьем на группы, объединяющие дуги, заходящие в отдельные вершины, а именно (Ь, о) - дуги, заходящие в вершину Xi; (с, i) -в вершину Xj; (е, f, k) -ъ вершину Х ; (/, п) - в вершину Хп-1 (р, h, т) - в вершинуХ„.

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

Сочетание дуг (Ь, i, е, р} представляет собой путь, так как имеется путь (Х j, Х/,) е вершины Xi, X„ ц XJ, 3 которых исходят дуги {р, i, е), имеются пути из вершины а з вершину Хп-1, из которой не исходит ни одна из выбранных дуг, путей из вершины Х нет.

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

Хп-ь ИЗ которой 1не исходит ни одна из дуг данного сочетания, ведет образованный этими дугами путь из вершины Xf , Сочетание дуг (о, с, f, j, т) образует путь, а вершины, из которых не исходили бы дуги данного сочетания,

вообще нет.

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

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

и (вапоМОгательная шина, соответствующие одной и той же вершине графа, присоединены к двум разньгм входам отдельной схемы 4, выиолняющей логическую операцию «НЕ - ИСКЛЮЧАЮЩЕЕ ИЛИ. На выходе этой схемы имеется сигнал в том случае, если на ее обоих входах одновременно имеется сигнал ИЛ1И на обоих входах сигнал отсут1СТ1вует. Выходы схем 4 (подключены « отделыны-м входам схемы совпадения 5, на выходе которой появляется сигнал только при наличии сигналов на всех без исключения ее входах.

Каждый ИЗ рабочих сдвоенных ключей 3, количество которых приравнивается общему количеству дуг графа, уменьщенному на количество дуг, заходящих в начало иутей ,и исходящих ИЗ конца путей, ставится в соответствие отдельным дугам /графа, за исключением указанных выше дуг. Одна пара -контактов такого ключа присоединяется к .вертикальной рабочей шине, соответствующей вершине, из которой исходит дуга, которой иоставлен в соответствие данный КЛЮЧ, ,и к .горизонтальной рабочей шине, соответствующей трафа, в которую заходит эта дуга. Вторая лара контактов присоединяется к плюсовому зажиму источника иитания И к вспомогательной шине, соответствующей вершине графа, из которой исходит данная дуга.

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

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

Работа устройства происходит таким образом, что замыкаются рабочие сдвоенные ключи, соответствующие выбранному сочетанию дуг. Если при этом на входе схемы совпадения 5 появляется сигнал, то все без исключения дуги данного сочетания образуют путь (X i,X/i), при Отсутствии такого сигнала такой путь не существует или образуется не всеми дугами выбранного сочетания.

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

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

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

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

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

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

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

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

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

Устройство состоит из рабочих тр.иггеров 9, нулевых триггеров 10, схемы совпадения // с двумя входами, триггера конца поиска 12, пускового переключателя J3, схемы сов-падеимпульсов /5, инвертора (схемы «НЕ) 16, генератора единичных импульсов 17.

Рабочие триггеры 9 подобно, и рабочие сдвоенные ключи 3, ставятся в соответствие отдельным дугам графа, за исключением дуг, заходящих в начало путей ,и исходящих из ко«ца путей. Выход каждого рабочего триггера присоединен IK щапи управления рабочего сдвоенного ключа, соответствующего той же дуге, что и сдвоенный ключ. Нулевые триггеры 10 ставятся в соответствие отдельным вершинам графа, за исключением вершин, Я)Вляющихся началом « .концом -путей ( и X. f . Нулевые тр.иггеры 10 отличаются от рабочих только отсутствием соединения их выходов с ценям.и управления рабочих ключей. Триггеры, соответствующ1ие дугам, заходящим iB одну и ту же вершину, Вместе с нулевым триггером, соответствующим данной вершине, если она не является концОМ Путей, соединены по кольцевой схеме.

Первый |Из группы триггеров, образующих кольцевую схему, независимо от того, является он рабочим или нулевым, присоединяется к цеniH сброса таким образом, что при включении этой цепи он устанавливается IB рабочее состояние, характеризующееся готовностью триггера к опрокидыванию .при подаче первого счетного и.М|Пульса; остальные триггеры данной группы присоединены к цепи сброса таким образом, что П1ри ее включении переходят в нерабочее состояние. В рабочем состоянии рабочего триггера 9 с его выхода подается в цепь управления соответствующего рабочего сдвоенного ключа 3 сигнал на замьгкапие обеих пар контактов и на срабатывание индикатора состояния ключей. Входы для счетных импульсов триггеров Первой группы присоединяются к выходу схемы совпадения //, а последующей группы - к .выходу последнего триггера предыдущей группы. К выходу последнего триггера в последней группе триггеров присоединен вход для счетных импульсов триггера конца поиска 12, рабочий .выход которого присоединен к одному из входов схемы совпадения 11; сигналом сброса триггера конца поиска приводится в рабочее состояние. Второй вход схемы совпадения // через пару нормально замкнутых контактов пускового переключателя 13 присоединен к аыходу схемы совпадения 14, один из входов которой подключен к выходу генератора счетных импульсов 15, а второй - через инвертор 16 - к выходу схемы совпадения 5; через пару нормально разомкнутых контактов пускового переключателя 13 соответствующий вход схемы совпадения 11 присоединяется 1К выходу источника единИчных импульсов 17.

Соединение рабочих и нулевых триггеров 9 и 10 и триггера -конца поиска 12 (см. ф.иг. 3) соответствует решению задачи поиска путей графа (см. фиг. 1) с началом и концом путей Xj и Х. Выходы отдельных рабочих триггеров 9 обозначены бзквеппыми символами пар контактов рабочих сдвоенных ключей, управляемых :этими триггерами. Группы триггеров, соответствующих дугам, заходящим в отдельные 1вершины, расположены в отдельных строках И обозначены индекса1ми этих вершиц.

Работа устройства при автоматическом поиске путей происходит таким образом, что при включенной цеп.и сброса первые триггеры в каждой группе триггеров находятся в рабочем состоянии, а обе пары контактов рабочих ключей 3, управляемых этими триггерами, замкнуты. Если дуги .графа, соответствующие замк нутым ключам, образуют путь, то на выходе схемы совпадения 5 имеется сигнал, вследствие чего подача счетных импульсов от генератора счетных импульсов 15 блокируется схемой совпаде.вия 14, а состояние устройства после отключения цепи сброса остается неизменным. Если же эти дуги не образуют пути, то счетпые импульсы после отключения цепи сброса будут подаваться .на триггеры 9 и /6 до тех пор, пока не зам,кнется труппа ключей, соответствующих дугам трафа, образующим путь. После снятия информации по индикаторам включения ключей подается путем .переключения пускового переключателя 13 единичный счетный им.пульс, который производит последующую коммутацию триггеров 5 и /О и ключей 3. При возвращении переключателя 13 в исходное .положение состояние триггеров не изменяется, если набран путь, если пути нет, происходит дальнейшая коммутация счетными импульсами генератора счетных импульсов 15 до тех (пор, пока не будет вновь набран .путь. При возвращении системы триггеров 9 и IJ в «сходное положение, вследствие срабатывания тр.иггера конца поиска 12, подача счетных импульсов как от генератора счетных импульсов 5, так И от источника единичных .им.пульсов .17, прекращается ввиду отсутствия сигнала хотя бы на одном из входов схемы совпадения 11.

На фиг. 4-8 в .качестве примера приведена схема одного из воз1МОж.ных вариантов практического исполнения предлагаемого устройства.

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

Для соединения рабочих и нулевых триггеров в кольцевые схемы цредусмотрены снабженные штепсельными вилками вспомогательные ячейки: .коммутационные (см. фиг. 7) ц мостиковая (ОМ. фиг. 8). Это соединение осуществляется установкой пябочих, нулевых, коммутационных и мостиковых ячеек в соответствующие розетки раонределителя. Через щтепсельные разъемы рабочих и нулевых ячеек содержащиеся в них схемы присоединяются 1к источнику литания и цепям управления. Вся схема устройства вылолнена на полупроводниковых лриборах. В качестве ра.бочих сдвоенных ключей используются полупроводниковые триоды Г; и Гг, работающие в ключевом режиме и управляемые напряжением, снимаемым с коллектора триода Гз, .входящего имеете с триодом Т в схему рабочего триггера (см. фиг. 5). В качестве Индикатора еключенното состояния /ключей используется неоновая лампочка Л, питаемая через трансформатор Тр от генератора на полупроводниковом триоде Т, запускаемого тем же напряжением, что и рабочие сдвое.нные ключи. Схема нулевой ячейки собрана на триодах Гб и ГУ (см. фиг. 6) и является повторением триггерной схемы рабочей ячейки. Переключатель П1 в схемах этих ячеек устанавливается в нижнем положении, если соответствующая ячейка является .первой из рабочих и нулевых ячеек в данном ряду; в остальных случаях он занимает верхнее положение Переключатель П2 в схеме нулевой ячейки ставится в верхнем положении, если эта ячейка установлена в диагональной розетке последнего задействованного ряда распределителя. Благодаря этому, выход этого триггера соедиияется со входом триггера конца поиска 12, собранного на триодах Tg и Тд (см. фиг. 4). Вход этого триггера -через инвертор на триоде Гю присоединен к схеме совпадения 11. Такое включение обеспечивает независимость состояния триггера .конца поиска от потенциала шины распределителя ШСИ (шина счетных ИМпульсов), через которую счетные им1пульсы подаются в кольцевую схему, образованную первой группой рабочих и нулевых триггеров. Второй вход схемы // через пусковой переключатель 13 присоединен или к схеме 14, или к .генератору единичных импульсов 17 (источнику питания с последовательно включенным резистрром RI). При нажатии кнопки переключателя 13 через резистор У 1 заряжаются конденсаторы С входных дифференцирующих цепочек триггеров9 и/О первого ряда;,при отпускании кнопки эти конденсаторы разряжаются, так как схема /4 в это время имеет потенциал земли, благодаря чему и появляется единичный положительныи импульс, воздействующий на входы триггеров. Кнопочный КЛЮЧ К2 служит для присоединения |цепи сброса к (Источнику питания при подготовке устройства к автоматической работе. Схемы, выполняющие логическую операцию эквивалентности «НЕ - ИСКЛЮЧАЮЩЕЕ ИЛИ, сОбраны на транзисторах Гц-Г14. Ситт. е. на коллекторе транзистора TI, появляется только При наличии на обоих входах сигнала-потенциала земли, или отрицательного потенциала, т. е. при отсутствии сигнала. Схема совпадения 5 -образована транз-истора ми TIS с параллельно включенными переходами эмиттер - коллектор, работающими на общую нагрузку (Rz- Схема выдает сигнал (,в данном случае отрицательный потенциал) только при наличии сигнала, т. е. потенциала земля на всех ее входах. Схема «НЕ представляет собою обычный транзисторный инвертор. Присоединение балластных резисторов 6 и коммутационных «лючей 7 к щинам распределителя и источнику питания точно такое же, каК iB функциональной схеме устройства, приведенной на фиг. 2. Устройство позволяет при наличии п розеток в распределителе находить элементарные пути трафа с количеством вершин п,п. При этом используются только розетки, расположенные в первых п, рядах, При программировании задачи в первую очередь в диагональных розетках рядов, соответствующих вершинам графа, не являющихся началом и концом путей, устанавливаются нулевые ячейки, а в диатональную розетку ряда, соответствующего началу путей - мостиковая ячейка. Затем в розетках, соответствующих дугам графа, которые могут образовывать пути, устанавливаются рабочие ячейки. Остальные розетки первых п, рядов, за исключением соответствующего началу путей, заполняются коммутационными ячейками, Переключатель П всех первых ячеек в каждом отдельном ряду устанавливается в нижнем положении. Переключатель П2 нулевой ячейки, стоящей в диагональной розетке последнего занятого ряда, также устанавливается в нижнее положение. Замыкаются на землю комл1утационные ключи 7 рабочей вертикальной щины, соответствующей началу путей, и вспомогательной, соответствующей .концу -путей. Для начала работы нажимом кнопочного ключа /Сг схема устанавливается в исходное состояние. После отпускания кнопочного -ключа начинается автоматический поиск путей, При нахождении пути блокируется подача счетных импульсов, и поиск прерывается. Инфор.мация о совокупности дуг, Образующих путь, дается индикаторными лампочками рабочих ячеек. После записи этой информации нажимом и отпусканием кнопки К (подача единичного импульса) возобновляется автоматический поиск путей. При переборе всех «омбинаций срабатывает триггер конца поиска 12; нажатие кнопки Ki уже не вызывает переключения ячеек. Предмет изобретения Устройство для поиска элементарных путей направленного графа, содержащее коммутациские схемы «И и «НЕ, -источни-к питания, генератор счетных имиульсов, источник единичных имиульсОВ, пусковой -переключатель, соответствующее не заходящим в начало и не исходящим из 1конца Путей дугам графа управляемые ключи с индикаторами включения и управляющие этими ключами рабочие триггеры, соответст1вующие вершинам графа, не являющимся началом или 1концом лутей, и буфферные триггеры, причем управляющие триг-ю геры, соответствующие дугам графа, заходящим IB одиу вершину, и буфферный триггер, соответствующий этой же вершине, соединены в кольцевые .коммутаторы, -первый из которых ерисоединен к выходу первой логической схе-is мы «И, а последующие - с выходом .последнего триггера предыдущего коммутатора, содержащее также триггер конца поиска, вход которого лрисоединен к выходу последнего триггера в последнем кольцевом коммутаторе,20 а (ВЫХОД -к отдельному входу лервой логической схемы «И, распределитель, состоящий из соответствующих отдельным вершинам графа пар вертикальных шин, каждая из которых через |балластный резистор лрисоединена к не-25 заземленному, а через коммутационный ключ с нормально разомкнутыми контактами - к заземленному зажимам источника питания, и пар горизонтальных шин, причем рабочие ве.ртикальная и горизонтальная шины, соответст-зо вующие одной и той же вершине графа, соединены вместе и, отличающееся тем. что. с 5 целью исключения .повторного выбора путей оно дололнительно содержит соответствующие отдельным .верШИнам графа логические схемы «НЕ -ИСКЛЮЧАЮЩЕЕ ИЛИ, входы которых соединены с вертикальными шинами раснределителя, соответствующими этим Вершинам, а выходы-к отдельньш входам второй логической схемы «И, (выход которой через логическую схему «НЕ присоединен к одному входу третьей логической схемы «И, второй вход которой соединен с выходом генератора счетных импульсов, а выход - с неподвижным контактом пускового лереключателя, второй неподвижный контакт последнего присоедииен к выходу генератора единичных импульсов, а подвижной контакт- ко второму входу лервой логической схемы «И, рабочая вертикальная щина, соответствующая началу лутей, и вспомогательная (вертикальная шина, соответствующая (концу лутей, через соответствующие ком(мутац ионные ключи с замкиутыми контактами лрисоединены к заземленному зажиму источника питания; управляемые ключ,и, соответствующие отдельным дугам графа, содержат две лары контактов, соединяющих пару -вертикальных шин, соответствующих вершине графа, из которой выходит данная дуга, с парой горизонтальных шин, соответствующих вершине графа, в которую эта дуга (входит; вторые горизонтальные шины распределителя присоединены к заземленному зажиму источника питания.