跳至內容

距離 (圖論)

維基百科,自由的百科全書

圖論中,一張無向圖里,兩頂點之間的距離是指他們之間最短路徑(英語:shortest path[註 1]的長度,兩頂點之間的距離也被稱為測地距離(英語:geodesic distance[1]。需要注意的是兩個頂點之間可能有多條最短路徑[2],如果兩個頂點之間不存在路徑(即他們屬於不同的連通分量),那麼按照傳統它們距離被定義為無窮大。

有向圖中,如果從頂點 到頂點 存在有向路徑(英語:directed path),那麼距離 被定義為從頂點  到頂點  之間最短有向路徑的長度[3]。不同於無向圖,在有向圖中 不一定和 相等[註 2],甚至有可能出現從頂點 到頂點 存在有向路徑,而從頂點 到頂點 卻不存在有向路徑的情況。

相關概念

一個頂點 偏心率  被定義為 和其它頂點的距離的最大值,也即是這個點和離其最遠點的距離[4]

一張圖的半徑  被定義為最小的偏心率:[4]

一張圖的直徑  被定義為最大的偏心率:,也即最遠的兩點間的距離。若要求得一張圖的直徑,首先要求得任意兩點之間的最短路徑,在這些所有的最短路徑中,取其長度最長者,即是這張圖的直徑[4]

一張半徑為 的圖的中心點是所有的偏心率為 頂點。若 是一個中心點,那麼可用數學符號表示為 。一張圖可以有不止一個中心點[4]

邊緣點和中心點的定義類似。一張直徑為 的圖的邊緣點是所有的偏心率為 的頂點。若 是一個邊緣點,那麼 。一張圖可以有多個邊緣點[4]

例子

圖1
圖2
圖3

有向圖

在圖1中,頂點 到頂點 的距離 ,而頂點 到頂點 的距離

直徑和半徑

頂點
偏心率 3 3 2 2 2 3

在圖2中,例如,距離頂點 的最遠點是頂點 ,那麼 。每一個頂點的偏心率如上表所示,所以圖1的半徑為2,而直徑為3。

加權圖

導言中定義的頂點間的距離也可以被擴展至加權圖[註 3](英語:weighted graph)。如在圖3中,頂點3到頂點5的距離為

參見

註釋

  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. ^ 4.0 4.1 4.2 4.3 4.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. 

參考文獻