.1
Данное устройство предназначено для автоматического решения одной из основных топологических задач - поиска прадеревьев направленного графа или нахождения в общем виде решения системы линейных алгебраических уравнений.
Применение известного топологического метода для решения системы линейных алгебраических уравнений, состояш,ей из произвольно большого количества уравнений, практически уже при наличии четырех-пяти вершин становится затруднительным; количество прадеревьев в таких случаях может достигать нескольких десятков. При поиске этих прадеревьев «вручную суш,ествует большая вероятность повторного выбора одних и пропуска других.
Задачу автоматического (механизированного) выбора прадеревьев в принципе можно решать с помошью универсальных цифровых вычислительных машин, хотя и до сих пор не разработан алгоритм поиска прадеревьев, удобный для его реализации в таких машинах.
Данное устройство позволяет полностью механизировать, а также автоматизировать поиск всех возможных прадеревьев. Оно содержит распределитель, состоящий из системы вертикальных и горизонтальных шин с числом шин, равным количеству вершин графа. Вертикальные и горизонтальные шины с одинаковым порядковым номером соединены между собой,
горизонтальные шины подсоединены через сигнальные лампочки к одному зажиму источника тока. Рабочие ячейки, количество которых равно числу дуг графа без числа дуг, заходяших в корень графа, образованные последовательно соединенными диодом и ключом, подсоединены к вертикальной шине распределителя, соответствующей вершине, из которой исходит данная дуга, и к горизонтальной шине распределителя, соответствующей , в которую эта дуга входит. Точка соединения вертикальной и горизонтальной шин, соответствующая корню прадеревьев, подсоединена к другому зажиму источника тока.
В рабочие ячейки включены схема световой индикации и триггер для управления ключом и этой схемой. Триггеры рабочих ячеек, присоединенных к одной горизонтальной шине, соединены таким образом, что один вход последующего триггера соединен с выходом предыдущего, вторые входы триггеров всех рабочих ячеек, присоединенных к иервой горизонтальной шине распределителя, соединены с выходом генератора счетных импульсов, один
вход которого присоединен к выходу схемы управления генератором счетных импульсов с двумя входами, один из которых соединен с выходом схемы совпадения, а другой - с выходом схемы пуска. Входы схемы совпадения входы триггеров раоочих ячеек, присоединенных к последующим горизонтальным шинам, подключены к выходу триггера последней рабочей ячейки, присоединенной к предыдущей горизонтальной шине распределителя. Выход I риггера последней рабочей ячейки, присоединенной к последней горизонтальной шине распределителя, соединен со входом триггера конца поиска, выход которого соединен со вторым входом генератора счетных импульсов. Входы управления триггеров рабочих ячеек подсоединены через ключ сброса нуля к блоку питания. Причем первая из этих дуг выходит из вершины Xj, являющейся началом пути, а последняя входит в вершину х/ - конец пути. В каждую вершину х, , k, не являющуюся ни началом, ни концом пути, заходит только по одной из дуг, образующих путь; в начало пути Xj не заходит, а из конца пути л:/, не исходит ни одна из дуг, образующих данный элементарный путь. Произведение величин всех h-1 дуг, образующих данное прадерево, называют велнчиной прадерева. Для решения топологическим методом системы Л-/ линейных алгебраических уравненийQX W,(1) где Q (,2,...n-1) - неособая матрица коэффициентов п-1-го иорядка;X - матрица-столбец неизвестных; W - матрица-столбец свободных членов, необходимо прежде всего матрицу коэффициентов преобразовать в расширенную неопределенную матрицу Q - //ijj/J/ (, k 1, 2,... п) /7-го порядка, прибавив к первой из них дополнительную п-ю строку, элементы которой определяются формулой (,2,...,л-1),(2) а затем дополнительный д-й столбец с элементами, определяемыми формулой 27; (,2,...,«). Непосредственной базой для решения топологическим методом системы уравнений (1) является граф G, изображающий расширенную матрицу QI, построенный по следующим правилам: а)калсдой паре, образованной столбцом и строкой матрицы Qi с одинаковым порядковым номером г 1,2,...,«, в графе G ставится в соответствие вершина х- ; б)каждому недиагональному элементу (jj. ( матрицы Qi в графе G соответствует дуга и (х,, Xj), ведущая из верщины л в вершину Xj , причем этой дуге присваивается величина c(.t,, .1- ::-gy. За исключением некоторых указанных ниже случаев, при gj/ 0 дуга U (.г, Xj) в графе G не указывается. После построения графа G необходимые для решения системы уравнений (1) определитель det Q и алгебраические дополнения (1)У4 ft. detQ(), где Q(i) -матрица, полученная из матрицы Q вычеркиванием /-и строки и k-ro столбца могут быть выражены следующим образом: величин всех прадеревьев графа G с detQ Уобшим произвольно выбранным корвеличин прадеревьев G с корнем Xj, содержаишх обязательно дугу U(X, Xf,), ведущую из верши(-l)/- detQa) 2 ны х в вершину х, величиной c(xi,x/.) 1 независимо, от действительного значения q. (5) Формулы (4) и (5) подтверждают возможность приведения задачи решения системы уравнений (1) в общем виде к чисто топологической задаче - нахождению прадеревьев графа. Данное устройство позволяет решать эту задачу автоматически. На фиг. 1 дана схема устройства с ручным поиском. Устройство состоит из распределителя /, рабочих ячеек 2, сигнальных лампочек 3 и источника постоянного тока 4. Распределитель образован системой вертикальных шин 1, 2,...i, /, k,..., («-) , п и системой горизонтальных шин /, 2,... Г, у, k..., (п-1), п с числом шин в каждой системе, равным предлагаемому наибольшему количеству вершин графа Л. Каждой вершине графа X; (, 2, ..., Л) соответствует пара шин, образованная одной вертикальной i и одной горизонтальной Г шинами с одинаковым порядковым номером i, соединяемыми накоротко в месте их пересечения. Каждой дуге графа И (х, х,), за исключением дуг, заходящих в корень прадеревьев, ставится в соответствие рабочая ячейка 2, состоящая из последовательно соединенных ключа 5 и диода 6, присоединяемая к вертикальной шине i, соответствующей вершине х, из которой исходит данная дуга, и к горизонтальной шине k, соответствующей вершине х, в которую эта дуга заходит таким способом, что при замкнутом ключе 5 диод 6 проводит от вертикальной шины к горизонтальной. Каждая из сигнальных лампочек 3 присоединена одним концом к одной из горизонтальных шин и вторым - к минусовому зажиму источника 4. Плюсовой зажим источника присоединяется к вертикальной щине, соответствующей корню прадеревьев. Расположение рабочих ячеек 2 в распределителе / и присоединение источника тока, поведенному на фиг. 2, причем корнем прадеревьев считается вершина Xj.
Когда ноиск прадеревьев графа осущестьляется с целью решения системы уравнений (для нахождения определителя и алгебраических дополнений), количество шнн в каждой системе шин распределителя приравнивают предполагаемому наибольшему количеству уравнений, увеличенному на единицу; горизонтальные шины ставят в соответствие строкам рлсширенной матрицы коэффициентов Q, вертикальные - ее столбцам, причем порядо расположения шин в обеих системах соответствует порядку расположения строк и столбцов в матрице Q. Как и при решении чисто топологической задачи поиска прадеревьев, шины с одинаковым порядковым номером соединяются в месте их пересечения накоротко. Каждому неднагональному, отличному от нуля, элементу д, матрицы Q, за исключением элементов qj /-и строки, соответствующей корню ирадеревьев, ставится в соответствие рабочая ячейка, присоединяемая к горизонтальной шине /, соответствующей ;-й строке матрицы Q, и к вертикальной. шине k с порядковым номером k-ro столбца. Плюсовой зажим источника присоединяют, к /-и вертикальной шине, соответствующей корню прадеревьев.
Составленное таким образом устройство точно соответствует графу, который был бы построен на базе расширенной матрицы коэффициентов Q.
Поиск прадеревьев осуществляется таким образом, что в каждой группе рабочих ячеек, присоединенных к одной горизонтальной шине, замыкается по одному ключу. Если при выбранной комбинации замкнутых ключей на всех шинах появляется сигнал относительно минусового зажима источника, что можно обнаружить по свечению всех сигнальных лампочек 3, то дуги графа, соответствующие рабочим ячейкам с замкнутыми ключами, образуют прадерево графа.
Действительно, присоединенные через замкнутые ключи п-1 выпрямители образуют пути электрическому току, ведущие из пары шин, соответствующих корню прадеревьев, во все пары шин, соответствующие остальным вершиЕвм графа. При этом в каждую пару шин, за исключением пары шин, соответствующих корню, проводит ток только один из выпрямителей, а именно выпрямитель единственной рабочей ячейки с замкнутым ключом, присоединенной к горизонтальной шине данной пары. Если учесть, что каждая рабочая ячейка соответствует определенной дуге графа, а каждая пара шин - его определенной вершине, легко установить, что дуги, соответствующие данной группе п-1 рабочих ячеек с замкнутыми ключа.ми, удовлетворяют всем принятым выше условиям. Очевидно, также, что если при замкнутых п-1 ключах (по одному ведущему к горизонтальным шинам, соответствующим вершинам, не являющимся корнем прадеревьев)
хотя бы на одной паре шин не будет сигнала, то соответствующими этим ключам дугами не будут образованы прадеревья, так как не будет удовлетворено условие б.
При количестве верщин графа меньшем, чем количество щин в горизонтальной и вертикальной системах шин устройства, последнее может быть использовано без каких-либо конструктивных изменений, с тем только условием, чтобы лишние пары шин заранее были присоединены непосредственно к плюсовому зажиму источника, например, путем включения рабочих ячеек с постоянно замкнутыми к.иочами между вертикальной шиной, соответстпуюихса
корню, и лишними горизонтальными ишиилтл. Таким же образом оно может быть приспособлено к решению системы ypLiBHeHHii с количеством уравнений, меньшим предполагаемого, т. е. с порядком ра ширеиной матрицы меньшп.м, чем количество горизонтальных шин.
Если через т,, обозначить количество дуг графа, заходящих в вершину, то для поиска рсех прадеревьев графа с корнем Xj необходиМО перебрать все I т,- сочетаний замкну1 1, i J
тых указанным выше способом ключей (по одному, ведущему к каждой из горизонтальных щии, за исключением шины, соответствующей корню прадеревьев). Естественно, что уже при пяти-шести вершинах графа переключение ключей вручную займет слишком много времени. Поэтому возникает необходимость автоматизировать перебор всех возможных соче
таний замкнутых ключей и сигнализацию о сочетаниях соответствующих прадеревьев.
Функциональная схема устройства для поиска прадеревьев направленного графа (с автоматизацией поиска) приведена на фиг. 3. Это
устройство содержит распределитель /, рабочие ячейки 2, блок питания 4, триггеры 7, схему совпадения 8, осуществляющую логическую операцию «НЕ-И, схему 9 управления генератором счетных импульсов, блок пуска 10,
генератор // счетных импульсов, триггер J2 конца поиска и ключ 13 сброса нуля.
Соединение шин распределителя 1 между собой, подключение его вертикальной шины, соответствующей корню прадеревьев, к нсточнику питания и присоединение рабочих ячеек 2 к шинам распределителя такое же, как в варианте устройства с ручным поиском. Горизонтальные шины распределителя присоединены ко входам схемы совпадения 8, выход которой подключен к одному из двух входов ехемы 9 управления генератором счетных импульсов. Второй вход этой схемы присоединен к выходу блока пуска 10, а ее выход - к цепи управления генератора 11 счетных импульсов.
Рабочие ячейки 2 содержат, как и в варианте устройства с ручным поиском, последовательно соединенные выпрямители и ключ, причем последний выполнен управляемым. Цепь управления ключа каждой рабочей ячейки
щего этой ячейке. В каждой рабочей ячейке находится управляемый ее триггером световой индикатор, который включается одновременно с ключом данной ячейки.
Триггеры 7, принадлежащие всем рабочим ячейкам, присоединенным к одной и той же горизонтальной шине распределителя, соединены друг с другом по кольцевой схеме (выход предыдущего триггера присоединен ко входу последующего). Вторые выходы всех триггеров, принадлежащие рабочим ячейкам, ирисоедииеииым к первой горизонтальной шине распределителя, подключены к выходу генератора // счетных импульсов, цепь управления которого присоединена к выходу схемы 9, и к выходу триггера 12 конца поиска. Вторые входы триггеров, принадлежащих рабочим ячейкам, присоединенным к одной из последующих горизонтальных шин распределителя, подключены к выходу триггера последней рабочей ячейки, присоединенной к предыдущей горизонтальной щине. Выход триггера последней из рабочих ячеек, присоединенных к последней горизонтальной шине распределителя, соединен со вторым входом триггера 12 конца поиска. Входы управления всех триггеров 7 подключены через ключ 13 сброса нуля к блоку питания 4 таким образом, что при замкиутом ключе 13 в рабочем состоянии (характеризующемся замыканием ключа в рабочей ячейке, к которой принадлежит данный триггер) находятся только триггеры первых ячеек в каждой группе рабочих ячеек, присоединенных к отдельным горизонтальным шинам. Через этот же ключ сброса нуля к блоку питания 4 присоединяется цепь управления триггера 12 конца поиска таким образом, чтобы при замкнутом ключе выходной сигнал этого триггера не препятствовал подаче счетных импульсов от геиератора // к триггерам 7 рабочих ячеек, присоединенных к первой горизонтальной шине распределителя.
Задача автоматизированного поиска прадеревьев направленного графа с помощью описанного выше устройства решается таким образом, что после программирования задачи, заключающегося в присоединении к шинам распределителя рабочих ячеек, соответствующих отдельным дугам графа (за исключением дуг, заходящих в корень прадеревьев), в подключении вертикальной шины, соответствующей корню прадеревьев, к плюсово.му зажиму источника питания и в соединении триггеров рабочих ячеек указанным выше способом, устройство замыканием ключа 13 сброса нуля приводится в исходное положение. После отпускания ключа импульсы, подаваемые с генератора // на вторые входы триггеров, принадлежащих рабочим ячейкам 2, присоединенным к первой горизонтальной Шине распределителя, приводят в рабочее состояние все по очереди триггеры этой группы.
При рабочем состоянии последнего триггера новый счетный импульс переводит в рабочее состояние первый триггер данной группы и одновременно создает счетный импульс для групиы триггеров, принадлежащих рабочим ячейкам, присоединенным ко второй горизонтальной шине распределителя. Перевод из рабоче10 в нерабочее состояние последнего из этой груипы триггеров приводит к переходу в рабочее состояние первого триггера данной группы и подаче счетного импульса на следующую группу триггеров. Подача счетных импульсов
от генератора // и переключение триггеров происходит до тех пор, пока вследствие замыкаиия ключей в рабочих ячейках сигнал не появится на всех горизонтальных шинах распределителя, что приведет к исчезновению сигнала на выходе схемы совпадеиия и появлению на выходе схемы 9 сигнала, запирающего вьь ход геиератора счетИых импульсов.
После снятия ииформации о включенных ключах рабочих ячеек сигнал от блока пуска
10 возобновляет подачу счетных импульсов от генератора 11, что приводит к дальнейщим переключениям триггеров до очередного появления сигнала на всех горизонтальных шинах распределителя. При рабочем состоянии последних триггеров во всех группах триггеров новый счетный импульс приводит к срабатыванию триггера 12 конца поиска и к иоследуюшему прекращению подачи счетных импульсов от генератора 11. Е данном состоянии устройства сигнал от блока 10 не возобновляет подачу счетных импульсов, что и свидетельствует О конце поиска.
Предмет изобретения
1. Устройство для поиска прадеревьев направленного графа, отличающееся тем, что, с целью механизации операции, связанной с поиском прадеревьев, оно содержит распределитель, состоящий из системы вертикальных и горизонтальных щин с числом шин, равным количеству вершин графа, причем вертикальные и горизонтальиые шины с одинаковым порядковым номером соединены между собой, горизонтальные шины подсоединены через сигнальные лампочки к одному зажиму источника тока, а рабочие ячейки, количество которых равно числу дуг графа без числа дуг, заходящих в корень графа, образованные последовательно соединенными диодом и ключом, подсоединены к вертикальной шине распределителя, соответствующей вершине, ,из которой исходит данная дуга, и к горизонтальной щине распределителя, соответствующей верщине, в
которую эта дуга входит, точка же соединения вертикальной и горизонтальной шин, соответствующая корню прадеревьев, подсоединена к другому зажиму источника тока. 2. Устройство со п. 1, отличающееся тем, что,
с целью автоматизации операций, связанных с поиском и индикацией прадеревьев, а также повыщения его надежности, в рабочие ячейки включены Схема световой индикации и триггер для управления ключом и указанной схебочих ячеек, присоединенных к одной горизонтальной шине, соединены таким образом, что один вход последующего триггера соединен с выходом предыдущего, вторые входы триггеров всех рабочих ячеек, присоединенных к первой горизонтальной шине распределителя, соединены с выходом генератора счетных импульсов, один вход которого присоединен к выходу схемы управления генератором счетных импульсов с двумя входами, один из которых соединен с выходом схемы совпадения, а второй - с выходом схемы пуска, входы схемы совпадения соединены с горизонтальными
10
шинами, вторые входы триггеров раоочих ячеек, присоединенных к последуюод,им горизонтальным шинам, подключены к выходу триггера последней рабочей ячейки, присоединенной к предыдущей горизонтальной шине распределителя, выход триггера последней рабочей ячейки, присоединенной к последней горизонтальной шине распределителя, соединен со входом триггера конца поиска, выход которого соединен со вторым входом генератора счетных импульсов, входы управления триггеров рабочих ячеек подсоединены через ключ сброса нуля к блоку питания.
Xj
Хк
Риг 2
3
