图的树图与中心 首先，我们从“树”这个你已经熟悉的结构出发。树是一种无环的连通图。而“树的中心”是树中一类特殊的顶点集合。理解中心需要先了解两个基本概念：离心率和半径。 离心率与半径 ： 对于树（或任意图）中的一个顶点 \(v\)，其 离心率 \(e(v)\) 定义为从 \(v\) 出发到图中所有其他顶点的距离的最大值。这里的“距离”是指两个顶点之间最短路径的边数。 一棵树的 半径 \(r\) 是其所有顶点离心率的最小值，即 \(r = \min_ {v \in V} e(v)\)。 树的中心 ： 树的 中心 定义为所有离心率等于该树半径的顶点集合。也就是说，中心顶点是树中“最居中”的点，它到最远顶点的距离达到了全局最小。 计算中心的方法 ：一个经典算法是重复“剥离”所有叶子节点（度为1的顶点）及其相连的边。每次剥离一层叶子，直到剩下一个顶点或两个相邻的顶点。最后剩下的顶点就是树的中心。可以证明，这个过程的迭代次数等于树的半径，最终剩下的顶点正好是中心。 性质 ：一棵树的中心要么包含一个顶点，要么包含两个相邻的顶点。中心顶点位于树的所有最长路径（直径）的中点位置。 接下来，我们引入“树图”的概念，它是从一个给定的树派生出来的另一种图结构。 树图的定义 ： 给定一棵树 \(T\)，它的 树图 （也称为“树的图”或“clique tree”）\(Tree(T)\) 是一个以 \(T\) 中所有顶点为顶点的新图。 在树图 \(Tree(T)\) 中，两个顶点（对应原树 \(T\) 的两个顶点）是相邻的，当且仅当在原树 \(T\) 中，连接这两个顶点的 唯一路径 上的所有顶点，诱导出的子图是 连通的 。一个等价的、更常用的表述是：在树图 \(Tree(T)\) 中，两个顶点相邻当且仅当它们在原树 \(T\) 中的距离为1， 或者 它们之间的距离为2且中间那个顶点（即它们唯一的公共邻居）的度数恰好为2。 更直观但不完全严谨的理解是：树图通过“缩短”原树中那些度数为2的顶点所在路径，将原树“压缩”成一个可能边更密集的图。原树的每条边在树图中通常仍保留，同时一些距离为2的顶点对之间也会新增边。 树图的性质与例子 ： 如果原树 \(T\) 是一条路径（所有内部顶点度为2），那么它的树图 \(Tree(T)\) 仍然是一条路径，且长度是原路径长度的一半（向下取整）。 如果原树 \(T\) 是一个星形（一个中心顶点连接多个叶子），那么它的树图 \(Tree(T)\) 是一个完全图（因为所有叶子之间在原树中距离为2，且公共邻居中心顶点的度数大于2，但根据严格定义，星形树的树图实际上是一个“块图”，中心与每个叶子相邻，但叶子之间不相邻——这里需要纠正：根据标准定义，星形树的树图中，叶子之间并不直接相连。更准确的例子是，对于一条长度为3的路径A-B-C-D，顶点A和C的距离为2，且中间点B的度数为2，所以A和C在树图中相邻）。 树图本身不一定是树，它可能包含环（三角形）。 树图的概念与“线图”有相似之处，但它是基于顶点和路径定义的，而线图是基于边定义的。 树图与中心的联系 ： 树图的概念为研究原树的结构提供了一个不同的视角。有趣的是，原树 \(T\) 的 中心 顶点，在树图 \(Tree(T)\) 中通常扮演着重要角色。例如，在一些树图中，原树的中心顶点可能对应于树图中的“中心”或关键顶点。研究树图的性质，可以帮助我们从另一个维度理解原树的对称性、稳定性和其他度量属性。 此外，通过递归地构造树图（即对树 \(T\) 构造树图 \(Tree(T)\)，再对 \(Tree(T)\) 构造树图 \(Tree(Tree(T))\)，如此往复），可以发现一个有趣的现象：这个序列最终会稳定到一个固定图，这个固定图很可能就是原树中心的完全图（单个顶点或一条边）。这从一个侧面反映了“中心”是树的一种稳定不变的内核。 总结来说， 树的中心 是树内部一个基于距离的核心顶点集，而 树图 是从一棵树衍生出的一种图，其边反映了原树中特定结构的路径。将两者结合研究，可以揭示树结构的层次性、稳定性和核心所在。