Барицентр дерева — различия между версиями
Anverk (обсуждение | вклад) (→Центр дерева) |
Anverk (обсуждение | вклад) (→Центр дерева) |
||
| Строка 41: | Строка 41: | ||
}} | }} | ||
| − | '''Замечание''': доказательство существования такого <tex> n </tex>, чтобы вершина <tex> x </tex> была барицентром можно было проводить и | + | '''Замечание''': доказательство существования такого <tex> n </tex>, чтобы вершина <tex> x </tex> была барицентром можно было проводить и менее строго, ведь очевидно, что при больших <tex> n </tex> у барицентра должно быть минимальное расстояние до <tex> n </tex> листьев. И такой вершиной и является <tex> x </tex>. |
== Примечания == | == Примечания == | ||
Версия 21:15, 24 декабря 2017
| Определение: |
| Барицентром дерева (англ. tree barycenter) называется вершина , у которой величина минимальна, где расстояние между вершинами и . |
Содержание
Основные свойства
| Лемма: |
Пусть существуют вершины соседи вершины . Тогда . |
| Доказательство: |
|
Подвесим дерево за вершину . Тогда дерево можно представить в виде объединения трёх непересекающихся множеств: поддеревья с корнями в вершинах соответственно и . Заметим, что все эти множества не пустые, так как содержат вершины соответственно. Найдём . Простой путь до вершины из всегда единственный и представим следующим образом: . Значит, все вершины из множества находятся от на одно ребро дальше, чем от . Аналогично все вершины из множеств ближе на одно ребро к , чем к . Тогда . Аналогично . Сложим эти уравнения и получим: . При этом . Таким образом, . |
| Лемма: |
Функция строго выпукла на любом пути в дереве. |
| Доказательство: |
|
Признак непрерывной строго выпуклой функции [1]: . Функция не является непрерывной при , но её можно доопределить так, чтобы на интервале , где она соединяла значения и параболой (или любой другой выпуклой функцией). Это можно сделать, потому что для функции на пути в дереве рассматриваются только натуральные аргументы. Для доказательства выпуклости нам интересна только точка параболы, абсцисса которой равна . В ней функция будет принимать значение, строго меньшее . Докажем, что признак строгой выпуклости функции выполняется. Есть два случая: когда расстояние между четное и нечетное. Докажем первый случай, второй доказывается аналогично. Пусть в пути от до , кроме них есть только вершина . Тогда по предыдущей лемме неравенство очевидно. Пусть есть другие вершины, кроме , тогда их не меньше двух, так как четно. Рассмотрим тогда в этом пути вершины, которые находятся от на расстоянии не больше (пусть они идут в порядке: ), и докажем, что неравенство всё ещё сохраняется. . Так будем увеличивать расстояние от и придём к вершинам , сохраняя инвариант. |
| Теорема (о числе барицентров): |
В дереве не более барицентов |
| Доказательство: |
| Пусть в дереве есть хотя бы барицентра: . Тогда рассмотрим путь, начинающийся в и заканчивающийся в . Так как , и функция строго выпукла, вершины являются соседями. В противном случае, или в этом пути есть вершина , или для всех вершин в пути . Первое предположение противоречит тому, что барицентры, а второе тому, что функция строго выпукла. Таким образом, вершины являются соседями. Аналогично доказывается, что вершины и соседи. Но в таком случае в дереве образовался цикл, что противоречит определению дерева. Таким образом, более барицентров в дереве быть не может. |
Центр дерева
| Определение: |
| Центром дерева (англ. Tree center) называется вершина , для которой величина минимальна. |
| Теорема: |
Для любого числа существует дерево, в котором расстояние между центром и барицентром дерева не меньше |
| Доказательство: |
|
Рассмотрим дерево, построенное следующим образом: к вершине дерева подвесим свободных вершин (в дереве они станут листьями) и бамбук, расстояние в котором от листа до назовём числом . Докажем, что существуют такие , что расстояние между центром и барицентром не меньше . Для удобства будем считать, что центр один, для этого будем рассматривать только нечётные Назовём лист бамбука вершиной , а центр дерева . Тогда . Теперь будем искать, какое стоит выбрать, чтобы барицентром оказалась вершина . Найдём : . Рассмотрим вершину . , так как все вершины, кроме удалены хотя бы на расстояние от вершины. В таком случае, . Мы получили, что , и является барицентром. Найдём такие что . Для этого можно взять любое . Таким образом, искомые существуют. |
Замечание: доказательство существования такого , чтобы вершина была барицентром можно было проводить и менее строго, ведь очевидно, что при больших у барицентра должно быть минимальное расстояние до листьев. И такой вершиной и является .
