51
правка
Изменения
Нет описания правки
|id = lem2
|statement = Функция <tex> d(x) </tex> строго выпукла (вниз) на любом пути дерева.
|proof = Признак непрерывной строго выпуклой функции <ref>{{Cite web|url = https://ru.wikipedia.org/wiki/Выпуклая_функция|title = Выпуклая функция |author = |date = |publisher = Википедия}}</ref>: <tex> 2f(\displaystyle \frac{x+y}{2}) < f(x) + f (y) </tex>. Функция <tex> d(x) </tex>, вообще говоря, не является непрерывной, но её можно доопределить, чтобы на полуинтервале <tex> [a, b) </tex>, где <tex> a, b \in \mathbb {N} </tex> она принимала значение <tex> d(a) </tex>
}}
Назовём лист бамбука вершиной <tex> a </tex>, а центр дерева <tex>- \ c </tex>. Тогда <tex> dist(a, c) = \displaystyle \frac{l+1}{2} </tex>. Для удобства будем считать, что центр один, для этого будем рассматривать только нечётные <tex> l. </tex> Теперь будем искать, какое <tex> n </tex> стоит выбрать, чтобы барицентром оказалась вершина <tex> x </tex>. Найдём <tex> d(x) </tex>: <tex> d(x) = n + 1 + \dots + l = n + \displaystyle \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 > \displaystyle \frac{(l+1)l}{2} + 2 </tex>. Мы получили, что <tex> dist(c, x) = \displaystyle \frac{l-1}{2} </tex>, и <tex> x </tex> является барицентром. Найдём такие <tex> l ,</tex> что <tex> \displaystyle \frac{l-1}{2} \geqslant k</tex>. Для этого можно взять любое <tex> l \geqslant 2k + 1 </tex>. Таким образом, искомые <tex> m, l </tex> существуют.
}}
== Примечания ==
<references/>
== См. также ==
