图的距离与离心率参数 图论中，图的距离与离心率参数用于量化图中顶点之间的“远近”关系，是刻画图结构特征的重要工具。以下从基本定义出发，逐步展开相关概念。 1. 顶点间的距离 定义 ：对于连通图 \( G = (V, E) \)，顶点 \( u \) 和 \( v \) 之间的距离 \( d(u, v) \) 是连接 \( u \) 和 \( v \) 的最短路径的边数。若图不连通且 \( u, v \) 属于不同连通分支，则距离定义为无穷大。 性质 ： 非负性：\( d(u, v) \geq 0 \)，且 \( d(u, v) = 0 \) 当且仅当 \( u = v \)。 对称性：\( d(u, v) = d(v, u) \)。 三角不等式：对任意顶点 \( u, v, w \)，有 \( d(u, v) \leq d(u, w) + d(w, v) \)。 示例 ：在路径图 \( P_ 4 \)（顶点依次为 \( a-b-c-d \)）中，\( d(a, c) = 2 \)，\( d(a, d) = 3 \)。 2. 图的直径与半径 离心率 ：顶点 \( v \) 的离心率 \( e(v) \) 是 \( v \) 到其他所有顶点的最大距离，即 \( e(v) = \max_ {u \in V} d(u, v) \)。 直径 ：图 \( G \) 的直径 \( \text{diam}(G) \) 是所有顶点离心率的最大值，即 \( \text{diam}(G) = \max_ {v \in V} e(v) \)，表示图中任意两顶点间距离的上界。 半径 ：图 \( G \) 的半径 \( \text{rad}(G) \) 是所有顶点离心率的最小值，即 \( \text{rad}(G) = \min_ {v \in V} e(v) \)，表示图中存在一个顶点到其他顶点的最大距离的最小值。 关系 ：对任意连通图，\( \text{rad}(G) \leq \text{diam}(G) \leq 2 \cdot \text{rad}(G) \)。 示例 ：在圈图 \( C_ 6 \) 中，每个顶点的离心率为 3，故直径和半径均为 3；在星图 \( K_ {1,3} \) 中，中心顶点离心率为 1，叶子顶点离心率为 2，故半径为 1，直径为 2。 3. 中心与边界顶点 中心顶点 ：离心率等于半径的顶点称为中心顶点，所有中心顶点构成的集合称为图的中心。 边界顶点 ：离心率等于直径的顶点称为边界顶点。 应用 ：中心顶点在网络设计中常作为优化节点（如医院、服务器选址），因其到其他节点的最坏情况距离最小。 示例 ：树图中，中心可能是一个顶点或两个相邻顶点（通过反复删除叶子顶点可找到中心）。 4. 平均距离与Wiener指数 平均距离 ：图中所有无序顶点对距离的平均值，记为 \( \bar{d}(G) = \frac{1}{\binom{n}{2}} \sum_ {u < v} d(u, v) \)，反映图的整体紧凑程度。 Wiener指数 ：所有无序顶点对距离之和，即 \( W(G) = \sum_ {u < v} d(u, v) \)，在化学图论中用于分子结构分析。 示例 ：完全图 \( K_ n \) 的任意两顶点距离为 1，故 \( W(K_ n) = \binom{n}{2} \)。 5. 距离相关参数的应用 网络分析 ：直径小（小世界现象）且平均距离短的网络具有高效信息传递能力。 图嵌入 ：通过控制直径和半径，可优化图在几何空间中的布局。 算法设计 ：广度优先搜索（BFS）的时间复杂度与图的直径相关，因BFS需遍历从起点到最远顶点的路径。 总结 ：图的距离与离心率参数通过局部（顶点对距离）和全局（直径、半径）两个层面揭示图的结构特性，其理论在社交网络、生物信息学及算法优化中具有广泛应用。