ОТЦ Попов.В.П (554120), страница 10
Текст из файла (страница 10)
В теории электрических цепей ц основном находят применение н а п р а в л е нные, илиориентированные, графы,у которых каждому ребру приписывается определенное направление, указываемое стрелкой. Различают направленные топологические графы и направленные графы прохождения сигналов. Н а и р а в л е н н ы й т оп о л о г и ч е с к и й г р а ф является упрощенной моделью электрической цепи, отражающей только ее топологические (структурные) 40 войства.
Н а п р а ален- (1) 2 (2) д (г) Е (ч) (1) ный граф прохождения сигналов представляет собой нагляд- 5 7 1 2 Ю нос графическое изображе- 1 ние системы уравнений, описывающей процессы в электрической цепи. В (0) (й) дальнейшем будем назы- а) б) вать направленный граф прохождениЯ сигналов рнс (йз. расширенный (а) н сокращенный (б) с и г н а л ь н ы и г Р а графы цепи, схема которой приведена на ф о м, а направленный рнс ! 2! топологический граф просто графом цепи. Граф электрической цепи строят по ее эквивалентной схеме, Каждую ветвь цепи заменяют при этом отрезком произвольной длины и формы — ветвью графа, а каждый узел цепи преобразуют в узел графа.
На ветвях графа стрелками указывают нх направления, которые совпадают с положительным направлением токов, протекающих по соответствующим ветвям цепи. Нумерация ветвеи и узлов графа таже, что и нумерация ветвей и узлов схемы. Расширенному топологическому описанию цепи (см. Рис. 1.21, а) соответствует расширенный граф пепи (рис.
1.25, а), сокращенному топологическому описанию (см. Рнс. 1.21, б) — сокращенный (рис. 1.25, б). Свойства графа не зависят от формы и длины ветвей, а также от взаимного расположения узлов графа на плоскости и определяются только числом ветвей р, числом узлов д и способом соединения ветвей между собой. Графы, имеющие одинаковые количества узлов и ветвей, соединенных между собой одинаковым образом, называются и з ам о р ф н ы м и (рис.
1.26). Изменяя длину и форму ветвей, а также взаимное расположение узлов графа на плоскости„можно получить бесчисленное множество графов, изоморфных исходному. Танис преобразования графа называются изоморфными преобр а з он а н и я м н. Каждый из вариантов изображения графа, полученный пУтем таких преобразований, называется его г е о м е т р и ч е с к о й реализацией. (1) д (2) Ф й) 4! (О) а) Рнс. !.26. Иаоыорфные графы Если узел 1 является концом ветви 1, то говорят, что они и иц и д е н т н ы (от англ.
1псЫепсе — сфера действия, охват). Каждая ветвь графа ннцидентна двум узлам. Часть графа, которая наряду с некоторым подмножеством ветвей графа содержит и все инцидентные им узлы, называется п о д г р а ф о м. Ст е и е н ь ю у з л а называется число ветвей графа, инцидентных данному узлу. На рис.
1.25, а узлы (7) и (4) имеют вторую степень, узлы (О) и (8) — четвертую. Графы, изоморфные с точностью до узлов второй степени, называются г о м е о м о р ф н ы м и. После удаления из гомеоморфных графов узлов второй степени и объединения инцидентных этим вершинам ветвей гомеоморфные графы становятся изоморфными. Таким образом, б 1 а) д) а) о) Рис. 1.28 Графи Понтрягина — Ку- ратонского: л — полный пвтпугольввв; 6 — аьуаольвый Рис. 1.27. Устранение пересечений ветвей графа с помощью иаоморфнмх преоврааонаиий графы соответствующие расширенному и сокращенному топологическому описанию цепи, являются гомеоморфными. Примером гомеоморфных графов являются графы, изображенные на рис.
1.25. П л а н а р н ы м (п л о с к и м ) называется такой граф, который в результате изоморфных преобразований может быть изображен иа плоскости без пересечения ветвей. Так, граф, изображенный на рис. ! .27, а, содержит две пересекающиеся ветви, однако он является планарным, так как существует изоморфный ему граф, не имеющий пересечения ветвей (рис. 1.27, б).
Можно убедиться, что все графы, содержащие не более четырех узлов, являются планарными. Непланарный (объемный) граф не может быть изображен на плоскости без пересечения ветвей (рис. 1.28). При удалении из представленных на рисунке графов любой ветви они становятся планарными. Полный пятнугольиик н двудольный граф (рис. 1.28) называюттакже графамн Понтрягина — Кур а т о в с к о го. Доказано, что произвольный граф является планарным тогда и только тогда, когда он не содержит подграфов, гомеоморфнык одному из графов Понтрягина — Куратовского. Электрическая схема, которой соответствует планарный граф, также называется и л а н а р н о й. Н е п л а н а р н о й с х е м е соответствует непланарный граф. Таким же образом вводятся понятия п л а н а рной и непланарной идеализированных электрических цепей.
(5) (Г) ч (г) у (5) 2 бр /б ((7) (з) з (г) т И) б Р /рбб (О) (Г) - (г) (Г) 5 (г) 5 г 5 Ф (и) (1) ( Л) (1) о Гг) 5 Гз) 5 Г Ы (г) (и) Рис. 1.30. Некоторые из коитуроз графа, изображенного на рис, 1.26 Планарный граф делит плос- (1) г (Г)) б (5) (Г) и Гг) у (4 рб бр жен, на внешнюю и внутренние б . врр " и а И ~ Рбб б Рбб бр б ббб б ббб рр-- называются ячейками или (Г) о (г) 5 (5) (Г) 5 (г) т (5) рф. в отношению к графу часть плоскости называется баз и с н о й Рис.
1,29, Различные пути между иерячейкой. шинамн (Г) и (а) графа, изображенного П у т ь — это подграф, являющийся последовательностью соединенных между собой ветвей, выбранных таким образам, что каждому узлу (за исключением двух узлов, называемых г р а н и чн ы м и) инцидентны две ветви, а граничным узлам инцидентно па одной ветви (рис. 1.29).
Каждая ветвь и каждый узел встречаются в пути только один раз. Замкнутый путь, т. е. путь, у которого начальные и конечные узлы совпадают, называется к о н т у р о м (рис. 1.30). Каждому из узлов контура инцидентны две ветви. Очевидно, что между контурами графа и контурами исходной цепи существует взаимно однозначное соответствие. С в я з н ы й г р а ф — это граф, между любыми двумя узлами которого существует, по крайней мере, один путь (см. Рис.
1.28 — 1.28). Д е р е в о м связного графа называется связный подграф, включающий все узлы графа, но не содержащий ни одного контура. Ветви графа, вошедшие в дерево, называются в е т в я м и д е р е в а; ветви, не вошедшие в дерево, называются с в я з я м и (г л а в н ы м и в е т в я м и, х о р д а м и). Каждому графу может быть поставлено в соответствие несколько деревьев, отличающихся друг от друга составом ветвей дерева (рис.
1.3!). Каждое из деревьев графа, содержащего р ветвей и (Г узлов, имеет Гп = б) — ! ветвей дерева и л = р — с) + 1 главных ветвей. При построении деревьев графов электрических цепей в число ветвей дерева обязательно вносят ветви, соответствующие идеализированным источникам напряжения. Ветви графа, соответствующие ветвям цепи, содержащим идеализированные источники тока, в число ветвей дерева не включают.
Добавление к дереву графа любой главной ветви образует контур. Контуры, образованные поочередным добавлением к дереву графа его главных ветвей, называются г л а в н ы м и конту р а м и (рис. 1.32). Таким образом, главный контур состоит из ветвей дерева и од- (1) 3 (г) (4 /б ()) 3 (г) Р (3) ~г (Р) 9 (Р) а) Рис 1.31. Некоторые из деревьев графа, изображенного иа рис. 1.26 ной главной ветви*>. Казкдому дереву соответствует своя система из и = р — а + 1 главных контуров, причем главные контуры, соответствующие определенному дереву, отличаются один от другого, по крайней мере, одной ветвью, а именно главной ветвью, входящей в казк- (1) гз (с) Р (о) ~ 2~ Рис. 1.32 Главные контуры графа (рис.
1.26), соответствующие дереву (рис !.31, а) дый из главных контуров. Каждому главному контуру обычно присваивают номер и приписывают ориентацию (направление обхода), совпадающие с номером и ориентацией соответствующей главной ветвиаа). С е ч е н и е м графа называется совокупность ветвей связного графа, пересекаемых замкнутой линией (линией сечения) или замкнутой поверхностью (поверхностью сечения), разделяющей граф на две части, причем ни одна из ветвей графа не пересекается дважды. Если удалить из связного графа ветви, образующие сечения, он распадается на две части, одна из которых может быть изолированным узлом. *) На ряс.
1.32 и последующих ветви дерева — сплошные липки, главные ветви — пунктирные. **) для большинства задач, рассматриваемых в рамках настоящего курса, нумерация главных контуров может быть выбраяа произвольио, иезааисимо от номеров соответствующих главиых ветвей. (1) ь (г) Р (л ()) и и 5 и) '„Я,;~О, (Р) (и) (1) а (2) б (3) ГР) Каждую из частей графа, лежащую по одну из сторон линии (поверхности) сечения можно рассматривать как обобщенный узел. Так, совокупности ветвей (1, 2, 3, 4), (1, 2, 5, 7), (3, 4, б), пересекаемых линиями а, б, в соответственно (рис. 1.33), образуют сечения, потому что при удалении каждой из этих совокупностей ветвей граф распадается на две части. Ветви, пересекаемые линией г, не образуют сечения, так как при удалении этих ветвей граф распадается более чем на две 4 а в 7 части.
г 5 Главным сечением гра- (1) У) фа называется такое сечение, в которое входит только одна ветвь выбран- г ного дерева. Остальные ветви, входяг щие в главное сечение, являются связями (рис, 1.34). Количество главных сечений равно количеству ветвей де- 5 (О) Ю рева, т.
е. т =- у — 1. Каждому дереву может бьипь поставлена в соответствие своя система главных сечений, причем главные сечения, соответствуюи(ие выбранному дереву, отличаются друг от друга, по крайней мере, одной ветвью — ветвью дерева, входящей в каждое из сечений. Главным сечениям графа присваивают номера и приписывают ориентацию, совпадающие с номером соответствующей ветви дерева и ее ориентацией относительно линии сечения. д) б (7) (в) г (о) г о) 5) 5) Рис 1.34. Главные сечения графа, приведенного на рис 1.26.
соответствующие деревьям, представленным: н — на рис. Ь31, а; б — на рис 1.31, б: в — на рис. 1.Зн в Если одна нз частей, на которые граф делится линией сечения, представляет собой изолированный узел, то соответствующее сечение называется к а н о н и ч е с к и м (сечения 3 и б на первом из графов. изображенных на рис. !.34). Топологическне матрицы Топологическне матрицы служат для аналитического описания гРафов, Такое описание можно представить в виде списка (перечня) ветвей графа с указанием, каким узлам онн ипцидентны и с какой ориентацией, или с помощью полной матрипы узлов А,.
46 Полная матрица узлов (полная матрица инциденцнй, матрица соединений, структурн а я м а т р и ц а ) — это таблица, в которой число столбцов равно числу ветвей графа р, а число строк равно числу узлов д. Номера строк совпадают с номерами узлов (строка с нулевым номером обычно располагается последней), номера столбцов совпадают с номерами ветвей. Элемент матрицы а;„, расположенный на пересечении Ой строки и )ьго столбца, может принимать значения +1, — 1 и О: агу --- +1, если ветвь ! ннцндентна узлу ! н направлена от этого узла; аы =- — 1, если ветвь / инцидентна узлу 1 и направлена к этому узлу; агу —— - О, если ветвь ! не ннцидентна узлу 1.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
