Барицентр дерева — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Новая страница: «{{Определение |id = tree_barycenter |definition = '''Барицентром дерева''' (англ. ''Tree barycenter'') называется вер...»)
(нет различий)

Версия 22:08, 17 декабря 2017

Определение:
Барицентром дерева (англ. Tree barycenter) называется вершина [math] x [/math], у которой величина [math] \sum\limits_v dist(x, v) [/math] минимальна, где [math] dist(x, v) -[/math] расстояние между вершинами [math] x [/math] и [math] v [/math] в рёбрах.


Основные свойства

Теорема (о числе барицентров):
В дереве не более [math] k [/math] барицентов


Определение:
Центром дерева (англ. Tree center) называется вершина [math] x [/math], для которой величина [math] \max\limits_v max(dist(x, v)) [/math] минимальна.


Теорема:
Для любого [math] k [/math] существует дерево, в котором расстояние между центром и барицентром вершины не меньше [math] k [/math]