距离 (图论)

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

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

相关概念

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

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

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

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

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

例子

 

图1

 

图2

 

图3

例1 - 有向图

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

例2 - 直径和半径

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

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

例3 - 加权图

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

参见

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

注释

1. 两点间的最短路径也被称为图的测地线（英語：graph geodesic）。
2. 见例1。
3. 加权图的含义是每一条边可以有各自的长度。

参考资料

1. Bouttier, Jérémie; Di Francesco,P.; Guitter, E. Geodesic distance in planar graphs. Nuclear Physics B. July 2003, 663 (3): 535–567 [2008-04-23]. doi:10.1016/S0550-3213(03)00355-9. （原始内容于2008-10-04）. By distance we mean here geodesic distance along the graph, namely the length of any shortest path between say two given faces 
2. Weisstein, Eric W. (编). Graph Geodesic. at MathWorld--A Wolfram Web Resource. Wolfram Research, Inc. [2008-04-23]. （原始内容于2008-04-23） （英语）. The length of the graph geodesic between these points d(u,v) is called the graph distance between u and v 
3. F. Harary. Graph Theory. Addison-Wesley. 1969: 199. 
4. Chartrand G., Johns G., Oellermann O.R. On Peripheral Vertices in Graphs. Bodendiek R., Henn R. (编). Topics in Combinatorics and Graph Theory. Physica-Verlag HD. 1990. 

参考文献 

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