距離 (圖論)

在圖論中，一張無向圖里，兩頂點之間的距離是指他們之間最短路徑（英語：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 （英語）.