Графы и их использование для описания цепей

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

=> топологические уравнения, характеризующие структурные особенности цепи, или се конфигурацию. Для их составления используются граф цепи и топологические матрицы,

=> компонентные уравнения, отражающие характеристики компонентов (ветвей).

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

Основные понятия теории графов. Топологическое описание цепи должно содержать:

=> способ соединения ветвей;

=> опорные направления для токов ветвей и напряжений.

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

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

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

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

Помимо ненаправленного и направленного графов известно большое количество других видов графов. Среди них следует выделить:

=> непланарный (пространственный) граф с пересекающимися (1 и 2) ветвями (рис. 2), если при его изображении на плоском чертеже невозможно избежать пересечения ветвей, и планарный (плоский) граф, который можно изобразить на плоскости без пересечения ветвей (рис. 3, а);

Рис. 2. Непланарный Рис. 3. Планарный граф (я) и его подграфы (б).

граф.

=> подграф (рис. 3,6), представляющий собой любую совокупность ветвей и вершин основного графа (рис. 3, а);

=> связный 1раф (рис. 3, а), в котором имеется хотя бы один путь между любой парой узлов, и несвязный 1раф в противном случае (рис. 3,6);

=> путь графа — подграф в виде непрерывной последовательности ветвей (1−3-5−8-9 на рис. 3, а), связывающую пару выбранных узлов (I, IV), с прохождением каждого узла нс более одного раза;

=> контур — связный подграф, имеющий замкнутый путь, в котором начальная вершина совпадает с конечной. В контуре к каждому узлу присоединены, но две ветви. На рис. 4 изображены все 7 контуров ненаправленного графа на рис. 1,6;

=> сечение — любая минимальная совокупность ветвей (4, 5, 6 на рис. 3, а), при удалении которых граф распадается на два несвязных подграфа.

• 119
• (рис. 3,6). Восстановление любой ветви из удаленного набора приводит к связному графу. Отметим, что количество ветвей в сечении не фиксировано. В частном случае несвязный подграф может не иметь ветвей и состоять только из одного узла. Число возможных сечений может намного превысить число узлов. Сечение изображается линией, однократно пересекающей каждую его ветвь. Для изображения будем использовать овал или линию со стрелками (рис. 3, а), указывающими на внутреннюю область сечения, которую называют обобщенным узлом. Введение этого понятия позволяет однозначно задать направление токов: втекающих в узел, вытекающих из узла.

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

Рис. 4. Полный набор контуров ненаправленного графа на рис. 1,6.

=> дерево графа, представляющее собой связный подграф, который содержит все узлы исходного связного графа и не содержит контуров. Между любой парой узлов дерева имеется единственный путь. Ветви, принадлежащие дереву, будем называть ребрами; а ветви, не принадлежащие дереву, — хордами. Все хорды, соответствующие данному дереву, образуют подграф, называемый дополнением дерева. На рис. 5, а приведено дерево для графа на рис. 1,6, при этом ребра нанесены сплошными линиями, а хорды — пунктирными. Число ребер'. N_p = N_y — 1 = 4 — 1 = 3; число хорд: N_x = N_B— N_y + 1= 6 — 4 + 1=3. Число возможных деревьев N_a исходного графа очень быстро растет с увеличением числа узлов: для N_y = 4 имеем N_a = 16 (рис. 6); для N_y = 6 — N_a = 1296. С деревом связаны главные контуры и главные сечения, которые определяют ряд важных свойств графа;

=> главный контур, образующийся при подключении хорды к дереву графа (рис. 5,6). Уравнения равновесия напряжений в главных контурах являются независимыми. Для выбранного дерева число главных контуров равно числу его хорд N_x = N_B — N_y + 1 = 6 — 4 + 1 = 3;

=> главное сечение, содержащее только одну ветвь дерева (ребро), которая нс входит в другие сечения, и несколько хорд. Поэтому уравнения.

равновесия токов в главных сечениях являются независимыми. Для выбранного дерева число главных сечений равно числу его ребер

Рис. 5. Полный набор главных сечений (а) и главных контуров (б) ненаправленного графа на рис. 1,6.

Рис. 6. Полный набор деревьев ненаправленного графа на рис. 1, 6.

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

=> автоматизировать процесс составления уравнений исследуемой цепи по законам Кирхгофа;

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

В общем случае для построения топологической матрицы предварительно следует:

=> составить (выбрать) дерево исходного графа;

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

=> выбрать положительные направления ветвей графа. Этот выбор подчинен получению единичной подматрицы и обосновывается при рассмотрении конкретных матриц.

Изложение материала иллюстрируется на примере графа с N_y = 4 узлами и N_B = 6 ветвями. На рис. 7,а, изображено дерево графа, содержащее:

=> три ребра (1,2, 3) и три хорды (4, 5, 6);

=> три главных сечения (рис. 7,6), каждое из которых содержит только пересекаемые сечением ветви графа: сечение 1 содержит ребро 1 и хорды 5, 6; сечение 2 — ребро 2 и хорды 4, 6 (обратить внимание на разметку); сечение 3 — ребро 3 и хорды 4, 5. Номер каждого сечения совпадает с номером принадлежащего сечению ребра. Ток ребра каждого главного сечения направлен во внутрь сечения (обобщенного узла);

=> три главных контура 4, 5, 6 (рис. 7,в,г, 6). Направление контурного тока совпадает с направлением тока входящей в контур хорды.

Рис. 7. Исходный граф (а), его главные сечения (б) и главные контура (в) для иллюстрации построения топологических матриц Матрица инциденций. Среди топологических матриц широко используется N_yxN_B матрица инциденций А_а = я, у, или соединений узел — ветвь. Каждая /-я строка такой матрицы показывает, какие ветви связаны с данным узлом, или, как говорят, инцидентны /-у узлу. Отсюда название матрицы. Для направленного графа (рис. 7,а) матрицу инциденций можно представить в виде табл. 1, строки которой являются порядковыми номерами узлов (/), а столбцы — номерами ветвей (/). Число.

строк полной матрицы А_а = [я, у] равно числу узлов графа (N_y = 4), а число столбцов — числу ветвей (N_B = 6).

Каждый элемент а, у матрицы А_а равен:

=> -1, еслиу'-я ветвь входит в /-й узел;

=> +1, если у'-я ветвь выходит из /-го узла;

=> 0, если она нс соединена с /'-м узлом.

Отмстим, что при определении элементов а_и можно пользоваться разными правилами, лишь бы они были единообразными при определении знаков всех ненулевых элементов матрицы.

Таблица 1.

Поскольку каждая ветвь соединена с двумя узлами, в один из которых она входит, а из другого выходит, то сумма элементов в каждом столбце, а значит, и сумма элементов всей таблицы равна нулю. Следовательно, любую строку можно рассматривать как линейную комбинацию остальных строк. Поэтому одну из строк, обычно соответствующую базисному узлу (например, узлу IV), вычеркивают. Образующаяся при этом редуцированная матрица, А размером (N_y — 1) xW_B называется матрицей узлов. Если каждой у'-й ветви сопоставить ток /, (табл. 1), то закон Кирхгофа для токов в матричной форме имеет вид:

где i — вектор токов размерности N_K 0 — нулевой вектор размерности N_y- 1.

Матрицу соединений, А можно представить в виде подматриц А_р и А_х, относящихся к ребрам и хордам (соответственно левая и правая часть табл. 1).

Матрица главных сечений. Каждое главное сечение включает в себя одно ребро и нескольких хорд. Число главных сечений равно числу ребер N_p. Поэтому уравнения равновесия токов в главных сечениях являются независимыми. На рис. 7,6 показаны три главных сечения (1,2,3) выбранного дерева.

Матрицу главных сечений П можно представить в виде табл. 2 размером (N_y — 1) х Л^г_в, /-я строка которой соответствуют главному сечению, а /-й столбец — ветви графа. Каждый элемент а, у этой матрицы равен:

=> -1, если /-я ветвь выходит из /-го сечения;

=> +1, если/-я ветвь входит внутрь /-го сечения;

=> 0, если j-я ветвь не содержится в сечении.

Таблица 2.

Обратить внимание на заполнение строки 2 табл. 2. Так как ветви 2 и 4 входят внутрь сечения 2 (рис. 7,6), в столбцы 2 и 4 внесены значения + 1; ветвь 6 выходит из сечения, поэтому внесено значение -1.

Матрица П описывает соединения ветвей, входящих в независимые сечения. Ее можно представить в виде единичной матрицы 1 порядка iV_p и подматрицы П_х порядка Л^г_р х Л_х: П = [1 П_х]. Каждая /-я строка П_х показывает, какие хорды входят в главное сечение, образованное соответствующим ребром дерева, а /-й столбец — в какие сечения входит /'-я хорда.

Элементы а_& матрицы II являются коэффициентами уравнений, которые составляются «тля токов в главных сечениях и могут быть представлены в следующем виде:

ip ⁼ [4 h /з]^т; *x ⁼ [4 4 4] ^т; т — знак транспонирования матрицы, позволяющий для удобства записи столбец представить в виде строки.

В каждое уравнение системы входит единственный ток ребра, поэтому можно выразить токи ребер через токи хорд: i_p = - П _х i _х .

Матрица главных контуров. Каждый главный контур состоит из одной хорды, которая не входит в другие контуры, и нескольких ребер. Поэтому число главных контуров равно числу хорд N_K и уравнения равновесия напряжений в главных контурах являются независимыми. На рис. 1,в, г, д показаны три главных контура (4, 5, 6), соответствующих выбранному дереву.

Матрицу главных контуров Г можно представить в виде табл. 3 размером [/V_B — (Л/у — 1)] х N_B, /'-я строка которой соответствуют главному контуру, a у-й столбец — ветви графа. Каждый элемент я, этой матрицы равен:

=> +1, если направление/'-й ветви совпадает с направлением обхода контура;

=> -1, если направление у-й ветви не совпадает с направлением обхода контура;

=> 0, если ветвь не входит в главный контур.

Матрицу Г можно разбить на две части: подматрицу Г_р порядка N_x х N_p, которая получается из матрицы главных контуров исключением всех хорд, и единичную матрицу порядка N_x: Г = [Г_р 1]. Каждая /-я строка подматрицы Г_р показывает, какие ребра входят в главный контур, образованный замыканием соответствующей хорды, а у'-й столбец — в какие контуры входиту-е ребро.

Таблица 3.

Элементы а$ матрицы Г являются коэффициентами уравнений, которые составляются по закону Кирхгофа для напряжений в главных контурах и могут быть представлены в следующем виде:

Up = [м, U2 из]^т; u_x = [i/4 и$ /б] ^Т;т — знак транспонирования матрицы.

В каждое уравнение системы входит одно напряжение хорды м_у, поэтому с помощью матрицы Г_х напряжения хорд можно выразить через напряжения ребер: