Изменения

Рассмотрим корень дерева <math>(r)</math>. Положим изначально <math>v = r</math>. Изначально <math>|subtree(v)| = n</math>. Среди всех детей <math>v</math> выберем вершину <math>u</math> с максимальным размером поддерева. Если <math>v</math> - не центроид, то положим <math>v = u</math> и продолжим выбор нового u, иначе - остановимся. Докажем, что мы в какой-то момент остановимся. Пусть в призвольный момент времени <math>v</math> - не центроид и размер её наддерева меньше <math>\frac{n}{2}</math>, значит максимальное поддерево имеет размер больше чем <math>\frac{n}{2}</math>, т.е. <math>|subtree(u)| > \frac{n}{2}</math>, а значит размер "наддерева" вершины <math>u</math> равен <tex>n - |subtree(u)| < \frac{n}{2}</tex>. При этом теперь размер любого поддерева, на которое распадется дерево t при удалении вершины <math>u</math> не превосходит <math>|subtree(u)| - 1</math>, т.к. наддерево имеет размер меньше, чем поддерево <math>u</math>, а любое поддерево вершины <math>u</math> имеет хотя бы на <math>1</math> вершину меньше (сама вершина <math>u</math>). По индукции получаем, что в любой момент времени размер наддерева вершины v меньше <math>\frac{n}{2}</math>, значит мы будем спускаться только вниз по дереву <math>t</math>, и при переходе к вершине <math>u</math> - сыну <math>v</math> размер максимального поддерева уменьшится как минимум на <math>1</math>. Значит не более чем за <math>n</math> шагов наши действия прекратятся и мы окажемся в центроиде дерева <math>t</math>, ч.т.д. Итак, мы конструктивно доказали существование центроида и привели линейный относительно размера дерева алгоритм его нахождения.