Центроид дерева

Ветвь к вершине v дерева – это максимальный подграф, содержащий v в качестве висячей вершины. Вес вершины k – наибольший размер ее ветвей. Центроид (или центр масс) дерева C – множество вершин с наименьшим весом: C = { v | c (v) = }.

Вес любого листа дерева равен размеру дерева. Высота дерева с корнем, расположенным в центроиде, не больше наименьшего веса его вершин.

Свободное дерево порядка n с двумя центроидами имеет четное количество вершин, а вес каждого центроида равен n /2.

Теорема 14.3 (Жордана). Каждое дерево имеет центроид, состоящий из одной или двух смежных вершин.

Пример 14.1. Найти наименьший вес вершин дерева, изображенного на рис. 14.1, и его центроид.

Рис. 14.1

Решение. Очевидно, что вес каждой висячей вершины дерева порядка n равен n – 1. Висячие вершины не могут составить центроид дерева, поэтому исключим из рассмотрения вершины 1, 2, 4, 6, 12, 13 и 16. Для всех остальных вершин найдем их вес, вычисляя длину (размер) их ветвей.

Число ветвей вершины равно ее степени. Вершины 3, 5 и 8 имеют по две ветви, размеры которых равны 1 и 14. К вершине 7 подходят четыре ветви размером 1, 2, 2 и 10. Таким образом, ее вес . Аналогично вычисляются веса других вершин: , , . Минимальный вес вершин равен 8, следовательно, центроид дерева образуют две вершины с таким весом: 11 и 15.