Название: алгоритмизированное расчетно-графическое задание (В.А. Аксютин)

Жанр: Информатика

Просмотров: 1617


4.8. основные определения теории графов

 

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

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

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

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

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

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

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

Каждой ветви можно задать направление. Полагается, что

для любой ветви, за исключением источников, направление ветви

совпадает с направлением протекающего через элемент тока и

указывает на то, что узел, из которого вытекает ток, имеет более

высокий потенциал, чем узел, в который ток втекает. Поскольку

потенциалы узлов цепи до решения системы уравнений неизвестны,

направление ветвей графа, соответствующих пассивным элементам,

полностью произвольно. Для источников ЭДС примем направление

ветви графа от положительного к отрицательному полюсу источника (рис. 13).

 

Рис. 13

 

Для получения уравнений, описывающих режим работы цепи, удобно использовать обобщенную ветвь (рис. 14).

 

 

Рис. 14

 

Граф, состоящий из направленных ветвей, называется сигнальным или направленным графом.

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

последовательное соединение  и :  = + переименовать некоторые ветви с токами. Полученная цепь приведена на рис. 15, а на рис. 16 её направленный граф.

Рис. 15

 

Рис. 16

подграф – любая часть графа электрической цепи;

путь графа – подграф, образованный непрерывной последовательностью ветвей, связывающий выбранную пару ветвей;

связный граф – граф, в котором между любой парой выбранных узлов существует путь;

контур – путь по ветвям графа, который начинается и заканчивается в одном и том же узле, причём каждый узел входит в контур только один раз;

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

рёбра – ветви, входящие в состав дерева графа;

хорды или ветви связи – ветви графа, не вошедшие в состав

дерева;

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

главный контур – контур, который образован ветвями дерева и только одной хордой.

На рис. 17 изображено дерево графа, которое получено удалением ветвей 4, 5 и 6, являющихся хордами.

Рис. 17

 

Пусть q – число неустранимых узлов в схеме и р – число ветвей с неизвестными токами цепи.

Тогда

n = q – 1 – число ветвей дерева, которое равно числу независимых узлов, поскольку первая ветвь дерева содержит два узла, а каждая последующая ветвь вводит только один новый узел;

m = p – q + 1 – число ветвей связи, которое равно числу главных (независимых) контуров.

Если определению подлежат токи всех ветвей, то число неизвестных уравнений системы равно числу ветвей с неизвестными токами графа –

p = n + m. Так для схемы рис. 2 q = 4 (узел 5 устранимый и ; токи в параллельных ветвях 6 и 7 можно определить по правилу рычага),

p = 6, n = 3 и m = 3.

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

Основными из них являются:

узловая матрица А;

контурная матрица В;

матрица сечений Q.