Графы схем электрических цепей

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

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

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

Рис. 1.26. Расширенный (а) и сокращенный (б) графы цепи, изображенной на рис. 1.22.

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

Если узел i является концом ветви j, то считается, что они инцидентны (от англ, incidence — сфера действия, охват). Каждая ветвь графа инцидентна двум узлам. Часть графа, которая наряду с некоторым подмножеством ветвей графа содержит и инцидентные им узлы, называется подграфом.

Степень узла графа равна числу ветвей, инцидентных данному узлу. На рис. 1.26, а узлы (1), (2) и (4) имеют вторую степень, узлы (0) и (3) — четвертую.

Графы, изоморфные с точностью до узлов второй степени, называются гомеоморфными. После удаления из гомеоморфных графов узлов второй степени и объединения ин;

Рис. 1.27. Изоморфные графы цидентных этим узлам ветвей гомеоморфные графы становятся изоморфн ым и.

Таким образом, графы, соответствующие расширенному и сокращенному топологическому описанию цепи, являются гомеоморфнъши.

Примером гомеоморфных графов являются графы, изображенные на рис. 1.27.

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

Непланарный (объемный) граф не может быть изображен на плоскости без пересечения ветвей (рис. 1.29). При удалении из представленных на рисунке графов любой ветви они становятся планарными. Полный пятиугольник и двудольный граф называют также графами Понтрягина — Куратовского.

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

Рис. 1.28. Устранение пересечений ветвей графа с помощью изоморфных преобразований.

Рис. 1.29. Графы Понтрягина — Куратовского:

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

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

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

Рис. 130. Различные пути между вершинами (1) и (3) графа, изображенного на рис. 1.27.

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

Связный граф — это граф, между любыми двумя узлами которого существует, по крайней мере, один путь (см. рис. 1.26—1.29).

Деревом связного графа называется связный подграф, включающий все узлы графа, но не содержащий ни одного контура. Ветви графа, вошедшие в дерево, называются ветвями дерева, ветви, не вошедшие в дерево, называются связями {главными ветвями, хордами). Каждому графу, как правило, может быть поставлено в соответствие несколько деревьев, отличающихся друг от друга составом ветвей дерева (рис. 1.32). Каждое из деревьев графа, содержащего р ветвей и q узлов, имеет т = q — 1 ветвей дерева ип = р — q + 1 главных ветвей.

Рис. 1.31. Некоторые из контуров графа, изображенного на рис. 1.27.

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

Добавление к дереву графа любой главной ветви образует контур. Контуры, образованные поочередным добавлением к дереву графа его главных ветвей, называются главными (рис. 1.33). Таким образом, главный контур состоит из ветвей дерева и одной главной ветви^[1].

Каждому дереву соответствует своя система изп = р — - q + 1 главных контуров_у причем главные контуры, соответ ствующие определенному дереву, отличаются один от другогоу по крайней мере, одной ветвью, а именно главной ветвьюу входящей в каждый из главных контуров.

Рис. 1.32. Некоторые из деревьев графа, изображенного на рис. 1.27.

Рис. 133. Главные контуры графа (рис. 1.27), соответствующие дереву рис. 1.32, в.

Каждому главному контуру обычно присваивают номер и приписывают ориентацию (направление обхода), совпадающие с номером и ориентацией соответствующей главной ветви^[2].

Сечением связного графа называется минимальная совокупность ветвей графа, при удалении которых граф распадается на две изолированные части, каждая из которых может быть узлом. Для нахождения ветвей, образующих сечение, граф рассекают на две части замкнутой линией — линией сечения (в случае планарных графов) или замкнутой поверхностью — поверхностью сечения (в случае непланарных графов), построенными таким образом, что ни одна из ветвей графа не пересекается этой линией (поверхностью) дважды. Совокупности ветвей {1, 2, 3, 4}, {1, 2, 5, 7}, (3, 4, 6}, пересекаемых линиями а, b, с (рис. 1.34), образуют сечения, потому что при удалении каждой из этих совокупностей ветвей граф распадается на две части. Ветви, пересекаемые линией d, не образуют сечения, так как при удалении этих ветвей граф распадается более чем на две части.

Очевидно, что каждая из частей, на которые линия (поверхность) сечения разделяет граф цепи, может рассматри;

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

Главным сечением графа называется такое сечение, в которое входит только одна ветвь выбранного дерева. Остальные ветви, входящие в главное сечение, являются связями (рис. 1.35). Число главных сечений равно числу ветвей дерева: т = q — 1.

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

Если одна из частей, на которые граф делится линией сечения, представляет собой изолированный узел, то соответствующее сечение называется каноническим (сечения 3 и 6 па рис. 1.35, а).

• [1] На рис. 1.33 и последующих рисунках ветви дерева — сплошные линии, главные ветви — штриховые.
• [2] Для большинства задач, рассматриваемых в рамках настоящего курса, нумерация главных контуров может быть выбрана произвольно, независимо от номеров соответствующих главных ветвей.