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

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

Барицентром дерева (англ. 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]\triangleright[/math]

Признак непрерывной строго выпуклой функции : [math] 2f(\displaystyle \frac{x+y}{2}) \lt f(x) + f (y) [/math]. Функция [math] d(x) [/math], вообще говоря, не является непрерывной, но её можно доопределить так, чтобы на интервале [math] (a, b) [/math], где [math] a, b \in \mathbb {N} [/math] она соединяла значения [math] d(a) [/math] и [math] d(b) [/math] отрезком. Для доказательства непрерывности нам интересна только середина этого отрезка, то есть [math] \displaystyle \frac{a+b}{2} [/math]. В ней функция будет, очевидно, принимать значение [math] \displaystyle \frac{d(a)+d(b)}{2} [/math]. Докажем, что признак строго выпуклой функции выполняется. Есть два случая: когда расстояние между [math] x, y [/math] четное и нечетное. Докажем первый случай, второй доказывается аналогично. Пусть в пути от [math] x [/math] до [math] y [/math], кроме них есть только вершина [math] z [/math]. Тогда по предыдущей лемме неравенство очевидно. Пусть есть другие вершины, тогда их не меньше двух, так как [math] dist(x, y) [/math] четно. Рассмотрим тогда в этом пути вершины, которые находятся от [math] z [/math] на расстоянии [math] 2 [/math] (пусть они идут в порядке: [math] a b z c d [/math]), и докажем, что неравенство всё ещё сохраняется. [math] 4d(z) \lt 2d(b) + 2d(c) \lt d(a) + d(z) + d(z) + d (b) \Rightarrow 2d(z) \lt d(a) + d (b)[/math]. Так будем увеличивать расстояние от [math] z [/math] и придём к вершинам [math] x, y [/math], сохраняя инвариант.

[math]\triangleleft[/math]

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

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

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

[math]\triangleright[/math]

Пусть в дереве есть хотя бы [math] 3 [/math] барицентра: [math] a, b, c [/math]. Тогда рассмотрим путь, начинающийся в [math] a [/math] и заканчивающийся в [math] b [/math]. Так как [math] d(a) = d(b) = d_{min} [/math], и функция [math] d(x) [/math] строго выпукла, вершины [math] a, b [/math] являются соседями. В противном случае, или в этом пути есть вершина [math] v: d(v) \lt d_{min} [/math], или для всех вершин [math] u [/math] в пути [math] d(u) = d_{min} [/math]. Первое предположение противоречит тому, что [math] a, b \ - [/math] барицентры, а второе [math] - [/math] тому, что функция [math] d(x) [/math] строго выпукла. Таким образом, вершины [math] a, b [/math] являются соседями. Аналогично доказывается, что вершины [math] b, c [/math] и [math] a, c \ -[/math] соседи. Но в таком случае в дереве образовался цикл, что противоречит определению дерева. Таким образом, более [math] 2 [/math] барицентров в дереве быть не может.

[math]\triangleleft[/math]

Центр дерева

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

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

Теорема:

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

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

[math]\triangleright[/math]

Рассмотрим дерево, построенное следующим образом: к вершине дерева [math] x [/math] проводим [math] n + 1 [/math] ребро, [math] n [/math] из которых проведено в листья дерева, а одно ребро продолжим достраивать как бамбук, расстояние в котором от листа до [math] x [/math] назовём числом [math] l [/math]. Докажем, что существуют такие [math] m, l [/math], что расстояние между центром и барицентром не меньше [math] k [/math]. Назовём лист бамбука вершиной [math] a [/math], а центр дерева [math]- \ c [/math]. Тогда [math] dist(a, c) = \displaystyle \frac{l+1}{2} [/math]. Для удобства будем считать, что центр один, для этого будем рассматривать только нечётные [math] l. [/math] Теперь будем искать, какое [math] n [/math] стоит выбрать, чтобы барицентром оказалась вершина [math] x [/math]. Найдём [math] d(x) [/math]: [math] d(x) = n + 1 + \dots + l = n + \displaystyle \frac{(l+1)l}{2} [/math]. Рассмотрим вершину [math] v \neq x [/math]. Очевидно, что [math] d(v) \gt 2(n-1) [/math], так как все вершины, кроме [math] x [/math] удалены хотя бы на расстояние [math] 2 [/math] от [math] n-1 [/math] вершины. В таком случае, [math] d(x) \lt d(v) \Leftrightarrow n \gt \displaystyle \frac{(l+1)l}{2} + 2 [/math]. Мы получили, что [math] dist(c, x) = \displaystyle \frac{l-1}{2} [/math], и [math] x [/math] является барицентром. Найдём такие [math] l ,[/math] что [math] \displaystyle \frac{l-1}{2} \geqslant k[/math]. Для этого можно взять любое [math] l \geqslant 2k + 1 [/math]. Таким образом, искомые [math] m, l [/math] существуют.

[math]\triangleleft[/math]

См. также

• Выпуклые функции
• Дерево, эквивалентные определения

Источники информации

• Andrew Beveridge — Centers for Random Walks on Trees