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

 

О Й И-С

ИЗОБРЕТЕН ИЯ

259495

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

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

Республик

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

Зависимое от авт. свидетельства ¹

Заявлено 27Х1.1968 (№ 1253037(18-24) с присоединением заявки №

Приоритет

Кл. 4.2m<, 7/48

МПК G 06g

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

СССР

Опубликовано 12.XII.1969. Бюллетень № 2 за 1970

Дата опубликования описания ЗХ1.1970

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

P. П. Базилевич и Е. Ф. Замора

Заявитель

УСТРОЙСТВО ДЛЯ ОПРЕДЕЛЕНИЯ ПЕРЕДАЧИ ГРАФА

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

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

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

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

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

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

10 Устройство представляет собой специализированную математическую машину для автоматического нахождения передачи графа в символическом виде. Под передачей Т графа понимают выражение где Р— передача к-го пути от источника к стоку, 20 Л вЂ” определитель гр афа, Л вЂ” алгебраическое дополнение к-го пути (т. е. определитель,подграфа, не касающегося к-го пути).

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

На фиг. 1 представлена функциональная

30 схема описываемого устройства; на фиг. 2—

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

Устройство состоит из блока 1 поиска путей, блока 2 раскрытия определителей, генератора

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

Блок 1 поиска путей (см. фиг. 2,а) состоит из матрицы и- коммутирующих ячеек 10 (где

n — наибольший порядок графа), столбца и буферных триггеров 11, подчиненных строкам матрицы коммутирующих ячеек, входных сдвоенных ключей 12 задания начальной вершины (источника), путей, подчиненных строкам матрицы коммутирующих ячеек, п выходных сдвоенных ключей 18 задания конечной вершины (стоки) путей, подчиненных столбцам матрицы коммутирующих ячеек. Каждая коммутирующая ячейка (см. фиг. 2, б) содерж ит триггер 14 с четырьмя выходами — двумя статическими, противоположными по снимаемому сигналу («0» или «1», и двумя динамическ ими, управляемый переключатель 15 сигналов, программирующие сдвоенные переключатели 16, логические элементы «И» 17 и

18 и усилитель 19 «нулевого» сигнала.

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

Блок, поиска членов определителей (фиг. З,а) состоит из матрицы и- ячеек перебора 20, селектора 21, п элементов «И» 22 и п элементов

«ИЛИ вЂ” НЕ» 28, подчиненных строкам матрицы ячеек перебора, генератора 24 одиночных импульсов со сдвоенной кнопкой 25 продолжения поиска, управляемого переключателя

2б сигналов, индикатора 27 снятия результатов («запись»), логического элемента «ИЛИ»

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

81 сигналов (см. ф1иг. 3, б).

Селектор 21 содержит и логических элементов «ИЛИ вЂ” HE» 32, каждый íà и входов, подчиненных столбцам матрицы ячеек перебора, п,логических элементов «ИЛИ» 83, каждый на (и+1) вход, также подчиненных столбцам матрицы ячеек перебора, и логический элемент «И» 84 на (и+1) вход.

Блок определения четности (см. фиг. 4) содержит матри цу диодов 85, строки и столбцы которой подчинены одинаковым строкам и столбцам матрицы ячеек перебора, логические элементы «И» 36 подачи на матрицу дио5

ЗО

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

88 создания разделения во времени опрашивающих импульсов, каждый из которых, починен одной, кроме пер вой, строке матрицы ячеек перебора, триггер 89 задержки, служащий для создания в импульсной последовательности задержки на один импульс, необходимой для задания:конечному триггеру четности нерабочего состояния, n — 1 триггер 40 определения четности числа инверсий отдельных индексов элементов определителей, каждый из которых подчинен одной, кроме последней, строке матрицы ячеек перебора, (п — 1) триггер 41 опроса состояния триггеров четности, каждый из которых подчинен аналогично предыдущим триггерам строкам матрицы ячеек перебора, и конечный триггер 12 четности с индикаторами знака «плюс» и

«минус».

Генератор 3 тактовых импульсов через один ключ пусковой кнопки 6 соединен с оигнальным входом управляемого .переключателя 8, два управляющих входа которого соединены со статическими выходами упр авляющего триггера 4. Один выход, переключателя 8 соединен с клеммой П1 блока 1, Второй выход переключателя 8 соединен через клемму П2 блока 2 с GHIIнальным входом управляемого переключателя 26. Источник «нулевого» сигнала («0»), т. е. сигнала, устанавливающего триггеры устройства в нерабочее («нулевое») состоян ие, соединен через второй ключ .пусковой кнопочки б с клеммой ПЗ блока 1 и через элемент 9 — с клеммой П4 блока 2, а также со входом установления нерабочего состояния триггера 5 конца поиска и через переключатель 7 рода работ в положении ZP Ь вЂ” со входом установления нер абочего состояния управляющего триггера 4 или в;положении

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

Один вход логического элемента «И» 17 каждой коммутирующей ячейки соединен с тем статическим выходом триггера 14 этой ячейки, на котором имеется единичный сигнал в рабочем состоянии триггера. Второй вход элемента «И» 17 соединен через горизонтальную шину и входной сдвоенный ключ 12 одной строки с одним выходом управляемого переключателя 8 (через клемму Пl) .

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

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

259495 столбца рассматриваемых коммутирующих ячеек. Входы установления нерабочего состояния трипгеров 14 всех коммутирующих ячеек и буферных триггеров 11 соединены с клеммой ПЗ. Управляющий вход переключателя 15 соединен свыходомодного iH3 сдвоенных переключателей 1б. Один вход этого переключателя соединен через вертикальную шину, к которой также подключены аналогичные входы переключателей остальных ячеек одного столбца со статическим выходом буферного триггера, подчиненного строке, номер которой совпадает с номером столбца рассматриваемой ячейки. Второй вход переключателя соединен с источником «нулевого» сигнала («0»). Выход второго из сдвоенных переключателей 1б соединен с управляющим входом переключателя 81 той ячейки перебора 20, которая находится в строке и столбце, номера которых совпадают соответственно с номерами строки и столбца рассматриваемой коммутирующей ячейки. Один вход второго переключателя 1б соединен с выходом элемента «И» 18, второй вход — с источником «нулевого» сигнала.

Один вход элемента «И» 18 соединен с одним выходом усилителя 19 «нулевого» сигнала и через вертикальную шину — с аналогичными выходами усилителей 19 всех коммутирующих ячеек одного столбца, а также через горизонтальную штину, соединенную с этой вертикальной,шиной — со вторыми выходами усилителей 19:всех коммутирующих ячеек, находящихся в строке, номер которой совпадает с номером столбца рассматриваемой ячейки. Второй, вход элемента «И» 18 соединен со вторым выходом усилителя 19, вход которого соединен со статическим выходом триггера 14, имеющим «нулевой» сигнал в рабочем состояниями триггера. Выход переключателя 15 сигналов, на котором имеется «единичный» сигнал при наличии таких же сигналов на его сигнальном и управляющем входах, соединен со входом установления рабочвго состояния триггера 14, другой выход— с тем д инамическим выходом триггера 14, с которого снимается «единичный» сигнал при переходе триггера с рабочего состояния в нерабочее, и сигнальным входом переключателя

-15 сигналов следующей в строке коммутирующей ячейки. Если же коммутирующая ячейка последняя в строке, то рассматриваемый выход соединен со входами установления нерабочего состояния трипгеров 14, принадлежащих коммутирующим ячейкам столбца, номер которого совпадает с номером строки рассматриваемой ячейки, а также со входом установления нерабочего состояния буферного триггера одной строки и через второй ключ входных сдвоенных ключей 12 одной строки, клемму П5, переключатель 7 рода работ в положении Р К вЂ” со входом установления рабочего состояния триггера 5. Второй динамический выход триггера 14 соединен через вертикальную шину, к которой подключены аналогичные выходы триггеров всех коммути5

65 рующих ячеек одного столбца, через один из сдвоенных выходных ключей 13 одного столбца и клемму Пб со вторым входом логического элемента «ИЛИ» 9 и входом установления рабочего состояния управляющего триггера 4.

Динамический выход каждого оуферного триггера 11 соединен с cKI Hàëüíûì входом управляемого переключателя 15 первой в одной строке коммутирующей ячейки.

Входы установления нерабочего состояния триггеров 80 всех ячеек перебора 20, а также триггера 29 задания начального состояния соединены с клеммой П4 блока 2 (см. фиг. 3).

Вход установления рабочего состояния тригге,ра 29 соединен с клеммой П2 блока 2. Динамический выход триггера 29 соединен через разделительные диоды с сигнальными входами управляемых переключателей Л каждой первой в строке ячейки перебора. Выход переключателя Л, на котором имеется «единичный» сигнал при наличии таких же сигналов на его сигнальном и управляющем входах, соединен со входом установления рабочего состояния триггера 80, второй выход — с динамическим выходом триггера 80 и сигнальным входом переключателя 81 следующей в строке ячейками первбора. Если же ячейка перебора 20,последняя в строке, то рассматриваемый выход соединен с сигнальным входом ,переключателя 81 первой в одной с ней строке ячейки перебора, а также со входами установления нерабочего состояния триггера 30 всех находящихся в следующей строке ячеек перебора и с одним входом элемента «И» 22, подчиненного следующей строке. Если же ячейка перебора последняя в последней строке, то рассматриваемый выход соединен через клемму П7 блока 2 и переключатель 7 рода работ (см. фиг. 1) в положении Ь вЂ” со входом установления рабочего состояния триггера 5 конца поиска, а также через клемму П8 блока 1 и замкнутый при программировании выходной ключ И вЂ” со входами установле ния нерабочего состояния триггеров 14 всех коммутирующих ячеек, находящихся в одном столбце с указанным ключом И. Выход К всех ячеек перебора одного столбца подключены ко входам элемента «ИЛИ вЂ” НЕ» 32 этого же столбца. Выход К каждой ячейки перебора связан непосредственно с управляющим входом переключателя 81,этой ячейки. Выход элемента «ИЛИ вЂ” НЕ» 82 соединен с одним из входов элемента «ИЛИ» 33 одного столбца. К остальным входам элемента «ИЛИ» 33 подключены выходы Т всех ячеек перебора одного с ним столбца. Выход Т каждой ячейки:перебора связан со статическим выходом триггера 80 этой ячейки, на котором имеется

«един ичный» сигнал в р абочем состоянии трипгера. Выходы элементов «ИЛИ» 33 всех столбцов соединены со входами элемента «И»

84. Кроме этого, один из входов элемента «И»

84 соединен через клемму П9 блока 2 с тем статическим выходом триггера 4, на котором имеется «единичный» сиги ал в рабочем со С259495

60 же строке

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

26. Выход переключателя 26, на котором ,имеется «единичный» сигнал при нал ичии такого же сигнала на с|игнальном входе и «нулевого» сигнала на управляющем входе, соединен с выходом генератора 24, а также со входами установления нерабочего состояния триггеров 80 всех ячеек .переоора 20 первой строки и одним из входов элемента «И» 22, подчиненного первой строке. Второй вход каждого элемента «И» 22 соединен с выходом элемента «ИЛИ вЂ” HE» 28 одной строки. Входы последнего элемента соединены с выходами К ячеек перебора одной с вим строки.

Выход элемента «И» 22 соединен совместно с выходом последней в следующей строке ячейки перебора с одним из входов элемента

«И» 22, принадлежащего следующей строке.

Выход элемента «И» 22 последней строки соединен с клеммой П7 блока 2.

Од ип вход элемента «ИЛИ» 28 соединен через кнопку 25 в нажатом состоянии с источником «нулевого» сигнала. Второй вход — с клеммой П4 блока 2. Выход элемента «ИЛИ»

28 через разъем Ч1 соединен со входом установления рабочего состояния .первого из триггеров 88 и нерабочего состояния остальных триггеров 88, а также триггеров 89 — 41 (см. фиг. 4). Выход переключателя 26, на котором .имеется «единичный» сигнал при наличии таких же сигналов на сигнальном и управляющем входах, соединен через раз.ьем Ч2 со входами установления нерабо его состояния триггеров 88 — 41. Триггеры 88, 89 и 41 соединены последовательно, образуя схему, создающую последовательность сдвинутых во времени импульсов. Дииамический выход каждого триггера 88 соединен с одним из входов всех элементов «И» 86, под.инснных ячейкам переоора 20 одной строки. Динамический выход триггера 89 соединен со входом установления нерабочего состояния триггера 42. Динамический выход каждого триггера 41 соединен со входом установления нерабочего состояния подчиненного одной строке триггера

40. Динамические выходы всех триггеров 40 соединены с симметричным входом триггера

42. Второй вход каждого элемента «И» 36 соединен с выходом Т той ячейки перебора 20, которой подчинен рассматриваемый элемент.

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

87, Выход каждого элемента «И» 86 и второй вход каждого элемента «И» 87 подсоединены к матрице диодов 85. Выходы всех элементов

«И» 87 одной строки соединены с симметричным входом триггера 40, подчиненного этой

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

Перед началом работы необходимо запрограммировать на устройстве задачу. Для этого программирующие переключатели 16 всех коммутирующих ячеpê, соответствующих на5

55 л ичным дугам графа, переводят в положения

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

12, который подчинен строке, с номером, равным,номеру вершинины, соответствующей началу пути т. е. |источника, а также тот сдвоенный ключ

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

7 рода работ ставят в положение, йР, Л и нажимают пусковую кнопку б. При нажатии этой кнопки на все триггеры устройства от источника «нулевого» сигнала поступает сигнал, устанавливающий .их в нерабочее состояние.

После отпуска кнопки б через переключатель

8 импульсы с генератора 8 поступают на клемму П1 блока 1 по иска путей. После определения первого пути Р1 от Источника к стоку графа на клемме Пб блока 1 появляется сигнал, который переводит управляющий триггер

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

1 прекращается. Импульсы начинают посту.пать на клемму П2 блока 2.

При этом определитель Л подграфа раскрывается, образованный из запрограммированного на устройстве графа исключением верш ин, входящих в найденный путь Р, и инцидентных им дуг. Сначала импульсы через переключатель 26 блока 2 будут поступать на матрицу ячеек перебора 20. После определения первого члена определителя Л1, о чем будет свидетельствовать появление «единичного» сигнала на выходе элемента «И» 84 селектора 21, загорается индикатор 27.

Далее импульсы будут поступать через переключатель 26 к блоку определения четности, где определяется знак, с каким входит найденное слагаемое выражение раскрытого определителя Л1. Результат записывают по загоревшимся индикаторам коммутирующих ячеек блока 1 (выражение пути Р,) и ячеек перебора блока 2 (выражение первого члена определителя AI) с учетом знака, определяемого llo индикатору. После записи нажимают кнопку 25, и поиск членов определителя Л продолжается. После нахождения всех членов этого определителя на клемме П7 блока 2 появляется сигнал, который поступает на клемму П8 блока 1 для подготовки этого блока к дальней шему поиску путей и на триггер

4, в результате этого триггер 4 переводится опять в нерабочее состояние. Подача импульсов на блок 2 прекращается, и они начинают поступать на блок 1 до момента нахождения второго пут и — Р H T. д.

После определения всех слагаемых числителя, т. е. величины ZP,,Л», на клемме П блока 1 появляется сигнал, который через переключатель 7 поступает на триггер 5 конца поиска и переводит его в рабочее состояние, 259495

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

После этого переключатель 7 переводят в положение Л. При нажатии кнопки б на триггер

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

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

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