使用者:EtaoinWu/距離 (圖論)
外觀
在圖論中,一張圖兩個點之間的距離是指他們之間最短路徑的邊數。這也被稱為圖的測地距離。[1] 兩個點之間可能有多條最短路徑。[2] 如果兩個頂點之間沒有路徑(即他們屬於不同的連通分量),那麼按照傳統它們距離被定義為無窮大。
在有向圖的情況中,距離被定義為兩個頂點 和 之間最短路徑的邊數(如果存在)[3]。注意到,與無向圖不同, 不必與 相等。
相關概念
[編輯]一個利用圖的距離定義的測度空間被稱為圖測度。若且唯若這張無向圖是連通圖時這形成了一個測度空間。
一個結點的偏心率 被定義為 和其它頂點的距離的最大值,也被認為是這個點離其最遠點的距離。
一個圖的半徑 被定義為最小的偏心率:。
一張圖的直徑 被定義為最大的偏心率,即最大的兩點距離:。
參考資料
[編輯]- ^ 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.
By distance we mean here geodesic distance along the graph, namely the length of any shortest path between say two given faces
- ^ Weisstein, Eric W. Graph Geodesic. MathWorld--A Wolfram Web Resource. Wolfram Research. [2008-04-23].
The length of the graph geodesic between these points d(u,v) is called the graph distance between u and v
- ^ F. Harary, Graph Theory, Addison-Wesley, 1969, p.199.