Поддерево

Cтраница 4

Допустим теперь, что Т0 - наибольшее поддерево из Т, не содержащее двух подобных вершин. Тогда любая вершина из Т, смежная с какой-либо вершиной из Т0, подобна некоторой вершине из Г0, так как в противном случае Г0 не будет максимальным поддеревом указанного вида. Если Р также принадлежит Г0, то доказательство тривиально, так как тогда PQ принадлежит Г0 и, конечно, подобно самому себе при тождественном преобразовании. [46]

Для обратного обхода заталкивается узел, затем правое поддерево, а затем левое поддерево. [47]

Если NODE ( Q) имеет непустое правое поддерево, рассмотрим Q Р, Q Рв верхних диаграммах; NODE ( Q) - крайний левый узел этого правого поддерева. Если NODE ( Q) имеет пустое правое поддерево, рассмотрим Q Р в нижних диаграммах; чтобы найти место для NODE ( Q), необходимо перемещаться вверх по дереву до тех пор, пока не станет возможен первый шаг вправо. [48]

Пусть G - найденное таким способом свободное поддерево графа G. V), поскольку в G есть только один простой путь от V до V. [49]

Так как исходное дерево занумеровано, то поддерево является также занумерованным. [50]

Исключение узла с одним пустым поддеревом сводится к случаю исключения узла с обоими пустыми поддеревьями. [51]

В описанных ниже случаях пунктирные линии обозначают укорачиваемое поддерево. В некоторых случаях преобразование восстанавливает высоту поддерева до той, которая была до исключения; если это так, то алгоритм заканчивается, поскольку исключение не влияет на условие на высоту всех расположенных выше узлов. В других случаях сведения о том, что поддерево укорачивалось, должны быть продвинуты вверх по пути к корню. В каждом случае симметричные варианты не показаны. [52]

Назовем ветвью к вершине х дерева Т максимальное поддерево, содержащее х в качестве висячей вершины. Таким образом, число ветвей к вершине х равно ее степени. Вес каждой висячей вершины в дереве равен числу ребер в этом дереве. Вершина х называется центроидной, если вершина х имеет наименьший вес. Центроидом дерева называется множество его центроидных вершин. Можно показать также, что каждое дерево имеет центроид, состоящий из одной вершины или из двух смежных вершин. [53]

Граф, соответствующий рис. 31 и содержащий свободное поддерево. [54]

Страницы: 1 2 3 4