http://neerc.ifmo.ru/wiki/api.php?action=feedcontributions&feedformat=atom&user=91.122.183.19&*Викиконспекты - Вклад участника [ru]2026-06-11T14:10:24ZВклад участникаMediaWiki 1.30.0http://neerc.ifmo.ru/wiki/index.php?title=%D0%91%D0%B0%D1%80%D0%B8%D1%86%D0%B5%D0%BD%D1%82%D1%80_%D0%B4%D0%B5%D1%80%D0%B5%D0%B2%D0%B0&diff=62763Барицентр дерева2017-12-17T22:51:49Z<p>91.122.183.19: </p>
<hr />
<div>{{Определение<br />
|id = tree_barycenter<br />
|definition = '''Барицентром дерева''' (англ. ''Tree barycenter'') называется вершина <tex> x </tex>, у которой величина <tex>d(x) = \sum\limits_v dist(x, v) </tex> минимальна, где <tex> dist(x, v) -</tex> расстояние между вершинами <tex> x </tex> и <tex> v </tex> в рёбрах.<br />
}}<br />
<br />
== Основные свойства ==<br />
<br />
{{Лемма<br />
|id = lem1<br />
|statement = Пусть вершины <tex> y, z -</tex> соседи вершины <tex> x </tex>. Тогда <tex> 2d(x) < d(y) + d(z) </tex>.<br />
|proof = Подвесим дерево за вершину <tex> x </tex>. Тогда дерево можно представить в виде объединения трёх непересекающихся множеств: <tex> Y, Z </tex> (поддеревья с корнем в вершинах <tex> y, z </tex> соответственно) и <tex> X - </tex> остальных вершин (заметим, что все эти множества не пустые, так как содержат вершины <tex> y, z, x </tex> соответственно). Найдём <tex> d(x) </tex>:<br />
<tex> d(x) = d(y) + |Y| - |Z| - |X| </tex>. Это верно, так как все вершины из множества <tex> Y </tex> находятся от <tex> x </tex> на одно ребро дальше, чем от <tex> y </tex>, а вершины из множеств <tex> Z, X </tex> наоборот. Аналогично <tex> d(x) = d(z) + |Z| - |Y| - |X| </tex>. Сложим эти уравнения и получим: <tex> 2d(x) = d(y) + d(z) - 2|X| </tex>. При этом <tex> |X| > 0 </tex>. Таким образом, <tex> 2d(x) < d(y) + d(z) </tex>.<br />
}}<br />
<br />
{{Лемма<br />
|id = lem2<br />
|about = о выпуклости <tex> d(x) </tex><br />
|statement = Функция <tex> d(x) </tex> из определения выпукла на любом пути дерева<br />
}}<br />
<br />
{{Теорема<br />
|id = theor1<br />
|about = о числе барицентров<br />
|statement= В дереве не более <tex> 2 </tex> барицентов<br />
|proof= <br />
}}<br />
<br />
{{Определение<br />
|id = tree_center<br />
|definition = '''Центром дерева''' (англ. ''Tree center'') называется вершина <tex> x </tex>, для которой величина <tex> \max\limits_v dist(x, v) </tex> минимальна.<br />
}}<br />
<br />
{{Теорема<br />
|id = theor2<br />
|statement= Для любого числа <tex> k </tex> существует дерево, в котором расстояние между центром и барицентром вершины не меньше <tex> k </tex><br />
|proof= <br />
}}</div>91.122.183.19