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

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

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

Применение

Метод барицентров (англ. barycenter heuristic) используется в одном из этапов визуализации ориентированных ациклических графов. Сначала в графе находятся множества вершин [math] - [/math] уровни (англ. layers). Уровни ищутся так, чтобы рёбра между вершинами разных уровней шли в неубывающем или невозрастающем направлении по вертикали или горизонтали. После того, как найдены уровни, нужно уменьшить число пересечений между рёбрами. Одна из используемых эвристик и есть [math] - [/math] метод барицентров. Его суть заключается в том, чтобы координаты вершины определялись как среднее арифметическое координат смежных вершин предыдущего уровня. Важной особенностью этого метода является то, что если возможно построить граф без пересечений рёбер, то метод барицентров построит его без них. А в противном случае пересечений будет не более, чем в [math] 3 [/math] раза больше, чем минимальное число пересечений.

См. также

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

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

• Построение изображений ациклических ориентированных графов