Графи схем електричних кіл
У загальному випадку граф це сукупність відрізків довільної довжини і форми, званих гілками (ребрами), і точок їх з'єднання між собою, які називаються вузлами (вершинами). Теоретично електричних ланцюгів переважно знаходять застосування спрямовані , чи орієнтовані , графи , які кожному ребру приписується певне напрям, вказуване стрілкою. Розрізняють на правлені графи схем електричних ланцюгів та спрямовані графи проходження сигналів. Направлений граф схеми електричного ланцюга є спрощеною
діллю електричного ланцюга, що відображає тільки його топологічні (структурні)
властивості. Направлений граф проходження сигналів є наочним графічним зображенням системи рівнянь, що описує процеси в електричному ланцюгу. Надалі називатимемо направлений граф проходження сигналів сигнальним, а направлений граф схеми електричного ланцюга — просто графом ланцюга.
Граф ланцюга будують за його схемою заміщення. При цьому кожну гілка ланцюга замінюють відрізком довільної довжини і форми — гілкою графа, а кожен вузол ланцюга перетворять на вузол графа. На гілках графа стрілками вказують їх напрями, які збігаються з позитивним напрямом струмів відповідних гілок ланцюга. Нумерація гілок та вузлів графа та сама, що й нумерація гілок та вузлів схеми. Розширеному топологічному опису ланцюга (див. рис. 1.22, а) відповідає розширений граф ланцюга (рис. 1.26, а), скороченому топологічному опису (див. рис. 1.22, б) - скорочений (рис. 1.26, б).
Властивості графа не залежать від форми та довжини гілок, а також від взаємного розташування вузлів графа на площині та визначаються лише числом гілок р, числом вузлів q та способом з'єднання гілок між собою.
Графи, що мають одне й те самечисло вузлів та гілок, з'єднаних між собою однаковим чином, називаються ізоморфними (рис. 1.27). Змінюючи довжину і форму гілок, а також взаємне розташування вузлів графа на площині, можна отримати безліч графів, ізоморфних вихідному. Такі перетворення графа називаються ізоморфними. Кожен із варіантів зображення графа, отриманий шляхом ізоморфних перетворень, називається його геометричною реалізацією .
Якщо вузол i є кінцем гілки j , то вважається, що вони є інцидентними (від англ. inc & gt; підграфом .
Ступінь вузла графа дорівнює числу гілок, інцидентних даному вузлу. На рис.
Мал. 1.26. Розширений (а) та скорочений (б) графи ланцюга ряс. 1.22
1.26, а вузли (1), (2) та (4) мають другий ступінь, вузли (0) та (3) - четвертий.
Графи, ізоморфні з точністю до вузлів другого ступеня, називаються гомеоморфними. Після видалення з гомеоморфних графів вузлів другого ступеня і з'єднання порушених цим вузлам гілок гомеоморфні графи стають з морфними.
Таким чином, графи , що відповідають розширеному і скороченому логічному опису ланцюга , є гомеоморфними .
Прикладом гомеоморфних графів є графи, зображені на рис. 1.26.
Мал. 1.27. Ізоморфні графи
Планарним ( плоским ) називається такий граф, який у результаті з морфних перетворень може бути зображений на поверхні без перетину гілок. Так, граф, зображений на рис. 1.28 а, містить дві гілки, що перетинаються, однак він є планарним, так як існує ізоморфний йому граф, що не має перетину гілок (рис. 1.28, б). Неважко переконатися, що всі графи, які містять не більше чотирьох вузлів, є планарними.
Рос. 1.28. Усунення перетинів гілок графа за допомогоюізоморфних перетворень
Непланарний (об'ємний) граф може бути зображений на площині без перетину гілок (рис. 1.29). При видаленні з представлених малюнку графів будь-якої гілки вони стають планарними. Повний п'ятикутник і дводольний граф (рис. 1.29) називають також графами Понтрягіна - Куратовського.
Доведено, що довільний граф є планарним тоді і лише тоді, коли він не містить підграфів, гомеоморфних одному з графів Понтрягіна — Куратовського.
Електрична схема, якій відповідає планарний граф, також називається планарною. Непланарна схема відповідає непланарний граф. Таким же чином вводяться поняття планарного та непланарного ідеалізованих електричних ланцюгів.
Планарний граф ділить площину, де він зображений, на зовнішню і внутрішні області. Внутрішні області, обмежені гілками графа, називаються осередками або вікнами графа. Зовнішня щодо графа частина площини називається базисним осередком.
Мал. 1.29. Графи Понтрягіна - Куратовського: а - Повний п'ятикутник; б - дводольний граф
Шлях — це підграф, що є послідовністю з'єднаних між собою гілок, вибраних таким чином, що кожному вузлу (за винятком двох вузлів, званих граничними) інцидентні дві гілки, а граничним вузлам инци дентно по одній гілки (рис. 1.30). Кожна гілка та кожен вузол зустрічаються у дорозі лише один раз.
Замкнутий шлях, тобто шлях, у якого початкові та кінцеві вузли збігаються, називається контуром (рис. 1.31). Кожному з вузлів контуру інцидентні дві гілки. Очевидно, що між контурами графа та контурами вихідного ланцюга існує взаємно однозначна відповідність.
Мал. 1.30. Різні шляхи між вершинами (1) і (3) графа, зображеного наМал. 1.27
Зв'язний граф - це граф, між будь-якими двома вузлами якого існує, принаймні, один шлях (див. рис. 1.26 - 1.29).
Мал. 1.31. Деякі контури графа, зображеного на рис. 1.27
Деревом зв'язного графа називається зв'язний подграф, що включає всі вузли графа, але не містить жодного контуру. Гілки графа, що увійшли в дерево, називаються гілками дерева, гілки, що не ввійшли в дерево, називаються зв'язками (головними гілками, хордами). Кожному графу, як правило, може бути поставлене у відповідність кілька дерев, що відрізняються один від одного складом гілок дерева (рис. 1.32). Кожне з дерев графа, що містить р гілок і вузлів q, має m = q - 1 гілок дерева і n = + 1 головних гілок. При побудові дерев графіків електричних кіл до числа гілок дерева необхідно внести всі вироджені гілки, складені тільки з ідеальних джерел напруги. Гілки графіка, що відповідають виродженим гілкам ланцюга, що містять ідеальні джерела струму, до гілок дерева не включають.
Мал. 1.32. Деякі дерева графа, зображеного на рис. 1.27
Додавання до дерева графа будь-якої головної галузі утворює контур. Контури, утворені почерговим додаванням до дерева графа його головних гілок, називаються головними (рис.1.33). Таким чином, головний контур складається з гілок дерева та однієї головної гілки * .
Кожному дереву відповідає своя система з n = p - q + 1 головних контурів, причому головні контури, що відповідають певному дереву, відрізняються один від одного, принаймні однією гілкою, а саме головною гілкою, що входить до кожного з головних контурів.
* На рис.1.33 та наступних малюнках гілки дерева - суцільні лінії, головні гілки - штрихові.
Мал. 1.33. Головні контури графа (рис. 127), що відповідають дереву рис. 1.32,
Кожному головному контуру зазвичай присвоюють номер і приписують орієнтацію (напрямок обходу), що збігаються з номером і орієнтацією відповідної головної гілки * .
Перерізом зв'язного графа називається мінімальна сукупність гілок графа, при видаленні яких граф розпадається на дві ізольовані частини, кожна з яких може бути вузлом. Для знаходження гілок, що утворюють перетин, граф розсікають на дві частини замкнутою лінією — лінією перерізу (у разі планарних графів) або замкнутою поверхнею — поверхнею перерізу (у разі непланарних графів), побудованими таким чином, що жодна з гілок графа не переходить сікається цією лінією (поверхнею.) двічі. Сукупності гілок, що перетинаються лініями а, b, c (рис. 1.34), утворюють перерізи, тому що при видаленні кожної з цих сукупностей гілок граф розпадається на дві частини. Гілки, що перетинаються лінією d, не утворюють перерізу, так як при видаленні цих гілок граф розпадається більш ніж на дві частини.
Мал. 1.34. До визначення поняття перерізу графа
Очевидно, що кожна з частин, на які лінія (поверхня) перерізу розділяє граф ланцюга, може розглядатися як узагальнений вузол і, отже, для кожного перерізу графа можна скласти рівняння балансу струмів (струми гілок, однак орієнтовані щодо лінії перерізу, беруться з однаковим знаком).
* Для більшості завдань, що розглядаються в рамках цього курсу, нумерація головних контурів може бути обрана довільно, незалежно від номерів відповідних головних гілок.