Барицентр дерева

Определение:

Барицентром дерева (англ. Tree barycenter) называется вершина [math] x [/math], у которой величина [math]d(x) = \sum\limits_v dist(x, v) [/math] минимальна, где [math] dist(x, v) -[/math] расстояние между вершинами [math] x [/math] и [math] v [/math] в рёбрах.

Основные свойства

Лемма:

Пусть вершины [math] y, z -[/math] соседи вершины [math] x [/math]. Тогда [math] 2d(x) \lt d(y) + d(z) [/math].

Доказательство:

[math]\triangleright[/math]

Подвесим дерево за вершину [math] x [/math]. Тогда дерево можно представить в виде объединения трёх непересекающихся множеств: [math] Y, Z [/math] (поддеревья с корнем в вершинах [math] y, z [/math] соответственно) и [math] X - [/math] остальных вершин (заметим, что все эти множества не пустые, так как содержат вершины [math] y, z, x [/math] соответственно). Найдём [math] d(x) [/math]: [math] d(x) = d(y) + |Y| - |Z| - |X| [/math]. Это верно, так как все вершины из множества [math] Y [/math] находятся от [math] x [/math] на одно ребро дальше, чем от [math] y [/math], а вершины из множеств [math] Z, X [/math] наоборот. Аналогично [math] d(x) = d(z) + |Z| - |Y| - |X| [/math]. Сложим эти уравнения и получим: [math] 2d(x) = d(y) + d(z) - 2|X| [/math]. При этом [math] |X| \gt 0 [/math]. Таким образом, [math] 2d(x) \lt d(y) + d(z) [/math].

[math]\triangleleft[/math]

Лемма (о выпуклости [math] d(x) [/math]):

Функция [math] d(x) [/math] из определения выпукла на любом пути дерева

Теорема (о числе барицентров):

В дереве не более [math] 2 [/math] барицентов

Определение:

Центром дерева (англ. Tree center) называется вершина [math] x [/math], для которой величина [math] \max\limits_v dist(x, v) [/math] минимальна.

Теорема:

Для любого числа [math] k [/math] существует дерево, в котором расстояние между центром и барицентром вершины не меньше [math] k [/math]