Лекция 16.

1.5. Машинные алгоритмы выбора фундаментального дерева и оптимального разбиения ветвей

Алгоритм выбора фундаментального дерева

Обычно основные процедуры формирования исходных уравнений схемы (выбор фундаментального дерева, оптимальное разбиение ветвей, построение и преобразование матрицы сечений) реализуют на ЭВМ преобразованием структурной матрицы (§ 1.3). Так как размер этой матрицы по строкам определяется числом вершин v и по столбцам — числом ветвей l графа (υ∙l), причем она является сильно разреженной (коэффициент заполнения ненулевыми элементами равен 2l/υl = 2/υ), то в случае сложных схем использование полной структурной матрицы приводит к большой загрузке оперативной памяти.

Среди множества возможных алгоритмов, позволяющих свести соответствующие процедуры к операциям на множествах вершин и ветвей графа, рассмотрим алгоритмы, основанные на теоретико-множественном подходе [119].

Структура графа определяется множеством его ветвей X={x₁, х₂, ... , x_l), каждая из которых задается упорядоченной тройкой х_i = (α_i, β_i, γ_i). где α_i и β_i — cooт-ветственно начальная и конечная вершины, а γ_i — код ветви х_i (i=l, 2, ..., l). Множество V вершин графа представляется последовательностью v целых чисел, так что α_i и β_i — некоторые числа из V={1, 2, ..., υ}, т. е. α_i, β_iЄV. Код γ_i содержит информацию о подмножестве, к которому относится ветвь x_i и ее номера в этом подмножестве. Индекс i указывает на положение данной ветви в некоторой упорядоченной последовательности

ветвей графа. Например, у-ветвь с номером 8, направленная от вершины 23 к вершине 15 и расположенная двенадцатой в последовательности ветвей, запишется следующим образом: х₁₂ = (23, 15, y8).

Процедура формирования фундаментального дерева (ФФД) сводится к просмотру ветвей графа в установленной последовательности (иерархии) и их распределению между деревом и дополнением. Очередную ветвь вводят в дерево при условии, что она не образует контура с выбранной ранее совокупностью ветвей дерева. В результате множество X разбивают на два непересекающихся подмножества: подмножество ветвей дерева Х_T и подмножество хорд X_N.

В промежуточной ситуации совокупность ветвей графа, отнесенных к дереву, образует некоторый (вообще несвязный) подграф (рис. 1.40,а). Множества вершин каждой его части совместно с одноэлементными множествами, содержащими не вошедшие в этот подграф вершины, образуют совокупность классов эквивалентности V_j и определяют на Множестве V соответствующие разбиения. Ясно, что ветвь x_i должна быть отнесена к дереву, если и только если инцидентные ей вершины αi и β_i принадлежат различным классам эквивалентности. Пусть α_i V_r, β_i V_s; тогда x_i X_T при условии V_r≠V_s и x_i X_N при условии V_r=V_s. Включение ветви x_i в дерево означает объединение тех частей подграфа ветвей дерева, к которым принадлежат вершины этой ветви, т. е. классы эквивалентности V_r и V_s объединяются в класс V_r U V_s. Включение ветви x_i в дополнение не изменяет разбиения множества вершин V.

В исходном положении все v классов эквивалентности содержат по одной вершине, т. е. имеем сначала полное разбиение множества вершин. Первая же рассматриваемая ветвь относится к дереву и представляет двухэлементный класс, объединяющий пару вершин, инцидентных этой дуге. В дальнейшем каждое включение ветви в дерево сопровождается объединением двух классов эквивалентности, так что при наличии в дереве q ветвей разбиение состоит из υ—q классов. Процесс формирования дерева заканчивают после того, как совокупность ветвей графа образует дерево — связный подграф, не содержащий контуров. Ему соответствует полное отношение эквивалентности, при котором множество всех вершин графа образует единственный класс. В случае, если граф схемы несвязный, конечное разбиение содержит столько же классов эквивалентности, сколько частей имеется в исходном графе, причем каждый из этих классов объединяет все вершины соответствующей части.

При машинной реализации процедуры ФФД последовательные разбиения образуются идентификацией вершин на одномерном массиве, содержащем v ячеек, расположенных в той последовательности, которая принята при нумерации вершин. Так как любая вершина из данного класса может служить его представителем, то всем таким вершинам присваивается номер одной из них, который заносится в соответствующие ячейки. В исходном положении содержимое ячеек совпадает с их номерами, а в конечном — все ячейки для каждой части графа содержат одинаковые номера.

При рассмотрении очередной ветви x_i на массиве вершин содержимое ячеек считывается по адресам для α_i и β_i, в результате чего идентифицируются вершины в соответствующих классах эквивалентности, т. е. α_i→r_i, β_i→s_i, где r_i и s_i — номера вершин, играющих роль представителей этих классов (рис. 1.40,б). При r_i = s_i ветвь x_i относится к дополнению (x_i X_N), а при r_i≠s_i ветвь x_i относится к дереву (х_i Х_T) и одновременно идентифицируется r_i=s_i на множестве вершин v (во все ячейки, содержащие число r_i, заносится число s_i). Процедура ФФД повторяется до тех пор, пока не будет сформировано дерево. При наличии в графе взаимно определенных дуг процедура ФФД прерывается после рассмотрения всех (е, у)-дуг, так как необходимо решить вопрос о распределении взаимно определенных ветвей между множествами у и z. Соответствующая процедура оптимального разбиения взаимно определенных ветвей (ОР) будет рассмотрена далее. После ее выполнения процедура ФФД продолжается до образования v ветвей дерева или просмотра всех дуг графа. В последнем случае имеется возможность провести контроль по следующим тестам:

1) все ли е-ветви вошли в дерево (е V_T?);

2) все ли j-ветви вошли в дополнение (j V_N?);

3) равно ли число ветвей дерева числу независимых сечений (l_T=ν?). При утвердительных ответах процедура заканчивается. Наличие хотя бы одного отрицательного ответа свидетельствует о некорректности исходных данных или ошибке в операциях.

Алгоритм оптимального разбиения взаимно определенных ветвей

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

Как видно из соотношения (1.172), каждая новая y-ветвь увеличивает число вырожденных координат μ на единицу, а объединение двух частей (е, у) -графа уменьшает эту величину на два. Таким образом, к y-ветвям следует относить прежде всего те до-ветви, которые не связывают отдельных частей (е, у) -графа. Ветви, объединяющие какие-либо две части (е, у)-графа, целесообразно относить к у-ветвям, если их число не меньше двух.

В исходной последовательности ветвей графа до-ветви размещаются между подмножествами у и е. После применения процедуры ФФД к (е, у) -ветвям приходим к промежуточному разбиению на множестве вершин графа, при котором классы эквивалентности объединяют вершины соответствующих частей (е, у) -графа. Очевидно, ω-ветвь x_j должна быть отнесена к y-ветвям в двух случаях:

1) если инцидентные ей вершины принадлежат к одному и тому же классу эквивалентности, т. е. α_j,

2) если вершины принадлежат различным классам α_j V_r и β_j V_s, но найдется хотя бы еще одна ветвь x_k такая, что α_k V_r и β_k V_s или α_k V_s и β_k V_r.

Процедуру ОР начинают с идентификации вершин всех до-ветвей в соответствии с разбиением множества V, которое образовалось после просмотра всех (е, у)-ветвей в процедуре ФФД. Для этого номера вершин α_j и β_j до-ветвей (j=1, ..., l_ω) заменяют по схеме рис. 1.40,б содержимым соответствующих ячеек (представителями классов разбиения) массива вершин графа, т. е. осуществляется преобразование α_j→r_j; β_j→s_j (j=1, 2, . . ., l_ω). Сравнивая числа r_j и s_j, при r_j=s_j ветвь x_j относят к y-ветвям (х_j Х_у), а при r_j≠s_j пару чисел упорядочивают так, чтобы первое из них было меньше второго (это создает удобства на следующем этапе попарного сравнения до-ветвей).

После такого упорядочения и исключения ветвей, которые перенесены к множеству y-ветвей, получаем модифицированный массив до-ветвей. На нем сравнивают до-ветви и при обнаружении первой же пары, отвечающей второму из приведенных условий, идентифицируют массив вершин (r_j=s_j). Затем процедуру ОР повторяют до тех пор, пока после очередного сравнения не будет обнаружено ни одной пары ветвей, идентифицированные вершины которых соответственно совпадают. В результате получаем разбиение ω-ветвей, исходный массив которых представляется в новой последовательности: сначала располагаются y-ветви, выделенные процедурой ОР, а за ними следуют остальные ω-ветви, которые относятся к z-ветвям. Преобразованные коды ω-ветвей заносятся в память и при необходимости выводятся на печать.

Алгоритм определения матрицы сечений

Каждое сечение разбивает множество V вершин графа на два подмножества [108]. Одно из них V_0k, называемое нижней областью, объединяет вершины, которые фундаментальное дерево связывает с начальной вершиной ветви k-го сечения. Другое подмножество V_1k, называемое верхней областью, объединяет вершины, которые фундаментальное дерево связывает с конечной вершиной ветви k-го сечения (рис. 1.41). Очевидно, вершины инцидентной хорды должны принадлежать разным частям данного сечения, т. е. хорда x_j = (α_j, β_j) инцидентна сечению k, если α_i V_0k и β_j V_1k или α_i V_1k и β_j V_0k. В первом случае инцидентная хорда совпадает по направлению с сечением (берется со знаком плюс), а во-втором — противоположна сечению (берется со знаком минус).

Это положение используют для получения подмножеств хорд, инцидентных сечениям k=1, 2, ..., ν, причем совокупность таких подмножеств для всех сечений полностью определяет матрицу сечений π для хорд. Процедура определения матрицы сечений (ОМС) для данного k начинается с разбиения множества вершин V на подмножества V_0k и V_1k, в качестве представителей которых принимают соответственно числа 0 и 1. Предварительно в ячейку α_k массива вершин графа заносят нуль, а в остальные ячейки — единицы, и на этом массиве поочередно считываются значения для вершин всех ветвей дерева, кроме k-й. ветви. Идентифицированные значения (ρ_j, q_j) вершин (α_j, β_j) ветви дерева x_j принимают значения 0 или 1. Если их сумма по модулю два ρ_j q_j = 1, то на массиве вершин в ячейки для α_j и β_j заносятся нули. После просмотра всех ветвей дере

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

Следующий этап ОМС сводится к поочередному рассмотрению хорд и идентификации их вершин а_j→ρ_j и β_j→q_j в соответствии с разбиением, полученным на предыдущем этапе. Очевидно, хорда x_j инцидентна k-му сечению, если ρ_j≠q_j, причем она совпадает по направлению с сечением при ρ_j=0 и противоположна ему при ρ_j=1. По этим признакам код γ_j заносится в список инцидентных хорд с соответствующим знаком.

Процедуру ОМС повторяют для всех сечений (k=l, 2, ..., ν), причем каждый раз предварительно восстанавливается массив вершин (во все ячейки заносятся единицы). Признаком окончания этой процедуры является выполнение равенства k=v. Полученные в результате множества x_h хорд, инцидентных сечениям k=l, 2, ..., ν, позволяют построить матрицу сечений я (если она требуется). Для этого достаточно в k-й строке прямоугольной матрицы размера (ν∙σ) поставить ±1 в столбцах для хорд из x_k с соответствующим знаком.

Пример формирования сокращенного координатного базиса

Объединение процедур ФФД и ОР с процедурой ОМС составляет машинный алгоритм формирования сокращенного координатного базиса. В качестве примера рассмотрим граф (рис. 1.42,а), ветви которого xi=(α_i, β_i, γ_i) заданы в соответствии с установленной иерархией многомерным массивом

Идентификацию вершин при последовательном рассмотрении (е, у)-ветвей в процедуре ФД и соответствующие разбиения на массиве вершин графа представим следующим образом:

При i=l'=6 процедура ФФД прерывается и последнее разбиение используется для идентификации вершин ω-ветвей. Преобразование массива ω-ветвей в соответствии с процедурой ОР имеет вид

Идентификация вершин ω-ветвей по промежуточному разбиению

Модификация массива ω-ветвей

Идентификация вершин ω-ветвей

2:=7

Модификация массива ω-ветвей

Идентификация вершин ω-ветвей

5:=7

Модификация массива ω-ветвей

В результате получим разбиение с перекодировкой ω-ветвей и соответствующей перестановкой в исходной последовательности:

С учетом полученного разбиения ω-ветвей завершается процедура ФД:

Массив вершин

Ветви дерева

Хорды

Таким образом, совместное применение процедур ФФД и ОР дает разбиение множества ветвей графа на подмножества ветвей дерева и хорд:

Эти подмножества являются исходными для процедуры ОМС. Для сечения, определяемого ветвью дерева e1, имеем (k=1)

Массив вершин

Идентифицируя вершины хорд в соответствии с полученным разбиением массива вершин графа, получаем

Идентификация вершин хорд

Знак инцидентной хорды

+

+

+

+

γi

Отсюда имеем множество инцидентных данному сечению хорд х_1N={+у3, —y10, +z2, + z5, +j2}.

Аналогично можно определить множества инцидентных хорд и для остальных сечений. На рис. 1.42,б ветви дерева отмечены жирными линиями.

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