51
правка
Изменения
→Основные свойства
|id = lem2
|statement = Функция <tex> d(x) </tex> строго выпукла на любом пути в дереве.
|proof = Признак непрерывной строго выпуклой функции <ref>https://ru.wikipedia.org/wiki/Выпуклая_функция</ref>: <tex> \forall x, y \in \mathbb{R} </tex> выполнено <tex> 2f(\displaystyle \frac{x+y}{2}) < f(x) + f (y) </tex>. Функция Будем называть функцию выпуклой на множестве натуральных чисел, если предыдущее неравенство выполнено для всех <tex> d(x) , y \in \mathbb{N} </tex> не является непрерывной при . Доопределим функцию <tex> d(x \in \mathbb{R} ) </tex>, но её можно доопределить так, чтобы на интервале в точке <tex> (a, b) + \displaystyle \frac{1}{2} </tex>, где <tex> a, b \in \mathbb {N} </tex> она соединяла значения принимала значение, строго меньшее <tex> \displaystyle \frac{d(a) </tex> и <tex> +d(ba+1) }{2} </tex> параболой (или любой другой выпуклой функцией). Это можно нужно сделать, потому что для функции на пути в дереве рассматриваются только натуральные аргументы. Для доказательства выпуклости нам интересна только точка параболы, абсцисса которой равна не всегда <tex> \displaystyle \frac{a+b}{2} </tex>. В ней функция будет принимать значение, строго меньшее <tex> \displaystyle in \fracmathbb{d(a)+d(b)}{2N} </tex>. Докажем, что признак строгой выпуклости такой функции выполняется.
Есть два случая: когда расстояние между <tex> x, y </tex> четное и нечетное. Докажем первый случай, второй доказывается аналогично. Пусть в пути от <tex> x </tex> до <tex> y </tex>, кроме них есть только вершина <tex> z </tex>. Тогда по предыдущей лемме неравенство очевидно. Пусть есть другие вершины, кроме <tex> x, y, z </tex>, тогда их не меньше двух, так как <tex> dist(x, y) </tex> четно. Рассмотрим тогда в этом пути вершины, которые находятся от <tex> z </tex> на расстоянии не больше <tex> 2 </tex> (пусть они идут в порядке: <tex> a b z c d </tex>), и докажем, что неравенство всё ещё сохраняется. <tex> 4d(z) < 2d(b) + 2d(c) < d(a) + d(z) + d(z) + d (b) \Rightarrow 2d(z) < d(a) + d (b)</tex>. Так будем увеличивать расстояние от <tex> z </tex> и придём к вершинам <tex> x, y </tex>, сохраняя инвариант.
}}
