Барицентр дерева
| Определение: |
| Барицентром дерева (англ. Tree barycenter) называется вершина , у которой величина минимальна, где расстояние между вершинами и в рёбрах. |
Основные свойства
| Лемма: |
Пусть существуют вершины соседи вершины . Тогда . |
| Доказательство: |
|
Подвесим дерево за вершину . Тогда дерево можно представить в виде объединения трёх непересекающихся множеств: (поддеревья с корнем в вершинах соответственно) и остальных вершин (заметим, что все эти множества не пустые, так как содержат вершины соответственно). Найдём : . Это верно, так как все вершины из множества находятся от на одно ребро дальше, чем от , а вершины из множеств наоборот. Аналогично . Сложим эти уравнения и получим: . При этом . Таким образом, . |
| Лемма: |
Функция строго выпукла (вниз) на любом пути дерева. |
| Доказательство: |
|
Признак непрерывной строго выпуклой функции [1]: . Функция , вообще говоря, не является непрерывной, но её можно доопределить так, чтобы на интервале , где она соединяла значения и отрезком. Для доказательства непрерывности нам интересна только середина этого отрезка, то есть . В ней функция будет, очевидно, принимать значение . Докажем, что признак строго выпуклой функции выполняется. Есть два случая: когда расстояние между четное и нечетное. Докажем первый случай, второй доказывается аналогично. Пусть в пути от до , кроме них есть только вершина . Тогда по предыдущей лемме неравенство очевидно. Пусть есть другие вершины, тогда их не меньше двух, так как четно. Рассмотрим тогда в этом пути вершины, которые находятся от на расстоянии (пусть они идут в порядке: ), и докажем, что неравенство всё ещё сохраняется. . Так будем увеличивать расстояние от и придём к вершинам , сохраняя инвариант. |
| Теорема (о числе барицентров): |
В дереве не более барицентов |
| Доказательство: |
| Пусть в дереве есть хотя бы барицентра: . Тогда рассмотрим путь, начинающийся в и заканчивающийся в . Так как , и функция строго выпукла, вершины являются соседями. В противном случае, или в этом пути есть вершина , или для всех вершин в пути . Первое предположение противоречит тому, что барицентры, а второе тому, что функция строго выпукла. Таким образом, вершины являются соседями. Аналогично доказывается, что вершины и соседи. Но в таком случае в дереве образовался цикл, что противоречит определению дерева. Таким образом, более барицентров в дереве быть не может. |
Центр дерева
| Определение: |
| Центром дерева (англ. Tree center) называется вершина , для которой величина минимальна. |
| Теорема: |
Для любого числа существует дерево, в котором расстояние между центром и барицентром дерева не меньше |
| Доказательство: |
|
Рассмотрим дерево, построенное следующим образом: к вершине дерева проводим ребро, из которых проведено в листья дерева, а одно ребро продолжим достраивать как бамбук, расстояние в котором от листа до назовём числом . Докажем, что существуют такие , что расстояние между центром и барицентром не меньше . Назовём лист бамбука вершиной , а центр дерева . Тогда . Для удобства будем считать, что центр один, для этого будем рассматривать только нечётные Теперь будем искать, какое стоит выбрать, чтобы барицентром оказалась вершина . Найдём : . Рассмотрим вершину . Очевидно, что , так как все вершины, кроме удалены хотя бы на расстояние от вершины. В таком случае, . Мы получили, что , и является барицентром. Найдём такие что . Для этого можно взять любое . Таким образом, искомые существуют. |
