Изменения
Нет описания правки
{{Лемма
|id = lem1
|statement = Пусть существуют вершины <tex> y, z -</tex> соседи вершины <tex> x </tex>. Тогда <tex> 2d(x) < d(y) + d(z) </tex>.
|proof = Подвесим дерево за вершину <tex> x </tex>. Тогда дерево можно представить в виде объединения трёх непересекающихся множеств: <tex> Y, Z </tex> (поддеревья с корнем в вершинах <tex> y, z </tex> соответственно) и <tex> X - </tex> остальных вершин (заметим, что все эти множества не пустые, так как содержат вершины <tex> y, z, x </tex> соответственно). Найдём <tex> d(x) </tex>:
<tex> d(x) = d(y) + |Y| - |Z| - |X| </tex>. Это верно, так как все вершины из множества <tex> Y </tex> находятся от <tex> x </tex> на одно ребро дальше, чем от <tex> y </tex>, а вершины из множеств <tex> Z, X </tex> наоборот. Аналогично <tex> d(x) = d(z) + |Z| - |Y| - |X| </tex>. Сложим эти уравнения и получим: <tex> 2d(x) = d(y) + d(z) - 2|X| </tex>. При этом <tex> |X| > 0 </tex>. Таким образом, <tex> 2d(x) < d(y) + d(z) </tex>.
{{Лемма
|id = lem2
|about statement = о выпуклости Функция <tex> d(x) </tex>строго выпукла (вниз) на любом пути дерева.|statement proof = Функция Очевидно из характеристического признака строго выпуклой функции: <tex> d2f(\frac{x+y}{2}) < f(x) + f (y) </tex> из определения выпукла на любом пути дерева.
}}
|about = о числе барицентров
|statement= В дереве не более <tex> 2 </tex> барицентов
|proof= Пусть в дереве есть хотя бы <tex> 3 </tex> барицентра: <tex> a, b, c </tex>. Тогда рассмотрим путь, начинающийся в <tex> a </tex> и заканчивающийся в <tex> b </tex>. Так как <tex> d(a) = d(b) = d_{min} </tex>, и функция <tex> d(x) </tex> строго выпукла, вершины <tex> a, b </tex> являются соседями. В противном случае, или в этом пути есть вершина <tex> v: d(v) < d_{min} </tex>, или для всех вершин <tex> u </tex> в пути <tex> d(u) = d_{min} </tex>. Первое предположение противоречит тому, что <tex> a, b \ - </tex> барицентры, а второе <tex> - </tex> тому, что функция <tex> d(x) </tex> строго выпукла. Таким образом, вершины <tex> a, b </tex> являются соседями. Аналогично доказывается, что вершины <tex> b, c </tex> и <tex> a, c \ -</tex> соседи. Но в таком случае в дереве образовался цикл, что противоречит определению дерева. Таким образом, более <tex> 2 </tex> барицентров в дереве быть не может.
}}
{{Определение
{{Теорема
|id = theor2
|statement= Для любого числа <tex> k </tex> существует дерево, в котором расстояние между центром и барицентром вершины дерева не меньше <tex> k </tex>|proof= Рассмотрим дерево, построенное следующим образом: к вершине дерева <tex> x </tex> проводим <tex> n + 1 </tex> ребро, <tex> n </tex> из которых проведено в листья дерева, а одно ребро продолжим достраивать как бамбук, расстояние в котором от листа до <tex> x </tex> назовём числом <tex> l </tex>. Докажем, что существуют такие <tex> m, l </tex>, что расстояние между центром и барицентром не меньше <tex> k </tex>.Назовём лист бамбука вершиной <tex> a </tex>, а центр дерева <tex>- \ c </tex>. Тогда <tex> dist(a, c) = \frac{l+1}{2} </tex>. Для удобства будем считать, что центр один, для этого будем рассматривать только нечётные <tex> l. </tex> Теперь будем искать, какое <tex> n </tex> стоит выбрать, чтобы барицентром оказалась вершина <tex> x </tex>. Найдём <tex> d(x): d(x) = n + 1 + 2 + ... + l = n + \frac{(l+1)l}{2} </tex>. Рассмотрим вершину <tex> v \neq x </tex>. Очевидно, что <tex> d(v) > 2(n-1) </tex>, так как все вершины, кроме <tex> x </tex> удалены хотя бы на расстояние <tex> 2 </tex> от <tex> n-1 </tex> вершины. В таком случае, <tex> d(x) < d(v) \Leftrightarrow n > \frac{(l+1)l}{2} + 2 </tex>. Мы получили, что <tex> dist(c, x) = \frac{l-1}{2} </tex>, и <tex> x </tex> является барицентром. Найдём такие <tex> l ,</tex> что <tex> \frac{l-1}{2} \geq k</tex>. Для этого можно взять любое <tex> l \geq 2k + 1 </tex>. Таким образом, искомые <tex> m, l </tex> существуют, и теорема доказана.
}}
