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