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

О Й И-СИЗОБРЕТЕН ИЯ 259495 Союз Советских Социалистических РеспубликК АВТОРСКОМУ СВИДЕТЕЛЬСТВУ Зависимое от авт, свидетельстваЗаявлено 27.И.1968 ( 1253037(18-24)с присоединением заявкиПриоритет птф, 7/48 6 д Комитет по дел изобретении н отнрытипрн Совете МинистровСССР К 681.33.001,5 (088.8) убликовано 12,Х 11.1969. Бюллетень2за 1970та опубликования описания ЗХ 1,1970 Авторыизобретени, П, Базилевич и Е. Ф. Замо Заявит УСТРОЙСТВО ДЛЯ О ЕЛЕ ЕРЕ АЧИ ГРАФА ваемой ячейки перебора, и через лэлемент И соединен со статическдами триггеров всех коммутирующномера строк и столбцов которыхили с.номером строки, или с номерарассматриваемой ячейки перебора,Такое выполнение устройстваупростить процесс определения передфа.Устройство представляет собой спрованную математическую машинуматического нахождения передачисимволическом виде. Под передачейпонимают выражениеЬ огическии ими выхоих ячеек, сав,падают м столбца озволяе ачи тра ециализидля автографа в Т графа где Р, - пере сто 0 Л - опр Ь - алг-го пуафа, не касаНеобходимо кает при анал электрических которые опис возни- ейных истем, ненияНа фиг. 1 представлена функциональнаяО схема описываемого устройства; на фиг, 2 -Предлагаемое устройство относится к области вычислительной техники.Известно устройство для определения передачи трафа, содержащее генератор тактовых импульсов, триггеры, логические элементы И, переключатели и кнопку пуска.Предлагаемое устройство отличается от известного тем, что содержит блок,поиска путей, выполненный в виде матрицы коммутирующих ячеек, содержащих переключатели и триггеры, а также блок раскрытия определителей, выполненный в виде матрицы ячеек перебора. Выход генератора тактовых импульсов через кнопку пуска и,переключатель тактовых импульсов соединен со входами подачи тактовых импульсов блоков поиска путей и раскрытия определителей, управляющие входы переключателей тактовых имлульсов соединены с выходами триггера, один вход которого соединен с выходом блока поиска путей, а второй - с выходом блока раскрытия определителей. Выходы блоков поиска путей и раскрытия определителей соединены также через пере,ключатель рода работ со входами триггера конца поиска, Управляющий вход переключателя сигналов каждой ячейки перебора блока ,раскрытия определителей через переключатель коммутирующей ячейки блока паиска путей, номер строки и столбца которой совпадает с номером строки и столбца рассматриделитель гр афа,браическое дополнение кт. е. определитель подгрющегося к-го пути).сть нахожденмя графовизе методами графов лицепей, а также другихываются линейными урасхема олока поиска путей; на фиг. 3 - схема блока поиска членов определителей; на фиг. 4 - схема блока определения четности подстановок, образованных индексами членов определителей; на фиг. 5 - 7 - принципиальные схемы элементов устройства.Устройство состоит из блока 1 поиска путей, блока 2 раскрытия определителей, генератора 3 тактовы импульсов, управляющего триггера 4, триггера 5 конца поиска с индикатором его состояния, сдвоенной пусковой кнопки б, сдвоенного переключателя 7 рода работ, управляемого переключателя 8 тактовых импульсов и логического элемента ИЛИ 9 (см. фиг, 1).Блок 1 поиска путей (см. фиг. 2,а) состоит из матрицы и 2 коммутирующих ячеек 10 (где и - наибольший порядок графа), столбца и буферны триггеров 11, подчиненных строкам матрицы коммутирующих ячеек, входных сдвоенных ключей 12 задания начальной вершины (источника), путей, подчиненных строкам матрицы коммутирующих ячеек, и выходных сдвоенных ключей 13 задания конечной вершины (стоки) путей, подчиненных столбцам матрицы коммутирующих ячеек. Каждая коммутирующая ячейка (см. фиг. 2, б) содер. жант триггер 14 с четырьмя выходами - двумя статическими, противоположными по сни. маемому сигналу (О или 1, и двумя динамическими, управляемый переключатель 15 сигналов, программирующие сдвоенные переключатели 16, логические элементы И 17 и 18 и усилитель 19 нулевого сигнала.Блок 2 раскрытия определителей состоит из блока поиска членов определителей (см. фиг. 3) и блока определений четности подстановок, образованных индексами членов определителей (см. фиг. 4) .Блок, поиска членов определителей (фиг. З,а) состоит из матрицы и- ячеек перебора 20, селектора 21, и элементов И 22 и и элементов ИЛИ - НЕ 23, подчиненных строкам матрицы ячеек перебора, генератора 24 одиночных импульсов со сдвоенной кнопкой 25 продолжения поиска, управляемого переключателя 2 б сигналов, индикатора 27 снятия результатов (запись), логического элемента ИЛИ 28 и триггера 29 задания начального состояния и атрице ячеек перебор а. Каждая ячейка перебора 20 содержит триггер 30 с индикатором состояния и управляемый переключатель 31 сигналов (см. ф 1 иг, 3, б) .Селектор 21 содержит и логических элементов ИЛИ - НЕ 32, каждый на и входов, подчиненных столбцам матрицы ячеек перебора, и логических элементов ИЛИ 33, каждый на (и+1) вход, также подчиненных столбцам матрицы ячеек перебора, и логический элемент И 34 на (и+1) вход.Блок определения четноспи (см. фиг. 4) содержит матрицу диодов 35, строки и столбцы которой подчинены одинаковым строкам и столбцам матрицы ячеек перебора, логические элементы И 36 подачи на матрицу дио 5 10 15 20 25 ЗО 35 40 45 50 55 60 65 дов опрашивающих импульсов и подчиненных ячейкам перебора, находящимся в одинаковых с ними строках и столбцах, логические элементы И 37 снятия с матрицы диодов опрашивающих импульсов и аналогично подчиненных ячейкам перебора, (и - 1) триггер 38 создания разделения во времени опрашивающих импульсов, каждый из которых, починен одной, кроме первой, строке матрицы ячеек перебора, триггер 39 задержки, служащий для создания в импульсной последовательности задержки на один импульс, необходимой для задания конечному триггеру четности нерабочего состояния, и - 1 триггер 40 определения четности числа инверсий отдельных индексов элементов определителей, каждый из которых подчинен одной, кроме последней, строке матрицы ячеек перебора, (и - 1) триггер 41 опроса состояния триггеров четности, каждый из которых подчинен аналогично предыдущим триггерам строкам матрицы ячеек перебора, и конечный триггер 12 четности с индикаторами знака плюс и минус.Генератор 3 тактовых импульсов через один ключ пусковой кнопки 6 соединен с оигнальным входом управляемого переключателя 8, два управляющих входа которого соединены со статическими выходами упр авляющего триггера 4. Один выход, переключателя 8 соединен с клеммой П 1 блока 1, Второй выход переключателя 8 соединен через клемму П 2 блока 2 с оигнальным входом управляемого переключателя 26. Источник нулевого сигнала (О), т. е. сигнала, устанавливающего триггеры устройства в нерабочее (нулевое) состояние, соединен через второй ключ пусковой кнопочки б с клеммой ПЗ блока 1 и через элемент 9 - с клеммой П 4 блока 2, а также со входом установления нерабочего состояния триггера 5 конца поиска и через переключатель 7 рода работ в положении ХРЬ - со входом установления нерабочего состояния управляющего триггера 4 или в,положении Л - со входом установления рабочего состояния этого же триггераОдин вход логического элемента И 17 каждой коммутирующей ячейки соединен с тем статическим выходом триггера 14 этой ячейки, на котором имеется единичный сигнал в рабочем состоянии триггера, Второй вход элемента И 17 соединен через горизонтальную шину и входной сдвоенный ключ 12 одной строки с одним выходом управляемого переключателя 8 (через клемму П 1).К этой же горизонтальной шине подключены аналогичные входы элементов И 17 всех коммутирующих ячеек строки, а также вход установления рабочего состояния буферного триггера 11 одной строки.Выходы элементов И 17 всех коммутирующих ячеек одного столбца подключены к одной вертикальной шине, которая соединена с указанной выше горизонтальной шиной той строки, номер которой совпадает с номеромстолбца рассматриваемых коммутирующих ячеек. Входы установления нерабочего состояния трипгеров 14 всех коммутирующих ячеек и буферных триггеров 11 соединены с клеммой ПЗ. Управляющий вход переключателя 15 соединен с выходом одного из сдвоенных переключателей 1 б. Один вход этого переключателя соединен через вертикальную шину, к которой также подключены аналогичные входы переключателей остальных ячеек одного столбца со статическим выходом буферного триггера, подчиненного строке, номер которой совпадает с номером столбца рассматриваемой ячейки. Второй вход переключателя соединен с источником нулевого сигнала (0). Выход второго из сдвоенных переключателей 1 б соединен с управляющим входом переключателя 31 той ячейки перебора 20, которая находится в строке и столбце, номера которых совпадают соответственно с номерами строки и столбца рассматриваемой коммутирующей ячейки. Один вход второго переключателя 1 б соединен с выходом элемента И 18, второй вход - с источником нулевого сигнала. Один вход элемента И 18 соединен с одним выходом усилителя 19 нулевого сигнала и через вертикальную шину - с аналогичными выходами усилителей 19 всех коммутирующих ячеек одного столбца, а также через горизонтальную штину, соединенную с этой вертикальной,шиной - со вторыми выходами усилителей 19 всех коммутирующих ячеек, находящихся в строке, номер которой совпадает с номером столбца рассматриваемой ячейки. Второй, вход элемента И 18 соединен со вторым выходом усилителя 19, вход которого соединен со статическим выходом триггера 14, имеющим нулевой сигнал в рабочем состояниями триггера. Выход переключателя 15 сигналов, на котором имеется единичный сигнал при наличии таких же сигналов на его сигнальном и управляющем входах, соединен со входом установления рабочвго состояния триггера 14, другой выход - с тем динамическим выходом триггера 14, с которого снимается единичный сигнал при переходе триггера с рабочего состояния в нерабочее, и сигнальным входом переключателя -15 сигналов следующей встроке коммутирующей ячейки. Если же коммутирующая ячейка последняя в строке, то рассматриваемый выход соединен со входами установления нерабочего состояния трипгеров 14, принадлежащих коммутирующим ячейкам столбца, номер которого совпадает с номером строки рассматриваемой ячейки, а также со входом установления нерабочего состояния буферного триггера одной строки и через второй ключ входных сдвоенных ключей 12 одной строки, клемму П 5, переключатель 7 рода работ в положении Р К - со входом установления рабочего состояния триггера 5. Второй динамический выход триггера 14 саединеи через вертикальную шину, к которой подключены аналогичные выходы триггеров всех коммути 5 10 15 20 25 30 35 40 45 50 55 60 65 рующих ячеек одного столбца, через один из сдвоенных выходных ключей 13 одного столбца и клемму Пб со вторым входом логического элемента ИЛИ 9 и входом установления рабочего состояния управляющего триггера 4. Динамический выход каждого оуферного триггера 11 соединен с сигнальным входом управляемого переключателя 15 первой в одной строке коммутирующей ячейки,Входы установления нерабочего состояния триггеров 30 всех ячеек перебора 20, а также триггера 29 задания начального состояния соединены с клеммой П 4 блока 2 (см. фиг. 3). Вход установления рабочего состояния тригге,ра 29 соединен с клеммой П 2 блока 2. Динамический выход триггера 29 соединен через разделительные диоды с сигнальными входами управляемых переключателей Л каждой первой в строке ячейки перебора, Выход переключателя Л, на котором имеется единичный сигнал при наличии таких же оигналов на его сигнальном и управляющем входах, соединен со входом установления рабочего состояния триггера 30, второй выход - с динамическим выходом триггера 30 и сигнальным входом переключателя 31 следующей в строке ячейками первбора. Если же ячейка перебора 20,последняя в строке, то рассматриваемый выход соединен с сигнальным входом ,переключателя 31 первой в одной с ней строке ячейки перебора, а также со входами установления нерабочего состояния триггера 30 всех находящихся в следующей строке ячеек перебора и с одним входом элемента И 22, подчиненного следующей строке. Если же ячейка перебора последняя в последней строке, то рассматриваемый выход соединен через клемму П 7 блока 2 и переключатель 7 рода работ (см. фиг, 1) в положении Ь - со входом установления рабочего состояния триггера 5 конца поиска, а также через клемму П 8 блока 1 и замкнутый при программировании выходной ключ И - со входами установления нерабочего состояния триггеров 14 всех коммутирующих ячеек, находящихся в одном столбце с указанным ключом И. Выход К всех ячеек перебора одного столбца подключены ко входам элемента ИЛИ - НЕ 32 этого же столбца. Выход К каждой ячейки перебора связан непосредственно с управляющим входом переключателя 31,этой ячейки. Выход элемента ИЛИ - НЕ 32 соединен с одним из входов элемента ИЛИ 33 одного столбца. К остальным входам элемента ИЛИ 33 подключены выходы Т всех ячеек перебора одного с ним столбца. Выход Т каждой ячейки:перебора связан со статическим выходом триггера 30 этой ячейки, на котором имеется единичный сигнал в рабочем состоянии трипгера. Выходы элементов ИЛИ 33 всех столбцов соеданены со входами элемента И 34, Кроме этого, один из входов элемента И 34 соединен через клемму П 9 блока 2 с тем статическим выходом триггера 4, на котором имеется единичный сигнал в рабочем соС 259495тоянии триггера. Выход элемента И 34 соединен с индикатором 27 снятия результатов, а также с управляющим входом переключателя 26, Выход переключателя 26, на котором :имеется единичный сигнал при наличии такого же сигнала на сигнальном входе и нулевого сигнала на управляющем входе, соединен с выходом генератора 24, а также со входами установления нерабочего состояния триггеров 30 всех ячеек переоора 20 первой строки и одним из входов элемента И 22, подчиненного первой строке. Второй вход каждого элемента И 22 соединен с выходом элемента ИЛИ - -. 23 одной строки. Входы последнего элемента соединены с выходами К ячеек перебора одной с вим строки. Выход элемента И 22 соединен совместно с выходом последней в следующей строке ячейки перебора с одним из входов элемента И 22, принадлежащего следующей строке. Выод элемента И 22 последней строки соединен с клеммой П 7 блока 2.Одип вход элемента ИЛИ 28 соединен через кнопку 25 в нажатом состоянии с источником нулевого сигнала. Второй вход - с клеммой П 4 блока 2. Выход элемента ИЛИ 28 через разъем Ч 1 соединен со входом установления рабочего состояния, первого из триггеров 38 и нерабочего состояния остальных триггеров 38, а также триггеров Ж - 41 (см. фиг. 4). Выход переключателя 26, на котором имеется единичный сигнал при наличии таких же сигналов на сигнальном и управляющем входах, соединен через р аз ьем Ч 2 со входами установления нерабо его состояния триггеров 38 - 41. Триггеры 38, 39 и 41 соединены последовательно, образуя схему, создающую последовательность сдвинутых во времени импульсов. Динами еский выход каждого триггера 38 соединен с одним из входов всех элементов И 36, подчиненных ячейкам переоора 20 одной строки, Динамический выход триггера 39 соединен со входом установления нерабочего состояния триггера 42, Динамический выход каждого триггера 41 соединен со водом установления нерабочего состояния подчиненного одной строке триггера 40. Динамические выходы всех триггеров 40 соединены с симметричным входом триггера 42. Второй вход каждого элемента И 36 соединен с выходом Т той ячейки перебора 20, которой подчинен рассматриваемый элемент, С этим же выходом ячейки перебора соединен один из входов соответствующего элемента И 37, Выход каждого элемента36 и второй вход каждого элемента И 37 подсоединены к матрице диодов 35. Выходы всех элементов И 37 одной строки соединены с симметричным входом триггера 40, подчиненного этой же строке.Устройство работает следующим образом.Перед началом работы необходимо запрограммировать на устройстве задачу. Для это- го программирующие переключатели 16 всех коммутирующих ячеек, соответствующих на 5 10 15 20 25 30 35 40 45 50 55 60 65 личным дугам графа, переводят в положения Включено. Отметим, что дуге ц графа, исходящей из К-ой вершины и заходящей в 1-ую вершину, подчинена коммутирующая ячейка, находящаяся в с-ой строке и 1-ом столбце, Далее необходимо включить тот сдвоенный ключ 12, который подчинен строке, с номером, равным,номеру вершинины, соответствующей началу пути т. е, источника, а также тот сдвоенный ключ 13, который подчинен столбцу с номером, равным номеру вершины, соответствующей концу пуэи, т. е. стока. После этого переключатель 7 рода работ ставят в положение ,ЕР, Л и нажимают пусковую кнопку б. При нажатии этой кнопки на все триггеры устройства от источника нулевого сигнала поступает сигнал, устанавливающий их в нерабочее состояние. После отпуска кнопки б через переключатель 8 импульсы с генератора 3 поступают на клемму П 1 блока 1 поиска путей. После определения первого пути Р, от источника к стоку графа на клемме Пб блока 1 появляется сигнал, который переводит управляющий триггер 4 в рабочее состояние. В результате этого изменяются сигналы на управляющих входах переключателя 8, и подача импульсов на блок 1 прекращается, Импульсы начинают посту,пать на клемму П 2 блока 2.При этом определитель Л подграфа раскрывается, образованный из запрограммированного на устройстве графа исключением вершин, входящих в найденный путь Р, и ин. цидентных им дуг. Сначала импульсы через переключатель 26 блока 2 будут поступать на матрицу ячеек перебора 20. После определения первого члена определителя Ло чем будет свидетельствовать появление единичного сигнала на выходе элемента И 34 селектора 21, загорается индикатор 27.Далее импульсы будут поступать через переключатель 26 к блоку определения четности, где определяется знак, с каким входит найденное слагаемое выражение раскрытого определителя Л,. Результат записывают по загоревшимся индикаторам коммутирующих ячеек блока 1 (выражение пути Р,) и ячеек перебора блока 2 (выражение первого члена определителя Л 1) с учетом знака, определяе. мого по индикатору. После записи нажимают кнопку 25, и поиск членов определителя Л продолжается. После нахождения всех членов этого определителя на клемме П 7 блока 2 появляется сигнал, который поступает на клемму П 8 блока 1 для подготовки этого блока к дальнейшему поиску путей и на триггер 4, в результате этого триггер 4 переводится опять в нерабочее состояние. Подача импульсов на блок 2 прекращается, и они начинают поступать на блок 1 до момента нахождения Второго пут 3 и - Р 2 и т. д.После определения всех слагаемых числителя, т, е. величины ХРЛ, на клемме П блока 1 появляется сигнал, который через переключатель 7 поступает на триггер 5 конца поиска и переводит его в рабочее состояние, 259495При этом загорается индикатор его состояния, что будет свидетельствовать о полном раскрытии выражения числителя передачи графа.После этого переключатель 7 переводят в положение Л. При нажатии кнопки б на триггер 4 через переключатель 7 поступает сигнал, который устанавливает этот триггер в рабочее состояние. После отпуска кнопки б импульсы с генератора 3 будут поступать через пере ключатель 8 на клемму П 2 блока 2, При этом определитель полного гр аф а р аскр ыв ается, поскольку триггер 14 всех коммутирующих ячеек олока 1 будет находиться в нерабочем состоянии, и тем самым блоком 1 не будут 15 блокироваться ячейки блока 2, После полного раскрытия определителя Л на клемме П 7 блока 2 появляется сигнал, который через переключатель 7 поступает к триггеру 5 конца поиска и опрокидывает его (сигнальная лампоч ка конца поиска загорается).Предмет изобретенияУстройство для определения передачи графа, содержащее генератор тактовых импуль З сов, триггеры, логические элементы И, переключатели и кнопку пуска, отличающееся тем, что, с целью упрощения процесса определения передачи графа, оно содержит блок поиска путей, выполненный в виде матрицы коммутирующих ячеек, содержащих переключатели и триггеры, а также блок раскрытия определителей, выполненный в виде матрицы ячеек переоора, причем выход генератора тактовых импульсов через кнопку пуска и переключатель тактовых импульсов соединен со входами подачи тактовых импульсов блоков поиска путей и раскрытия определителей, управляющие входы переключателей тактовых импульсов соединень 1 с выходами триггера, один вход которого соединен с выходом блока попс. ка путей, а другой - с выхолом блока раскрытия определителей. выхоль 1 олоков поиска путей и раскрытия опрелелптелен соединены также через переключатель рода работ со входами трцггера конца поиска, а управляющий вход переключателя сигналов каждой ячейки перебора блэка раскрытия определителей через переключатель коммутирующей ячейки блока поиска путей, номер строки и столбца которой совпадает с номером строки и столбца рассматриваемой ячейки перебора, и через логический элемент И соединен со статическими выходами триггеров всех коммутирующих ячеек, номера строк и столбцов которых совпадают или с номером строки, или с номером столбца рассматриваемой ячейки перебор а.