图半径

图半径（graph radius）是在图中选择一个顶点作为中心时，能达到的最小“到最远顶点的距离”。对有限、非空、连通的无向无权图，顶点 $v$ 的离心率为 $\epsilon (v)=\underset{u}{max}d(v,u)$，图半径定义为 $$\mathrm{rad}(G)=\underset{v\in V(G)}{min}\epsilon (v).$$ 取得最小值的全部顶点组成图的中心。这里候选中心只能选顶点，不能任意选在边的中点；它与连续路网中的设施选址模型有不同的可选范围。

在五顶点路径 $a-b-c-d-e$ 中，选 $a$ 为中心时最远要走四步；选 $b$ 要走三步；选 $c$ 只需两步。因此半径为二，中心是 $\{c\}$。

下方数字是到最远顶点的距离。圈出的c使这个最坏距离最小。

先取最远，再选择中心

半径的两个极值次序描述两项不同决策。固定中心 $v$ 后，最远目标 $u$ 使距离最大；随后在所有候选 $v$ 中选择这个最大距离最小的一个： $$\mathrm{rad}(G)=\underset{v}{min}\underset{u}{max}d(v,u).$$ 把内外极值交换并不能得到同一含义。例如若先对每个目标 $u$ 选距离它最近的顶点 $v$，总能直接选 $v=u$，得到零；这不是一个同时服务所有目标的中心。

主例各离心率为 $4,3,2,3,4$，最小值为二，最大值为四；后者是图直径。两个概念使用同一组数值，只在外层分别取最小和最大。

半径与直径的两倍界

定理。 对有限、非空、连通无向图，若半径为 $r$、直径为 $D$，则 $$r\le D\le 2r.$$

证明。 每个离心率都不超过全部离心率的最大值 $D$，所以它们的最小值 $r\le D$。再取一个中心 $c$。对任意两点 $u,v$，先从 $u$ 到 $c$ 再到 $v$ 给出一条可能重复顶点的路线，最短距离不会更大，因此三角不等式给出 $$d(u,v)\le d(u,c)+d(c,v)\le r+r=2r.$$ 对全部 $u,v$ 取最大值，就有 $D\le 2r$。证明对单点图也成立，此时两个数均为零。

主例满足 $D=4=2r$，达到右侧等号。五顶点环中每个顶点到最远点都为二，所以 $r=D=2$，达到左侧等号。因此不能总把半径定义为直径除以二；“半径”这一名称在图度量中只保证上述界。

中心不由度数单独决定

在四顶点路径 $a-b-c-d$ 中，离心率为 $3,2,2,3$，中心是 $\{b,c\}$，所以中心可能不唯一。若允许选边中点，最优位置在边 $bc$ 中间，最坏距离会是 $3/2$；本文的顶点中心只能取得二。

最大度顶点也不一定是中心。考虑路径 $v_0-v_1-\cdots -v_6$，再给 $v_0$ 接两片叶子 $x,y$。顶点 $v_0$ 度为三，是唯一最大度顶点，但它到 $v_6$ 的距离为六。顶点 $v_2$ 到 $v_6$ 为四，到 $x,y$ 为三，其离心率为四；顶点 $v_3$ 到叶子为四，到 $v_6$ 为三，离心率也为四。直径由 $x$ 到 $v_6$ 为七，上述两倍界使半径至少为四，故中心为 $\{v_2,v_3\}$、半径四。局部邻居多并不保证全图最远距离小。

变式与应用中的目标差异

变式。 给主例的五顶点路径增加边 $ae$。新图是五环，全部顶点离心率都为二，所以半径仍为二，但中心从一个顶点扩大成全部五点。距离缩短未必使半径严格下降，也可能只增加最优解数量。

若把边看作等长通道、顶点看作可建服务点，半径对应最小化最坏通达距离。若目标是所有点距离的总和最小，则得到图的中位点问题；若按人数或需求加权，又是不同优化。中心、度中心性和平均距离最小点不能仅凭名称相近而混用。

对非连通图，采用不可达距离为无穷的约定时，每个顶点都存在不可达目标，半径也为无穷。应用中常按分量各求中心，但应明确目标服务范围已缩小到分量。有向图若不强连通，还须区分向外离心率和向内离心率，不能直接使用无向图中的对称距离证明。