距离 (图论)

在图论中，一张无向图里，两顶点之间的距离是指他们之间最短路径（英语：shortest path）的长度，两顶点之间的距离也被称为测地距离（英语：geodesic distance）。需要注意的是两个顶点之间可能有多条最短路径，如果两个顶点之间不存在路径（即他们属于不同的连通分量），那么按照传统它们距离被定义为无穷大。

在有向图中，如果从顶点 $u$ 到顶点 $v$ 存在有向路径（英语：directed path），那么距离 $d(u,v)$ 被定义为从顶点 $u$ 到顶点 $v$ 之间最短有向路径的长度。不同于无向图，在有向图中 $d(u,v)$ 不一定和 $d(v,u)$ 相等，甚至有可能出现从顶点 $u$ 到顶点 $v$ 存在有向路径，而从顶点 $v$ 到顶点 $u$ 却不存在有向路径的情况。

相关概念

一个顶点 $v$ 的偏心率 $\epsilon (v)$ 被定义为 $v$ 和其它顶点的距离的最大值，也即是这个点和离其最远点的距离。

一张图的半径 $r$ 被定义为最小的偏心率：$r=\min _{v\in V}\epsilon (v)$

一张图的直径 $d$ 被定义为最大的偏心率：$d=\max _{v\in V}\epsilon (v)$，也即最远的两点间的距离。若要求得一张图的直径，首先要求得任意两点之间的最短路径，在这些所有的最短路径中，取其长度最长者，即是这张图的直径。

一张半径为 $r$ 的图的中心点是所有的偏心率为 $r$ 的顶点。若 $v$ 是一个中心点，那么可用数学符号表示为 $\epsilon (v)=r$。一张图可以有不止一个中心点。

边缘点和中心点的定义类似。一张直径为 $d$ 的图的边缘点是所有的偏心率为 $d$ 的顶点。若 $v$ 是一个边缘点，那么 $\epsilon (v)=d$。一张图可以有多个边缘点。

例子

图1

图2

图3

有向图

在图1中，顶点 $B$ 到顶点 $C$ 的距离 $d(B,C)=1$，而顶点 $C$ 到顶点 $B$ 的距离 $d(C,B)=3$。

直径和半径

顶点	$V_{1}$	$V_{2}$	$V_{3}$	$V_{4}$	$V_{5}$	$V_{6}$
偏心率	3	3	2	2	2	3

在图2中，例如，距离顶点 $V_{1}$ 的最远点是顶点 $V_{6}$，那么 $\epsilon (V_{1})=3$。每一个顶点的偏心率如上表所示，所以图1的半径为2，而直径为3。

加权图

导言中定义的顶点间的距离也可以被扩展至加权图（英语：weighted graph）。如在图3中，顶点3到顶点5的距离为 $d(3,5)=7$。

参见

• 连通图
• 最短路问题
• 图论术语

参考文献 

• Diestel, Reinhard. Graph Theory. Springer. 2000: 8. ISBN 9780585498935 （英语）.