图直径

图直径（graph diameter）是图中两点之间最短路径距离的最大值。对有限、非空、连通的无向无权图 $G$，若 $d(u,v)$ 表示从 $u$ 到 $v$ 所需最少边数，则 $$\mathrm{diam}(G)=\underset{u,v\in V(G)}{max}d(u,v).$$ 这里先对每对顶点寻找最短路线，再在这些最短距离中取最大值；它与“图中最长简单路径的长度”是不同的量。

例如，五顶点路径 $a-b-c-d-e$ 中，从 $a$ 到 $e$ 需要四条边，其他顶点对都不需要超过四条边，所以直径为四。

路径图中没有绕行或捷径，因此a到e的唯一四边路径也是最短路径。

从距离表计算离心率

固定一个顶点 $v$，它到其他顶点最远的距离称为离心率，记为 $\epsilon (v)=\underset{u}{max}d(v,u)$。于是直径也可写为 $\underset{v}{max}\epsilon (v)$。对主例，按 $a,b,c,d,e$ 排序，距离表为

起点／终点	a	b	c	d	e	离心率
a	0	1	2	3	4	4
b	1	0	1	2	3	3
c	2	1	0	1	2	2
d	3	2	1	0	1	3
e	4	3	2	1	0	4

每一行先取最大值得到 $(4,3,2,3,4)$，再取最大值得四。任意达到直径的顶点对称为直径端点对，未必唯一。图的半径对这些离心率取最小值，故本例半径为二。

最短路径不重复顶点

若一条最短游走重复经过某个顶点，重复的两次出现之间形成闭合段；删除该段仍连接相同起终点，却减少边数，违背最短性。因此最短路线可以取为不重复顶点的简单路径。若图有 $n$ 个顶点，这样的路径至多有 $n-1$ 条边，所以对 $n\ge 2$ 的连通简单图， $$1\le \mathrm{diam}(G)\le n-1.$$ 单点图的直径为零。上界由路径图 $P_n$ 达到；下界由完全图 $K_n$ 达到，因为每两个不同顶点都有直接边。

该证明依赖无权边数距离，或至少依赖边长非负时可删除闭合段。含负权边及负环的最短路模型可能没有有限最短距离，不能直接套用本篇定义。

树的直径端点是叶子

命题。 对至少两个顶点的树，任何达到直径的两端点都是度为一的叶子。

证明。 设直径路径为 $v_0,v_1,\dots ,v_D$。若端点 $v_0$ 另有一个不同于 $v_1$ 的邻居 $w$，则 $w$ 不能是这条路径上的其他顶点，否则树中会出现环。因此可以把路径延长为 $w,v_0,v_1,\dots ,v_D$，长为 $D+1$。树内两点间路径唯一，这条延长路径仍是两端之间的最短路，与 $D$ 最大矛盾。另一端同理。

主例端点 $a,e$ 正是两片叶子。逆命题不成立：一棵树的任意两片叶子未必构成直径端点。若一个中心连接两条长度三的支臂和一条长度一的短支臂，两个长臂末端距离六，是直径；短臂末端到任一长臂末端距离只有四。叶子只是必要条件。

加边变式与最长路径反例

变式。 给主例增加边 $ea$，得到五顶点环 $C_5$。任意两点可沿两方向绕行，选短的一侧至多走两条边；确有相隔一个顶点的两点需要两步，故新直径为二。旧的四步路线仍存在，但已不再是端点之间的最短路线。

五环仍有包含全部五点的简单路径，长度四；直径却为二。这直接区分了“最长简单路径”与“最大最短距离”。在固定顶点集上增加边，所有最短距离都不增，直径也不增；删除边但保持连通时方向相反。

非连通图与有向图的约定

非连通图中的某些点对没有路径。若把这种距离定义为 $+\mathrm{\infty }$，整图直径也为无穷；有些应用只报告各分量的直径或其中最大值，必须明确这是另一个统计口径。例如两个分离的三角形，按扩展距离定义直径为无穷，按“最大分量直径”则为一。

有向图的距离通常按箭头方向定义，可能有 $d(u,v)\ne d(v,u)$。以全体有序顶点对取最大值时，要得到有限直径，必须强连通。忽略方向后计算的则是底层无向图直径，含义不同。