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

 

ОПИСАНИЕ

ИЗОБРЕТЕНИЯ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ бова Сййетскна

Соцналистнческиз республик

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

Заявлено 22.Х11.1966 (№ 1121629/26-24) с присоединением заявки №вЂ”

Приоритет—

Опубликовано 29,11.1968. Бюллетень № 9

Дата опубликования описания 13.V.1968

Кл. 42m, 36

МПК 6 061

V, л1х 681 325 67(088 8) Комитет ло делаю

Изойретеинй н открытий лри Совете Министров

СССР

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

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

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

Заявитель

УСТРОЙСТВО ДЛЯ ПОИСКА ПРАДЕРЕВЬЕВ

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

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

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

«вручную» существует большая вероятность повторного выбора одних и пропуска других.

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

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

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

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

30 соединены с горизонтальными шинами. Вторые

21МЗЗ входы триггеров рабочих ячеек, присоединенных к последующим горизонтальным шинам, подключены к выходу триггера последней рабочей ячейки, присоединенной к предыдущей горизонтальной шине распределителя. Выход (риггера последней рабочей ячейки, присоединенной к последней горизонтальной шине распределителя, соединен со входом триггера конца поиска, выход которого соединен со вторым входом генератора счетных импульсов. Входы 10 управления триггеров рабочих ячеек подсоединены через ключ сброса нуля к блоку питания. Причем псрвая из этих дуг выходит из вершины х,, являющейся началом пути, а последняя входит в вершину х — конец пути. 15

В каждую вершину. х,, r j/, k, не являющуюся ни началом, ни концом пути, заходит только по одной из дуг, образующих путь; в начало пути х не заходит, а из конца пути х,. не ис 1 ходит ни одна из дуг, ооразующпх данныи 20 элементарный путь.

Произведение величин всех h — 1 дуг, ооразующих данное прадерево, называют величиной прадерева.

Для решения топологическим методом сис- 25 тсмы h — 1 линейных алгебраических уравнений

QX= 1Г, (j=1,2, ...,n) где Q = llq/Ill (jk=1,2, ... n — 1) — неособая Зо матрица коэффициентов и — 1-ro порядка;

Л вЂ” матрица-столбец неизвестных;

à — матрица-столбец свободных членов, необходимо прежде всего матрицу коэффици- 35 ентов преобразовать в расширенную неопрсделенную матрицу Q = //(/р// (j, k=1, 2, ... и) и-го порядка, прибавив к первой из них дополнительную и-ю строку, элементы которой определяются формулой 40 и — 1

q„, = — ...„q,, (r=1,2, ...,n — 1), (2)

j а затем дополнительный и-й столбец с элементами, определяемыми формулой 45

n — 1

q,,= );д„ (3)

r=l

Непосредственной базой для решения топологическим методом системы уравнений (i) является граф G, изображающий расширенную матрицу Q(, построенный по следующим правилам: а) каждой паре, образованной столбцом и строкой матрицы Q с одинаковым порядко- 55 вым номером i=1,2,...,n, в графе 6 ставится в соответствие вершина х;; б) каждому недиагональному элементу q;,, (k /1) матрицы QI в графе 6 соответствуег дуга (/ (х,, х,), ведущая из вершины х„60 в вершину х,, причем этой дуге присваивается величина с(х,, х) = — q/I °

За исключением некоторых указанных ниже случаев, при q, 0 дуга U (х,, х,-) в графе

G не указывается. 65

После построения графа 6 необходимые для решения системы уравнений (1) определитель «t Q и алгебраические дополнения (— 1) 1- с1е1 Q (), где Q () — матрица, полученная из матрицы Q вычеркиванием J-й строки и k-го столбца могут быть в сражены следующим образом: величин всех прадеревьев графа G ( с1е1 Q = $ общим произвольно выбранным корнем; (4) величин прадеревьев 6 с корнем х,-, содержащих обязательно дугу U(x„, х ), ведущую из вершины х, в вершину х„ величиной с (х„, х,) =

= 1 независимо, от действительн oro значения q„„.. (о) (— 1) г det q(() = $

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

Данное устройство позволяет решать эту задачу автомагически.

На фиг, 1 дана схема устройства с ручным поиском.

Устройство состоит из распределителя 1. рабочих ячеек 2, сигнальных лампочек 8 H u(точника постоянного тока 4.

Распределитель образован системой вертикальных шин 1", 2",...i", j", /г", ..., (n — 1), и" и системой горизонтальных шин 1, 2, ... I., / . k (и — 1), и с числом шин в каждой системе, равным предлагаемому наибольшему количеству вершин графа h. Каждой вершине графа х, (i=1, 2, ..., h) соответствует пара шин, образованная одной вертикальной (" и одной горизонтальной 1 шинами с одинаковым порядковым номером 1 = 1" =/, соединяемыми накоротко в месте их пересечения.

Каждой дуге графа U (х,, х,), за исключением дуг, заходящих в корень прадеревьев, ставится в соответствие рабочая ячейка 2, состоящая из последовательно соединенных ключа 5 и диода б, присоединяемая к вертикальной шине i", соответствующей вершине х,, из которой исходит данная дуга, и к горизонтальной шине k, соответствующей вершине х, в которую эта дуга заходит таким способом, что при замкнутом ключе 5 диод б проводит ст вертикальной шины к горизонтальной. Каждая из сигнальных лампочек 8 присоединена одним концом к одной из горизонтальных шин и вторым — к минусовому зажиму источника 4. Плюсовой зажим источника присоединяется к вертикальной шине, соответствующей корню прадеревьев.

Расположение рабочих ячеек 2 в распределителе. 1 и присоединение источника тока, показанное на фиг. 1, соответствует графу, при2l2633

15

5 веденному на фиг. 2, причем корнем прадеревьев считается вершина х . !

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

Toiio >ocH -IccIloÉ зада iH lioHcK3 IIP3+cPcBbcB, шины с одинаковым порядковым номером соединяются в месте их пересечения накоротко.

Каждому недиагональному, отличному от нуля, элементу q,„ì3òðèöû Q, за исключением элементов q,, 1-й строки, соответствующей корню прадеревьев, ставится в соответствие рабочая ячейка, присоединяемая к горизонтальной шине i, соответствующей i-й строке матрицы Q, и к вертикальной шине k" с порядковым номером k-го столбца. Плюсовой

= -а>ким источника присоединяют к 1-й вертикальной шине, соответствующей корню прадеревьев, Составленное таким образом устройство тз1но соответствует графу, который был бы построен на базе расширенной матрицы коэффициентов Q .

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

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

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

65 хотя бы на одной паре шин не будет спгн11.i3, то соответствующими этим кчючам дугами и будут образованы прадеревья, так как не будет удовлствор"но условие б.

При количестве вершин графа меньшем, чем количество шин в горизонтальной и вертикальной системах шнн устройства, последнее может быть использовано без каких-либо конструктивных изменений, с тем только условием, чтобы лишние пары шин заранее были присоединены непосредственно к плюсовому зажиму источника, 11апри:1ер, путем включения рабочих ячеек с постоянно замкнутыми кл1оча.iti между вертикальной шиной, соответству.он1«й корню, и лишними горизонтальны>п1 нп1п11м.1.

Таким же образом оно можгт оыть приспособлено к решен:Iio системы уравнений с количеством уравнений, меньшим предполагасмoão, т. е. с порядком ра ширенной матрицы меньшим, чем количество горизонтальных ш н.

Если через пг, обозначить количество дуг графа, заходящих в вершину, то для поиска гсех прадеревьев графа с корнем х, необходни мо перебрать все I (m, сочетаний замкнуi.= I, i тых указанньв| выше способом ключей (п. одному, ведущему к каждой из горизонтальных шин, за исключением шины, соответствующей корню прадсревьев). Естественно, что уже при пяти-шести вершинах графа переключен,i: ключей вручную займет слишком много врсмени. Поэтому возникает необходимость автоматизировать перебор всех возможных сочтакий замкнутых ключей и сигнализацгпо о сочетаниях соответствующих прадерсвьев.

Функциональная схема устройства для поиска прадеревьев направленного графа (с автоматизацией поиска) приведена на фиг. 3. Это устройство содержит распределитель 1, рабочие ячейки 2, блок питания 4, триггеры 7, схему совпадения 8, осуществляющую логическую операцию «НŠ— И», схему 9 управления генератором счетных импульсов, блок пуска 10, генератор 11 счетных импульсов, триггер 12 конца поиска и ключ 18 сброса нуля.

Соединение шин распределителя 1 между собой, подключение его вертикальной шины, соответствующей корню прадеревьев, к источнику питания и присоединение рабочих ячеек 2 к шинам распределителя такое же, как в варианте устройства с ручным поиском. Горизонтальные шины распределителя присоединены ко входам схемы совпадения 8, выход которой подключен к одному из двух входов схемы 9 управления генератором счетных импульсов. Второй вход этой схемы присоединен к выходу блока пуска 10, а ее выход — к цепи управления генератора 11 счетных импульсор.

Рабочие ячейки 2 содержат, как и в варианте устройства с ручным поиском, последов;.тельно соединенные выпрямители и ключ, причем последний выполнен управляемым. Цепь управления ключа каждой рабочей ячейки подключена к выходу .триггера 7, принадлежа212633

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

Триггеры 7, принадлежащие всем рабочим ячейкам, присоединенным к одной и той же горизонтальной шине распределителя, соединены друг с другом по кольцевой схеме (выход предыдущего триггера присоединен ко входу последующего). Вторые выходы всех триггеров, принадлежащие рабочим ячейкам, присоединенным к первой горизонтальной шине распределителя, подключены к выходу генератора ll счетных импульсов, цепь управления которого присоединена к выходу схемы 9, и к выходу триггера 12 конца поиска. Вторые входы триггеров. принадлежащих рабочим ячейкам, присоединенным к одной из последующих горизонтальных шин распределителя, подключены к выходу триггера последней рабочей ячейки, присоединенной к предыдущей горизонтальной шине. Выход триггера последней из рабочих ячеек, присоединенных к последней горизонтальной шине распределителя, соединен со вторым входом триггера 12 конца поиска. Входы управления всех триггеров 7 подключены через ключ 18 сброса нуля к блоку питания

4 таким образом, что при замкнутом ключе 18 в рабочем состоянии (характеризующемся замыканием ключа в рабочей ячейке, к которой принадлежит данный триггер) находятся только триггеры первых ячеек в каждой группе рабочих ячеек, присоединенных к отдельным горизонтальным шинам. Через этот же ключ сброса нуля к блоку питания 4 присоединяется цепь управления триггера 12 конца поиска таким образом, чтобы при замкнутом ключе 18 выходной сигнал этого триггера не препятствовал подаче счетных импульсов от генератора 11 к триггерам 7 рабочих ячеек, присоединенных к первой горизонтальной шине распредел ителя.

Задача автоматизированного поиска прадеревьев направленного графа с помощью опи. санного выше устройства решается таким образом, что после программирования задачи, заключающегося в присоединении к шинам распределителя рабочих ячеек, соответствующих отдельным дугам графа (за исключением дуг, заходящих в корень прадеревьев), в подключении вертикальной шины, соответствующей корню прадеревьев, к плюсовому зажиму источника питания и в соединении триггеров рабочих ячеек указанным выше способом, устройство замыканием ключа 18 сброса нуля приводится в исходное положение. После отпускания ключа импульсы, подаваемые с генератора 11 на вторые входы триггеров, принадлежащих рабочим ячейкам 2, присоединенным к первой горизонтальной шине распределителя, приводят в рабочее состояние все по очереди триггеры этой группы.

При рабочем состоянии последнего триггера новый счетный импульс переводит в рабочее состояние первый триггер данной группы и одноврсменно создает счетный импу!1bc для группы триггеров, принадлежащих рабочим ячейкам, присоединенным ко второй горизонтаЛьной шине распределителя. Перевод из рабочего в нерабочее состояние последнего из этой группы триггеров приводит к переходу в рабочее состояние первого триггера данной группы и подаче счетного импульса на следующую группу триггеров. Подача счетных импульсов от генератора 11 и переключение триггеров происходит до тех пор, пока вследствие замыкания ключей в рабочих ячейках сигнал не появится на всех горизонтальных шинах распределителя, что приведет к исчезновению сигнала на выходе схемы совпадения и появлению на выходе схемы 9 сигнала, запирающего выход генератора счетных импульсов.

После снятия информации о включенных ключах рабочих ячеек сигнал от блока пуска

lO возобновляет подачу счетных импульсов от генератора 1(, что приводит к дальнейшим переключениям триггеров до очередного появления сигнала на всех горизонтальных шинах распределителя. При рабочем состоянии последних триггеров во всех группах триггеров новый счетный импульс приводит к срабатыванию триггера 12 конца поиска и к последующему прекращению подачи счетных импульсов от генератора 11. В данном состоянии устройства сигнал от блока 10 не возобновляет подачу счетных импульсов, что и свидетельствует о конце поиска.

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

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

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

212633 х„

9ис 2

4ьг 3

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

Редактор Б. Б. Федотов Текред Т. П. Курилко Корректоры: С. А. Башлыкова и А. П. Татаринцев

Заказ 901/15 Тираж 530 Подписное

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

Москва, Центр, пр. Серова, д. 4

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