ВУЗ:
Составители:
Рубрика:
95
2.1. АЛГЕБРА K-ДЕРЕВЬЕВ И СХЕМНЫЕ ОПРЕДЕЛИТЕЛИ
Аппарат K-деревьев лежит в основе символьной диакоптики –
анализе электрических цепей по частям. Схемные определители,
являющиеся сомножителями в диакоптических формулах, можно
отобразить соответствующими множествами K-деревьев (K = 2, 3, ...).
Множество K-деревьев задается кодом, содержащим характерные номера
узлов. В частности, код может содержать номера всех узлов исследуемой
схемы. Код K-дерева указывается в скобках, что обозначает некоторое
множество K-деревьев.
Внутри кода K-дерева имеются разделители (точка или запятая),
которые подразделяют множество характерных вершин на подмножества,
относящиеся к отдельным компонентам связности K-дерева. Например,
код (ij,m,l) обозначает, что множество 3-деревьев (K = 3) рассматривается
относительно четырех узлов схемы i, j, m, l. При этом узлы i и j относятся
к одной компоненте 3-дерева, а узлы m и l не могут быть достижимыми
друг из друга, а также из узлов i и j.
Код множества K-деревьев может быть детализирован путем до-
бавления еще одной вершины согласно основному тождеству алгебры K-
деревьев
(i,j) = (il,j) + (i,jl). (2.1.1)
Это очевидно, поскольку узел l, принадлежащий схеме и не указанный в
первоначальном коде, может относиться как к одной, так и другой
компоненте 2-дерева. Если порядок следования узлов в части кода,
соответствующей некоторой компоненте K-дерева несущественен, то
данные ниже обозначения эквивалентны
(il,j) = (li,j), (i,jl) = (i,lj). (2.1.2)
Если схема, отображаемая K-деревьями, не удовлетворяет свойству
взаимности, то узел, следующий первым в части кода K-дерева, которая
соответствует некоторой компоненте, считается корнем или базисным
узлом этой компоненты.
Применяя тождество (2.1.1) к каждому слагаемому правой части
повторно, можно довести количество узлов в коде до числа узлов схемы и,
тем самым, решить задачу перечисления всех 2-деревьев схемы,
множество которых задает первоначальный код. В качестве примера
найдем множество 2-деревьев типа (1,0) в полной схеме с четырьмя
узлами, представленной на рис. 2.1.1.
Страницы
- « первая
- ‹ предыдущая
- …
- 93
- 94
- 95
- 96
- 97
- …
- следующая ›
- последняя »
