ВУЗ:
Составители:
Рубрика:
97
Тождество (2.1.6) отображает взаимосвязь 2-, 3-, 4-деревьев произвольной
схемы и позволяет находить одни типы K-деревьев через другие.
Множества K-деревьев, учитываемые в тождестве (2.1.6), можно
подразделить на множества объединительные – (i,0), (i,j,m,0), (i,j,0),
(i,m,0); путевые – (im,0), (ij,0) и комбинированные – (ij,m,0), (im,j,0). Для
нахождения объединительных множеств K-деревьев используется
следующее правило.
Правило 2.1.1. Множество K-деревьев графа вида (1, 2, ... q)
получается как множество деревьев схемы, образованной из исходной
схемы в результате объединения узлов 1, 2, ... q.
Для нахождения множеств путевых 2-деревьев используется другое
правило.
Правило 2.1.2. Множество 2-деревьев вида (ij,l), содержащих путь
между узлами i и j, получается как множество деревьев схемы,
образованной в результате подсоединения НУИ, причем ГНУИ направлен
от узла l к узлу i, а ПНУИ – от узла l к узлу j.
Нахождение множества комбинированных K-деревьев (ij,1,2, ... m)
требует объединения всех узлов исходной схемы, которые указываются в
коде как отдельные узлы. Далее к производной схеме с объединенным
узлом 1 + 2 + … + m применяется правило 2.1.2, что обеспечивает
получение искомого множества комбинированных K-деревьев.
Решим рассмотренную ранее задачу с использованием правила 2.1.1.
Множество 2-деревьев (1,0) схемы на рис. 2.1.1 соответствует множеству
деревьев схемы, изображенной на рис. 2.1.2,а. При объединении узлов 1 и
0 ветвь y
1
обращается в петлю и отбрасывается.
Рис. 2.1.2. Схема для нахождения 2-деревьев вида (1,0) схемы на рис. 2.1.1 (а)
и схема для нахождения 2-деревьев вида (12,0) схемы на рис. 2.1.1 (б)
Искомые деревья являются слагаемыми определителя данной схемы.
Отсюда получаем
(1,0) = 2(3 + 5 + 6) + 3(4 + 6) + 4(5 + 6) + 56 . (2.1.7)
Для нахождения множества K-деревьев вида (12,0) в соответствии с
правилом 2.1.2 используется схема, представленная на рис. 2.1.2,б.
y
5
y
2
y
6
y
3
y
4
0
1
2
3
y
5
y
6
y
3
y
4
0
1
2
3
а
б
Страницы
- « первая
- ‹ предыдущая
- …
- 95
- 96
- 97
- 98
- 99
- …
- следующая ›
- последняя »
