Барицентр дерева
| Определение: |
| Барицентром дерева (англ. tree barycenter) называется вершина , у которой величина минимальна, где расстояние между вершинами и . |
Основные свойства
| Лемма: |
Пусть существуют вершины соседи вершины . Тогда . |
| Доказательство: |
|
Подвесим дерево за вершину . Тогда дерево можно представить в виде объединения трёх непересекающихся множеств: поддеревья с корнями в вершинах соответственно и . Заметим, что все эти множества не пустые, так как содержат вершины соответственно. Найдём . Простой путь до вершины из всегда единственный и представим следующим образом: . Значит, все вершины из множества находятся от на одно ребро дальше, чем от . Аналогично все вершины из множеств ближе на одно ребро к , чем к . Тогда . Аналогично . Сложим эти уравнения и получим: . При этом . Таким образом, . |
| Лемма: |
Функция строго выпукла на любом пути в дереве. |
| Доказательство: |
|
Признак непрерывной строго выпуклой функции [1]: выполнено . Будем называть функцию строго выпуклой на множестве натуральных чисел, если предыдущее неравенство выполнено для всех . Введём функцию , которая по номеру вершины в пути находит саму вершину. В дальнейшем будем считать как для некоторого рассматриваемого пути . Доопределим функцию так, чтобы в точке , где она принимала значение, строго меньшее . Это нужно сделать, потому что не всегда . Докажем, что такая функция строго выпукла на множестве натуральных чисел. Есть два случая: когда расстояние между четное и нечетное. Докажем первый случай, второй доказывается аналогично. Пусть в пути от до , кроме них есть только вершина . Тогда по предыдущей лемме неравенство очевидно. Пусть есть другие вершины, кроме , тогда их не меньше двух, так как четно. Рассмотрим тогда в этом пути вершины, которые находятся от на расстоянии не больше (пусть они идут в порядке: ), и докажем, что неравенство всё ещё сохраняется. . Так будем увеличивать расстояние от и придём к вершинам , сохраняя инвариант. |
| Теорема (о числе барицентров): |
В дереве не более барицентов |
| Доказательство: |
| Пусть в дереве есть хотя бы барицентра: . Тогда рассмотрим путь, начинающийся в и заканчивающийся в . Так как , и функция строго выпукла, вершины являются соседями. В противном случае, или в этом пути есть вершина , или для всех вершин в пути . Первое предположение противоречит тому, что барицентры, а второе тому, что функция строго выпукла. Таким образом, вершины являются соседями. Аналогично доказывается, что вершины и соседи. Но в таком случае в дереве образовался цикл, что противоречит определению дерева. Таким образом, более барицентров в дереве быть не может. |
Центр дерева
| Определение: |
| Центром дерева (англ. Tree center) называется вершина , для которой величина минимальна. |
| Теорема: |
Для любого числа существует дерево, в котором расстояние между центром и барицентром дерева не меньше |
| Доказательство: |
|
Рассмотрим дерево, построенное следующим образом: к вершине дерева подвесим свободных вершин (в дереве они станут листьями) и бамбук, расстояние в котором от листа до назовём числом . Докажем, что существуют такие , что расстояние между центром и барицентром не меньше . Для удобства будем считать, что центр один, для этого будем рассматривать только нечётные Назовём лист бамбука вершиной , а центр дерева . Тогда . Теперь будем искать, какое стоит выбрать, чтобы барицентром оказалась вершина . Найдём : . Рассмотрим вершину . , так как все вершины, кроме удалены хотя бы на расстояние от вершины. В таком случае, . Мы получили, что , и является барицентром. Найдём такие что . Для этого можно взять любое . Таким образом, искомые существуют. |
Замечание: доказательство существования такого , чтобы вершина была барицентром можно было проводить и менее строго, ведь очевидно, что при больших у барицентра должно быть минимальное расстояние до листьев. И такой вершиной и является .
Примечания
См. также
Источники информации
- Melnikov O.. «Exercises in Graph Theory» — «Springer», 2013 г. — 47-48 стр. — ISBN 978-94-017-1514-0
