УСТРОЙСТВО ДЛЯ ОПРЕДЕЛЕНИЯ ПЕРЕДАЧИ ГРАФА Советский патент 1970 года по МПК G06G7/48 

Йредлагаемое устройство относится к области вычислительной техники.

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

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

или с :номером строки, или с номером столбца рассматриваемой ячейки перебора.

Такое выполнение устройства позволяет упростить процесс определения передачи графа.

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

р JL

л А.

д

где Р -передача к-го пути от источника к

стоку, Д-определитель графа,

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

схема блока поиска путей; на фиг. 3 - схема блока поиска членов определителей; )ia фиг. 4 - схема блока определения четности подстановок, Образованных индексами членов определителей; на фиг. 5-7 - принципиальные схемы элементов устройства.

Устройство состоит из блока 1 поиска лутей, блока 2 раскрытия определителей, генератора 3 тактовых импульсов, управляющего триггера 4, триггера 5 конца поиска с индикатором его СОСТОЯНИЯ, сдвоенной пусковой кнопки 6, сдвоенного переключателя 7 рода работ, управляемого переключателя 8 тактовых импульсов и логического элемента «ИЛИ 9 (см. фиг. 1).

Блок / поиска путей (см. фиг. 2,а) состоит из матрицы л2 коммутирующих ячеек 10 (-где п - наибольший порядок графа), столбца п буферных триггеров 11, подчинепных строкам матрицы коммутирующих ячеек, входных сдвоенных ключей Ш задания начальной верщины (источника), путей, подчиненных строкам матрицы коммутирующих ячеек, п выходных сдвоенных ключей 13 задания конечной вершийы (стоки) путей, подчиненных столбцам матрицы колшутирующих ячеек. Каждая ком.мутирующая ячейка (см. фиг. 2,6) содержит триггер 14 с четырьмя выходами - двумя статическими, противоположными по снимаемому сигналу («О или «1, и двумя ди 1амическими, управляемый переключатель J5 сигналов, программирующие сдвоенные переключатели 16, логические элементы «И 17 и 18 и усилитель 19 «нулевого сигнала.

Блок 2 раскрыт:ия определителей состоит из блока поиска членов определителей (см. фиг. 3) и блока определений четности подстановок, образованных индексами членов определителей (см. фиг. 4).

Блок поиска членов определите; ей (фиг. 3,а) состоит из .матрицы п- ячеек перебора 20, селектора 21, п элементов «И 22 и п элементов «ИЛИ-НЕ 23, подчиненных строкам матрицы ячеек перебора, генератора 24 одиночных импульсов со сдвоенной кнопкой 25 продолжения поиска, управляемого переключателя 26 сигналов, индикатора 27 снятия результатов («запись), логического элемента «ИЛИ 28 и триггера 29 задания начального состояния матрице ячеек перебора. Каждая ячейка перебора 20 содержит триггер 30 с индикатором состояния и управляемый переключатель 31 сигналов (см. фиг. 3,6).

Селектор 21 содержит п логических элементов «ИЛИ-НЕ 32, каждый на п входов, подчиненных столбцам матрицы ячеек перебора, п логических элементов «ИЛИ 33, каждый на (n-f 1) вход, также подчиненных столбцам матрицы ячеек nepei6opa, и логический элемент «И 34 на (га+1) вход.

Блок определения четности (см. фиг. 4) содержит матрицу диодов 35, строки и столбцы которой подчинены одинаковым строкам и столбцам матрицы ячеек перебора, логические элементы «И 36 подачи на матрицу диодов опращивающих импульсов и подчиненных ячейкам перебора, находящимся в одинаковых с ними строках и столбцах, логические элементы «И 37 снятия с матрицы диодов опращивающих импульсов и аналогично подчиненных ячейкам перебора, (п-1) триггер 38 создания разделения во времени опрашивающих импульсов, каждый из которых починен одной, кроме пер1вой, строке матрицы

ячеек перебора, триггер 39 задержки, служащий для создания в импульсной последовательности задержки на один импульс, необходимой для задания ;конечпому триггеру четности нерабочего состояния, л-1 триггер 40

определения четности числа инверсий отдельных индексов элементов определителей, каждый из которых подчинен одной, кроме последней, строке матрицы ячеек перебора, (п-I) триггер 41 опроса состояния триггеров

четности, каждый из «оторых подчинен аналогично предыдущим триггерам строкам матрицы ячеек перебора, и конечный триггер 12 четности с индикаторами знака «плюс и «минус.

Генератор 3 тактовых импульсов через один ключ пусковой кнопки 6 соединен с сигнальным входом управляемого переключателя 8, два управляющих входа которого соединены со статическими выходами управляющего

триггера 4. Одии выход переключателя 8 соединен с клеммой Я/ блока /. Второй выход переключателя 8 соединен через клемму П2 блока 2 с сигнальным входом управляемого переключателя 26. Источник «нулевого сигнала («О), т. е. сигнала, устанавливающего триггеры устройства в нерабочее («нулевое) состояние, соединен через второй ключ пусковой кнопки 6 с клеммой ПЗ блока 1 и через элемент 9-с клеммой П4 блока 2, а также

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

А со входом установления рабочего состояния этого же триггера

Один вход логического элемента «И 17 каждой .коммутирующей ячейки соединен с тем статическим выходом триггера 14 этой

ячейки, на котором имеется единичный сигнал в рабочем состоянии триггера. Второй вход элемента «И 17 соединен через горизонтальную щину и входной сдвоенный ключ 12 одной строки с одним выходом управляемого

переключателя 8 (через «ле.мму 171).

К этой же горизонтальной щине подключены аналогичные входы элементов «И 17 всех коммутирующих ячеек строки, а также вход установления рабочего состояния буферного

триггера 11 одной строки.

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

столбца рассматриваемых коммутирующих ячеек. .Входы установления нерабочего состояния триггеров 14 всех коммутирующих ячеек и буферных тритгеров 11 соединены с клеммой ПЗ. Управляющий вход переключателя 15 соеди-нен с выходом одного из сдвоенных переключателей 16. Один вход этого переключателя соединен через вертикальную шину, к которой также подключены аналогичные входы переключателей остальных ячеек одного столбца со статическим выходом буферного триггера, подчиненного строке, номер которой совпадает с номером столбца рассматриваемой ячейки. Второй вход переключателя соединен с источником «нулевого сигнала («О). Выход второго из сдвоенных переключателей 16 соединен с управляющим входом переключателя 31 той ячейки перебора 20, которая находится в строке и столбце, номера которых совпадают соответствен-но с номерами строки и столбца рассматриваемой коммутирующей ячейки. Один вход второго переключателя 16 соединен с выходом элемента «И 18, второй вход - с источником «нулевого сигнала. Один вход элемента «И 18 соединен с одним выходом усилителя 19 «нулевого сигнала и через вертикальную шину - с аналогичными выходами усилителей 19 всех коммутирующих ячеек одного столбца, а также через горизонтальную шину, соединенную с этой вертпикальной шиной - со вторыми выходами усилителей 19 всех коммутирующих ячеек, находящихся в строке, номер которой совпадает с .номером столбца рассматриваемой ячейки. Второй .вход элемента «И 18 соединен со вторым выходом усилителя 19, вход которого соединен со статическим выходом триггера 14, имеющим «нулевой сигнал в рабочем состоянии триггера. Выход переключателя 15 сигналов, на котором имеется «единичный сигнал при наличии таких же сигналов на его сигнальном и управляющем входах, соединен со входом установления рабочего состояния триггера 14, другой выход- с тем динамическим выходом триггера 14, с которого снимается «единичный сигнал при переходе триггера с рабочего состояния в нерабочее, и сигнальным входом переключателя -15 сигналов следующей в строке ком мутирующей ячейки. Если же коммутирующая ячейка последняя в строке, то рассматриваемый выход соединен со входами установления нерабочего состояния триггеров (14, принадлежащих коммутирующим ячейкам столбца, номер которого совпадает с номером строки рассматриваемой ячейки, а также со входом установления нерабочего состояния буферного триггера одной строки и через второй ключ входных сдвоенных ключей 12 одной строки, клемму П5, переключатель 7 рода работ в положении 2РдА - со входо.м установления рабочего состояния триггера 5. Второй динамический (ВЫХОД триггера 14 соединен через вертикальную щину, к которой подключены аналогичные выходы триггеров всех коммутирующих ячеек одного столбца, через один из сдвоенных выходных ключей 13 одного столбца и клемму П6 со вторым входом логического элемента «ИЛИ 9 и входом установления

рабочего состояния управляющего триггера 4. Динамический выход каждого буферного триггера 11 соединен с сигнальным входом управляемого переключателя 15 .первой в одной строке коммутирующей ячейки.

|Входы установления нерабочего состояния триггеров 30 всех ячеек перебора 20, а также триггера 29 задания начального состояния соединены с клеммой П4 блока 2 (см. фиг. 3). Вход установления рабочего состояния триггера 29 соединен с клеммой П2 блока 2. Динамический выход триггера 29 соединен через разделительные диоды с сигнальными входами управляемых переключателей 31 каждой первой в строке ячейки перебора. Выход переключателя 31, на котором имеется «единичный сигнал при наличии таких же сигналов на его сигнальном и управляющем входах, соединен со входом установления рабочего состояния триггера 30, второй выход - с динамическим выходам триггера 30 и .сигнальным входом переключателя 31 следующей в строке ячейки перебора. Если же ячейка перебора 20 .последняя в строке, то рассматриваемый выход соединен с сигнальным входом

.переключателя 31 первой в одной с ней строке ячейки перебора, а также со входами установления нерабочего состояния триггера 30 всех находящихся в следующей строке ячеек перебора и с одним входом элемента «И 22,

подчиненного следующей строке. Если же ячейка перебора последняя в последней строке, то рассматриваемый выход соединен через клемму П7 блока 2 и переключатель 7 рода работ (см. фиг. 1) в положении А - со входом установления рабочего состояния триггера 5 конца поиска, а также через клемму П8 блока / и замкнутый при программировании выходной ключ 13 - со входами установления нерабочего состояния триггеров 14 всех

коммутирующих ячеек, находящихся в одном столбце с указанным ключом 13. Выход Л всех ячеек перебора одного столбца подключены ко входам элемента «ИЛИ- НЕ 32 этого же столбца. Выход К каждой ячейки перебора связан непосредственно с управляющим входом переключателя 31 .этой ячейки. Выход элемента «ИЛИ-НЕ 32 соединен с одним из входов элемента «ИЛИ 33 одного столбца. К остальным входам элемента «ИЛИ 33

подключены выходы Г всех ячеек перебора одного с ним столбца. Выход Т каждой ячейки перебора связан со статическим выходом триггера 30 этой ячейки, на котором имеется «единичный сигнал в рабочем состоянии

триггера. Выходы элементов «ИЛИ 33 всех столбцов соединены со входами элемента «И 34. Кроме этого, один из входов элемента «И 34 соединен через клемму П9 блока 2 с тем статическим выходом триггера 4, на котором

тоянин триггера. Выход элемента «И 34 соединен с индикатором 27 снятия результатов, а также с управляющим входом переключателя 26. Выход переключателя 26, на котором имеется «единичный сигнал при наличии такого же снгнала на сигнальном входе и «нулевого сигнала на унравляюидем входе, соединен с выходом генератора 24, а также со входами установления нерабочего состояния триггеров 30 всех ячеек .перебора 20 первой строки и одним из входов элемента «И 22, подчиненного первой строке. Второй вход каждого элемеита «И 22 соединен с выходом эле.мента «ИЛИ-НЕ 23 одной строки. Входы последнего элемеита соединены с выходами К ячеек перебора одной с ним строки. Выход элемента «И 22 соединен совместно с выходом последней в следующей строке ячейки перебора с одним из входов элемента «И 22, принадлежащего следующей строке. Выход элемента «PI 22 последней строки соединен с клеммой Я7 блока 2.

Один вход элемента «ИЛР1 28 соединен через кнопку 25 в нажатом состоянии е источником «нулевого сигнала. Второй вход - с клеммой П4 блока 2. Выход элемента «ИЛИ 28 через разъем Ч соединен со входом установления рабочего состояния .первого из триггеров 38 и нерабочего состояния остальных триггеров 38, а также триггеров 39-41 (см. фиг. 4). Выход переключателя 26, на котором .имеется «единичный сигнал при наличии таких же сигналов па сигнальном и унра.вляющем входах, соединен через разъем 42 со входами установления нерабочего состояния триггеров 38-41. Триггеры 38, 39 и 41 соединены последовательно, образуя схему, создающую последовательность сдвинутых во времени имиульсов. Динамический выход каждого триггера 38 соединен с одним из входов всех элементов «И 36, подчиненных ячейкам перебора 20 одной строки. Динамический выход триггера 39 соединен со входом уста)1овления нерабочего состояния триггера 42. Динамический выход каждого триггера 41 соединен со входом установления нерабочего состояния подчиненного одной строке триггера 40. Динамические выходы всех триггеров 40 соединены с сим-метричным входом триггера 42. Второй вход каждого элемента «И 36 соединен с выходом Т той ячейки перебора 20, которой иодчинеи рассматриваемый элемент. С этим же выходом ячейки перебора соединен один из входов соответствуюн|его элемента «И 37. Выход каждого элемента «И 36 и второй вход каждого элемента «И 37 подсоединены к матрице диодов 35. Выходы всех элементов «PI 37 одной строки соединены с симметричным входом триггера 40, подчиненного этой же строке.

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

Перед началом работы необходимо запрограммировать на устройстве задачу. Для этого программирующие переключатели /& всех ком.мутирующих ячеек, соответствующих наличным дугам графа, .переводят в положения «Включено. Отмети.м, что дуге ij графа, исходящей из f-ой верщины и заходящей в /-ую вершину, подчинена коммутирующая ячейка, нахо.дящаяся в f-ой строке и j-o-u . Далее необходимо включить тот сдвоенный ключ 12, который подчинен строке, с номером, равным номеру вершины, соответствующей началу пути т. е. источника, а также тот сдвоенный ключ

13, который подчинен столбцу с номером, равным номеру верщины, соответствующей концу пут1И, т. е. стока. Иосле этого переключатель 7 рода работ ставят в положение 1.Р А и нажимают пусковую кнопку 6. При нажатии

этой кнопки на все триггеры устройства от источника «нулевого сигнала поступает сигнал, устанавливающий их в нерабочее состояние. После отпуска кнопки 6 через переключатель 5 импульсы с генератора 3 поступают на

клемму Я/ блока / поиска путей. После определения первого пути PI от источника к стоку графа на клемме П6 блока / появляется сигнал, который переводит управляющий триггер 4 в рабочее состояние. В результате этого изменяются сигналы на управляющих входах переключателя 8, и подача импульсов на блок 1 прекращается. Импульсы начинают посту.пать на клем-му П2 блока 2.

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

матрицу ячеек перебора 20. После определения первого члена определителя AI, о чем будет свидетельствовать появление «единичного сигнала на выходе элемента «И 34 селектора 21, загорается индикатор 27.

Далее импульсы будут поступать через переключатель 26 к блоку определения четности, где определяется знак, с каким входит найденное слагаемое выражение раскрытого определителя Aj. Результат записывают по

загоревшимся индикаторам коммутирующих ячеек блока 1 (выражение пути Р) и ячеек перебора блока 2 (выражение первого члена определителя Aj) с учетом знака, определяемого по индикатору. После записи нажимают

кнопку 25, и поиск членов определителя AI продолжается. После нахождения всех членов этого определителя на клемме Я7 блока 2 поя.вляется сигнал, который поступает на Kvie.MAiy блока / для подготовки этого блока к дальнейшему поиску путей и на триггер 4, в результате этого триггер 4 .переводится опять в нерабочее состояние. Подача импульсов на блок 2 прекращается, и они начинают поступать на блок / до мо.мента нахождения

второго пут1И - РЗ и т. д.

После определения всех слагаемых числителя, т. е. величины 2f,;Aj, на клемме nf блока / появляется сигнал, который через переключатель 7 поступает на триггер 5 конца

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

После этого Переключатель 7 переводят в положение Л. При «ажатии кнопки 6 на триггер 4 через переключатель 7 поступает сигнал, который устанавливает этот триггер в рабочее состояние. После отпуска кнопки 6 импульсы с генератора 3 будут поступать через переключатель 5 на клемму П2 -блока 2. При этом определитель полного графа раскрывается, поскольку триггер 14 всех коммутирующих ячеек блока 1 будет находиться в нерабочем состоянии, и тем самым блоком 1 не будут блокироваться ячейки блока 2. После полного раскрытия определителя А на клемме П7 блока 2 появляется сигнал, который через переключатель 7 поступает к триггеру 5 конца поиска и опрокидывает его (сигнальная лампочка конца поиска загорается).

Предмет и з о б ip е т е ;Н и я

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

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

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

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

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

fui 1

П6 Пв

р,.г г

U2

35

38

36 -П2

т1А-Уг

,

/т./

Т I(

т I//7 1

7 22

т п

,

//7-у/7

71 /7Л-//

4/

2