用戶:EtaoinWu/距離 (圖論)

在圖論中，一張圖兩個點之間的距離是指他們之間最短路徑的邊數。這也被稱為圖的測地距離。 兩個點之間可能有多條最短路徑。 如果兩個頂點之間沒有路徑（即他們屬於不同的連通分量），那麼按照傳統它們距離被定義為無窮大。

在有向圖的情況中，距離$d(u,v)$被定義為兩個頂點 $u$ 和 $v$ 之間最短路徑的邊數（如果存在）。注意到，與無向圖不同，$d(u,v)$ 不必與 $d(v,u)$相等。

相關概念

一個利用圖的距離定義的測度空間被稱為圖測度。若且唯若這張無向圖是連通圖時這形成了一個測度空間。

一個結點$v$的偏心率 $\epsilon (v)$ 被定義為 $v$ 和其它頂點的距離的最大值，也被認為是這個點離其最遠點的距離。

一個圖的半徑 $r$ 被定義為最小的偏心率：$r=\min _{v\in V}\epsilon (v)$。

一張圖的直徑 $d$ 被定義為最大的偏心率，即最大的兩點距離：$d=\max _{v\in V}\epsilon (v)$。