4.9.2. [Q] - матриця головних перетинів
Перетином називають замкнуту поверхню, що охоплює частину графа електричного кола. Перетин графа є узагальненням поняття вузла. На кресленні перетин зображують у вигляді сліду цієї поверхні, що розтинає граф на дві частини. Тим самим перетин графа ділить його на два ізольованих подграфа.
Перетин називають незалежним або головним, якщо воно містить гілки зв'язку і тільки одну гілку дерева. Отже, кожна гілка дерева дозволяє побудувати тільки одна незалежна перетин, тому повне число головних перетинів n = q - 1 - числу гілок дерева.
На рис. 18 зображений граф електричного кола, що містить дерево з гілками 1, 2, 3 і гілки зв'язку 4, 5, 6. Пунктирними лініями на графі нанесені перетину. Кожне перетин містить тільки одну гілку дерева і, отже, є незалежним.
[Q] - матриця перетинів є таблицею, рядки якої відповідають перетинах графа, а стовпці - його гілкам.
Елементи матриці мають таке значення:
+ 1 - якщо гілка i входить в перетин j;
- 1 - якщо гілка i виходить з перетину j;
0 - якщо ж гілка i не пов'язана з перетином j.
Таким чином, елементи рядки показують, які гілки входять в перетин або виходять з нього.
Матриця перетинів [Q], побудована для графа, зображеного на рис. 16, має вигляд табл. 3.
4.9.3. [B] - матриця головних контурів
Контурна матриця - [B] є таблицею, рядки якої відповідають контурам графа, а стовпці - його гілкам.
Елементи матриці мають таке значення:
+1 - якщо контур i містить гілка j і напрямок обходу контуру збігається з напрямком гілки;
-1 - якщо контур i містить гілка j і напрямок обходу контура протилежно напрямку гілки;
0 - якщо ж контур i не містить гілки j.
Таким чином, елементи рядка матриці [В] показують, які гілки входять в контури і як вони спрямовані.
Контурна матриця може бути складена як для всіх контурів ланцюга, так і для незалежних контурів. Якщо контурну матрицю становлять для всіх контурів ланцюга, то її називають невизначеною. При цьому один з контурів вважають базисним або опорним, і він не входить в матрицю [В]. Повне число контурів визначають з умови, що кожна гілка графа входить в два протилежно спрямованих контуру.
Незалежна система контурів складається так, щоб в кожен контур входили гілки дерева графа і одна з хорд. Число головних (незалежних) контурів, яке дорівнює числу хорд, можна визначити як.
Якщо контурна матриця складена тільки для незалежних контурів, то її називають визначеною. За відомою контурної матриці можна побудувати граф ланцюга.
Певна контурна матриця, складена для графа рис. 19, має вигляд табл. 4.
| Зміст |
Кращі з кращих