Учебное пособие «Методы анализа и расчета электронных схем»

32

учитывается дважды.

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

Например, в полюсном графе на рис. 2.5,б инцидентными вершине 1 являются дуги I, II, III; вершине 2 – дуги II, IV, V и т.д.. Смежными вершинами являются 1 и 2, 1 и 3, 2 и 3 и т.д.. Степени всех вершин графа на рис. 2.5,б равны 3, а взаимные степени – равны 1.

Маршрут длины m определяется как последовательность m ребер графа (не обязательно различных) и инцидентных им вершин таких, что граничные вершины двух соседних ребер совпадают. Замкнутый маршрут начинается и заканчивается в одной и той же вершине. Маршрут, все ребра которого различны, называется цепью, а маршрут, для которого различны все вершины, называется простой цепью. Примером простых цепей в полюсном графе на рис. 2.5,б являются последовательности ребер I, II (длина цепи равна 2); I,V,IV (длина цепи равна 3); II,IV,VI (длина цепи равна 3) и т.д.

Замкнутая цепь называется циклом, а простая замкнутая цепь – простым циклом. Понятия цепи и циклов применимы и к орграфам, при этом направления дуг не учитываются (вместо орграфа рассматривается неориентированный соотнесенный ему граф). Простыми циклами полюсного графа на рис. 2.5,б являются последовательности ребер I, V, II (длина цикла равна 3); I,V,IV, III (длина цикла равна 4) и т.д.

Применительно к орграфам дополнительно рассматриваются ориентированные маршруты, когда начальная вершина каждой последующей дуги маршрута совпадает с конечной вершиной предыдущей дуги. Ориентированный маршрут, не содержащий повторяющихся дуг, называется путем, а не содержащий повторяющихся вершин – простым путем. Замкнутый путь называется контуром, а простой замкнутый путь – простым контуром. Граф на-

34

Рис. 2.6. Подграф (а) и дополнение подграфа (б)

Часть графа, содержащая некоторое подмножество ребер и все вершины исходного графа, называется суграфом.

Пример суграфа для графа на рис. 2.5,б приведен на рис. 2.7.

III

0

Рис. 2.7. Суграф полюсного графа

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

Связный ациклический граф называют деревом. Очевидно, количество ребер дерева на единицу меньше количества его вершин. Несвязный граф, компоненты которого являются деревьями, называется лесом. Примеры дерева и леса представлены на рис. 2.8.

35

Рис. 2.8. Дерево (а) и лес (б)

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

На рис. 2.9 приведены дерево, покрывающее дерево и дополнение дерева графа, представленного на рис. 2.5.

36

Рис. 2.9. Дерево (а), покрывающее дерево (б) и дополнение дерева (в)

Граф называют плоским (планарным), если он может быть представлен на плоскости без пересечения ребер (рис. 2.5,б).

Топологические матрицы и уравнения

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

Матрица инциденций (структурная матрица) представляет собой матрицу, строки которой соответствуют вершинам, а столбцы – ребрам графа. Для орграфов элемент (ij) равен +1 (–1), если i-ая вершина является начальной (конечной) для j-ой дуги и равен 0, если i-ая вершина и j-ая дуга не инцидентны. Каждый столбец матрицы инцидентностей обязательно содержит два ненулевых элемента (для орграфа эти элементы всегда имеют различные знаки), следовательно, сумма всех строк по mod 2 равна нулю, а это значит, что без потери информации одна из строк (чаще всего последняя) может быть удалена, что приводит к получению сокращенной матрицы инцидентностей.

37

Структурная матрица полюсного графа на рис. 2.5 имеет вид

Удаляя строку, соответствующую вершине 0, получим один из возможных вариантов сокращенной структурной матрицы

[Определение] Сечением связного графа называется совокупность ребер, удаление которых делает граф несвязным. [.]

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

[Определение] Совокупность ребер, инцидентных некоторой вершине графа, является сечением с центром в этой вершине и называется центральным сечением. [.]

В графе с вершинами имеется центральных сечений, причем каж-

38

дому из них соответствует строка матрицы инциденций.

На рис. 2.10 показаны примеры сечений связного графа, причем сечение C1 является центральным.

Рис. 2.10. Сечения связного графа

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

[Определение] Совокупность сечений графа, обеспечивающая линейную независимость системы уравнений по первому закону Кирхгофа, пред-

где — количество вершин графа; n — количество компонентов (частей) графа (для связного графа n=1).

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

[Определение] Система независимых центральных сечений носит на-

39

звание канонической. [.] [Внимание] В канонической системе сечений все сечения направляют

изнутри. [.] [Определение] Сечение, которому инцидентно только одно ребро по-

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

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

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

Рис. 2.11. Системы независимых сечений:

а – каноническая система; б – система главных сечений

Матричной формой представления системы независимых сечений является матрица независимых сечений . Строки матрицы соответствуют сечениям, а столбцы ребрам графа. Элемент ij матрицы равен +1 (–1), если j- ое ребро инцидентно i-ому сечению и направлена с ним согласно (противопо-

40

ложно), и 0, если j-ая ветвь не инцидентна i-ому сечению. В канонической системе сечений матрица независимых сечений соответствует сокращенной структурной матрице.

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

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

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

Каноническая форма матрицы (2.3) главных сечений имеет вид