The nature and proof of the center of gravity of [mathematics] tree

Definition ：

There are many equivalent definitions of the center of gravity of a tree , We use this definition ： The center of gravity of the tree refers to , This point is the point that minimizes the number of nodes of the largest subtree . Let the number of nodes of the tree be $n$.

nature 1：

spot $u$ Is the center of gravity of the tree , If and only if the number of nodes of its largest subtree is less than or equal to $\lfloor n/2\rfloor$.
prove ：
Proband $\Rightarrow$. If $u$ Center of gravity , But the number of nodes of its largest subtree is greater than $\lfloor n/2\rfloor$, Then consider the root of the subtree $v$. set up $s[x]$ by $x$ Size of subtree , that $s[v]>\lfloor n/2\rfloor ,n-s[v]<\lfloor n/2\rfloor <s[v]$, So as to $v$ For the root of a tree , The size of its largest subtree must be less than $s[v]$ Of , And $u$ For the center of gravity contradiction .
Re evidence $\Leftarrow$. If $u$ The number of nodes of the largest subtree of is less than or equal to $\lfloor n/2\rfloor$, but $u$ Not the center of gravity , hypothesis $v\ne u$ but $v$ Center of gravity , consider $v$ Including $u$ That little tree of mine , from $u$ From the perspective of , The number of nodes of its largest subtree is less than or equal to $\lfloor n/2\rfloor$, So get rid of $u$ To $v$ That path $u$ The sum of nodes of the remaining subtrees is greater than or equal to $n-1-\lfloor n/2\rfloor$, thus $v$ Including $u$ The size of the subtree of is greater than or equal to $n-\lfloor n/2\rfloor$. If $n$ It's odd , be $n-\lfloor n/2\rfloor >\lfloor n/2\rfloor$, And $v$ It's the contradiction of focus . If $n$ It's even , Only in $u$ and $v$ The number of nodes of the largest subtree of is equal to $n/2$ also $u$ And $v$ There is no contradiction when connecting , At this time, these two points are the center of gravity . The above proof proves that there is no other center of gravity in this situation .

inference ：

Only when the number of nodes is not unique can there be two barycenters , And the center of gravity is at most two . When the center of gravity has two , They are adjacent nodes . The number of nodes of the largest subtree of the barycenter is determined .

nature 2：

set up $d[u]$ Is all points and $u$ The sum of the distances （ Let's say that the edge weights are $1$）, So if and only if $u$ When the center of gravity $d[u]$ Minimum .
prove ： Proband $\Leftarrow$. hypothesis $v$ bring $d[v]$ Minimum , also $v$ Not the center of gravity , that $v$ One subtree is larger than $\lfloor n/2\rfloor$ Of , If you will $v$ Move a step towards the sub tree , be $d[v]$ It's bound to get smaller , contradiction . So if $d[v]$ Minimum , that $v$ It must be the center of gravity .
Re evidence $\Rightarrow$. If $d[u]$ Not the smallest , There is another point $v$ bring $d[v]$ Minimum , Then by nature $1$,$v$ Center of gravity , but $u$ It's also the center of gravity , If the center of gravity is unique , This is a contradiction . If the center of gravity is not unique , Infer from the above ,$n$ It's even ,$u$ And $v$ The number of nodes of the largest subtree of adjacent and two points is equal to $n/2$, that $d[u]=d[v]$, Also contradictory . So if $u$ Center of gravity ,$d[u]$ Must be the smallest .