距離 (圖論)

距離計法嘅示例：啲邊有箭咀嘅係有向圖。

喺圖論語境入便，距離係指一幅圖之中兩個頂點，佢哋之間嗰段最短路徑經歷咗幾多條邊。兩個頂點之間，可以有多過一條最短路徑。假如某兩個頂點之間完全冇任何路徑連接住，慣例上佢哋之間嘅距離就會設做無限大。

喺有向圖當中，兩個頂點 u 同 v 之間嘅距離 d(u,v)，定義上係指緊由 u 去 v 嘅最短、有向路徑有幾長，而前提係有最少一條噉嘅路徑存在。

相關概念

睇埋：圖論同距離

某頂點 v 嘅離心率用符號寫係 ε(v)，係指 v 同圖中任何其他頂點之間最遠相差幾大嘅距離，即係話：

$\epsilon (v)=\max _{u\in V}d(v,u)$

某幅圖嘅半徑 r 係指圖中頂點嘅最細嘅離心率，用符號表示即係：

$r=\min _{v\in V}\epsilon (v)=\min _{v\in V}\max _{u\in V}d(v,u)$

某幅圖嘅直徑 d 係指圖中頂點最大嘅離心率，用符號表達即係：

$d=\max _{v\in V}\epsilon (v)=\max _{v\in V}\max _{u\in V}d(v,u).$

要搵一幅圖嘅直徑，首先要計出每對頂點之間嘅最短路徑，呢啲路徑之中最長嘅嗰個長度，就係成幅圖嘅直徑。

運算問題

睇埋：運算複雜度、組合爆發同搵路演算法

要睇晒咁多條可能路徑然後決定邊條係最短路徑，可以好撈絞。噉係因為隨住邊嘅數量上升，可能路徑嘅數量會有爆發性嘅增長。

睇埋

• 網絡中心度
• 中介中心度