Введение в информационные системы. Брюхомицкий Ю.А. - 67 стр.

UptoLike

ВУЗ: 

ТТИ ЮФУ | Таганрог

Составители: 

Рубрика: 

67
первого члена последовательность
(Т
1
) исчерпывается, а
(Т
2
) и
(Т
3
) раз-
биваются на последовательности:
(Т
21
) = (1);
(Т
22
) = (1);
(Т
23
) = (1);
(Т
31
) = (4,1,2,1);
(Т
32
) = (6,1,1,3,1,1).
Первые члены этих последовательностей соответствуют корням факто-
ра второго уровня, которые соединяются ребрами с теми корнями, из которых
они «вырастают». После этого первые три из них исчерпываются, а из двух ос-
тальных получаем:
(Т
311
) = (1);
(Т
312
) = (2,1);
(Т
321
) = (1);
(Т
322
) = (1);
(Т
323
) = (3,1,1).
Корни деревьев третьего уровня соединяем с соответствующими кор-
нями предыдущего уровня, и после удаления первых членов имеем одноэле-
ментные последовательности:
(Т
3121
) = (1);
(Т
3231
) = (1);
(Т
3232
) = (1),
которые представляют одновершинные факторы четвертого уровня.
Во многих случаях важно различать только неизоморфные деревья.
Корневая форма дерева для этих случаев может выступать как каноническая, в
которой изоморфные деревья неразличимы, а неизоморфные получают различ-
ные представления. Корнем такого дерева является специальным образом вы-
бранная вершина.
Одна из стандартных процедур выбора корня
состоит в следующем: из
дерева удаляются все концевые вершины и ребра, затем в полученном дереве
снова удаляются все вершины и ребра и т.д. до тех пор, пока исходное дерево не
сократится до единственной вершины или ребра. В первом случае оставшаяся
вершина выбирается в качестве корня и называется центром. Во
втором случае
две вершины и связывающее их ребро образуют бицентр. При этом за корень
принимается та вершина, из которой вырастает дерево с меньшим числом вер-
шин (если число вершин одинаково, то за корень принимается любая из вершин
бицентра). Так, для корневого дерева (рис. 5.13) корневая форма будет иметь
вид, показанный на
рис. 5.14.

Страницы