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