树的重心

定义

对于树上每一个顶点,分别计算其所有子树中最大子树的顶点数,当此值最小时,这个顶点即为树的重心

性质

树的重心主要有一下性质:

  • 以树的重心为根,每一子树的大小都不超过整棵树大小的一半。
  • 树中所有顶点到重心的距离和比到其它顶点距离和小,若存在多个重心则到它们的距离一致。
  • 若两棵树相连合成一颗新树,则新树的重心在原树两个重心的路径上。
  • 在树上添加或删除一个叶子,树的重心最多移动到其邻居的位置上。

求解方法

通过深度优先搜索计算每一子树的大小并记录,由$|V_{upper}|=|V_{all}|-|V_{lower}|-1$及定义可求解出重心位置,时间复杂度$O(n)$。

树的直径

定义

树上距离最远两点的距离即称为树的直径

性质

  • 直径的两个端点一定是两个叶子。
  • 距离树上任意顶点最远的顶点一定是直径的某个端点。
  • 对于两颗树,若用一条边将其连接从而构成新树,其直径的两个端点一定为原树四个顶点中的其中两个。
  • 若树存在多条直径,则其交点是这些直径的中点。
  • 在树上添加一个叶子,最多会改变直径中的一个端点。

求解方法

以任意顶点为根,搜索距离其最远的顶点$u$,再从这个顶点出发寻找距离其最远的顶点$v$,$(u,v)$即为树的直径。若树存在多条直径,则只需分别求距离其最远顶点即可。

Last modification:May 17th, 2020 at 11:09 am
博客维护不易,如果你觉得我的文章有用,请随意赞赏