距离 (图论)

一个顶点 ${\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 - 有向图

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

例2 - 直径和半径

在图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}$ 。

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

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