树的中心

树的中心是一个离心率最小的顶点。树G中顶点X的离心率是顶点X与树中任何其他顶点之间的最大距离。最大离心率是树的直径。如果树只有一个中心，则称为中心树；如果树有多个中心，则称为双中心树。每棵树要么是中心树，要么是双中心树。

查找树的中心和双中心的算法

步骤1 - 从给定的树中移除所有度为1的顶点及其关联边。

步骤2 - 重复步骤1，直到剩下单个顶点或由一条边连接的两个顶点。如果剩下单个顶点，则它是树的中心；如果剩下由一条边连接的两个顶点，则它们是树的双中心。

问题1

找出以下树的中心/双中心：

解答

首先，我们将移除所有度为1的顶点及其关联边，得到以下树：

再次，我们将移除所有度为1的顶点及其关联边，得到以下树：

最终我们得到单个顶点'c'，算法停止。由于只有一个顶点，这棵树只有一个中心'c'，这棵树是中心树。

问题2

找出以下树的中心/双中心：

解答

首先，我们将移除所有度为1的顶点及其关联边，得到以下树：

再次，我们将移除所有度为1的顶点及其关联边，得到以下树：

最终，我们剩下两个顶点'c'和'd'，因此算法停止。由于剩下两个由一条边连接的顶点，这棵树的双中心是'cd'，这棵树是双中心树。

Mahesh Parahar

更新于：2019年8月23日

4K+ 浏览量

开启你的职业生涯

完成课程获得认证

开始学习