Лекция 11.

Вид дерева определяется порядком расположения ветвей графа при записи структурной матрицы. При изменении этого порядка можно получить другое дерево. Часто при выборе дерева графа требуется соблюсти определенную иерархию ветвей, т. е. отдать предпочтение одной группе ветвей перед другими. Для обеспечения этого требования необходимо в исходной структурной матрице упорядочить ветви в соответствии с принятой иерархией. В частном случае фундаментальное дерево может представлять собой граф, все ветви которого сходятся к одной из вершин, называемой базисной, и направлены к ней (рис. 1.33). При этом каждое сечение охватывает соответствующую вершину графа (кроме базисной) и матрица сечений П совпадает со структурной матрицей А₀, образованной из матрицы А вычеркиванием

строки, которая соответствует базисной вершине, т. е. П=А₀. Такую систему независимых сечений называют канонической [108]. Для ее определения достаточно выбрать базисную вершину и пронумеровать остальные вершины от 1 до ν.

Применяя первый закон Кирхгофа к сечениям, по аналогии с (1.81) можно его записать в обобщенной форме:

(1.99)

Это важное соотношение является первым топологическим уравнением графа, описывающим связи между его ветвями через условие равновесия токов в ветвях.

Матрица контуров

В соответствии со вторым законом Кирхгофа алгебраическая сумма напряжений в контуре равна нулю. Полная система уравнений по второму закону Кирхгофа представляется матричным уравнением

(1.100)

где

(1.101)

а Р — матрица контуров.

Очевидно, строки матрицы Р должны соответствовать всем независимым контурам графа, а столбцы — ветвям графа, т. е. она является прямоугольной матрицей размера (σ∙l).

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

Если граф схемы плоский [14, 77], т. е. может быть вычерчен на поверхности без пересечения ветвей, то проще всего в качестве независимых контуров выбрать контуры, охватывающие ячейки графа — области, на которые граф разбивает занимаемую им поверхность (рис. 1.34). Каждому контуру приписывают определенное направление, например, по часовой стрелке.

Ветви графа, входящие в контур, являются инцидентными данному контуру. Матрица контуров Р, очевидно, запишется по следующему правилу: элемент матрицы ρ_ij= + 1 (или —1), если j-я ветвь графа инцидентна i-му контуру и направлена с ним согласно (или противоположно), и равен 0, если j-я ветсь не инцидента i-му контуру. Так, для графа на рис. 1.34,а

Плоский граф можно представить в виде выпуклого многогранника [107]. при этом ячейки играют роль граней, ветви — ребер, а вершины графа — вершин многогранника. Число ячеек графа на единицу меньше числа граней соответствующего многогранника, так как одна из его граней образуется внешней областью графа

Поэтому в соответствии с известным соотношением [18] для числа ячеек, а значит, и независимых контуров, получаем формулу

(1.102)

Для несвязного графа, состоящего из п частей, эта формула принимает вид

(1.103)

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

Матрицу контуров записывают для ветвей, инцидентных данному контуру (по строкам), или для контуров, инцидентных данной ветви (по столбцам). Так, для рассматриваемого примера (рис. 1.34,б)

При таком подходе к образованию контуров совокупность контуров, охватывающих ячейки (каноническая система контуров), соответствует дуальному дереву, все ветви которого идут от внешней дуальной вершины к внутренним дуальным вершинам (рис. 1.34,а). Независимую совокупность контуров можно получить также из условия, что ветви дуального дерева пересекают только по одной ветви графа схемы (рис. 1.34,в). Каждая из этих ветвей инцидентна только одному контуру и может быть поставлена ему в соответствие. В то же время с остальными ветвями каждая такая ветвь образует контур. Аналогичное соотношение имеется между хордами и ветвями дерева графа. Отсюда следует, что рассматриваемый способ образования совокупности независимых контуров по существу сводится к выбору некоторого дерева графа, причем каждый из контуров образуется соответствующей хордой и ветвями дерева (рис. 1.34,г). Такие контуры называют главными контурами. Направление и номер главного контура обычно считают совпадающими с направлением и номером соответствующей ему хорды. Число главных контуров равно числу хорд, т. е. σ=l—ν. Подставив в это соотношение значение v из (1.96) и (1.97) соответственно, получаем формулы (1.102) и (1.103).

Матрицу главных контуров записывают так же, как и в общем случае. Так, для графа, показанного на рис. 1.34,г, она имеет вид

Р асположив сначала столбцы, соответствующие всем ветвям дерева, а затем остальные столбцы, матрицу главных контуров можно привести к виду

(1.104)

где ρ — матрица главных контуров для ветвей дерева. В рассматриваемом примере

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

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