在圖論中,一張無向圖里,兩頂點之間的距離是指他們之間最短路徑(英語:shortest path)[註 1]的長度,兩頂點之間的距離也被稱為測地距離(英語:geodesic distance)[1]。需要注意的是兩個頂點之間可能有多條最短路徑[2],如果兩個頂點之間不存在路徑(即他們屬於不同的連通分量),那麼按照傳統它們距離被定義為無窮大。
在有向圖中,如果從頂點 到頂點 存在有向路徑(英語:directed path),那麼距離 被定義為從頂點 到頂點 之間最短有向路徑的長度[3]。不同於無向圖,在有向圖中 不一定和 相等[註 2],甚至有可能出現從頂點 到頂點 存在有向路徑,而從頂點 到頂點 卻不存在有向路徑的情況。
相關概念
一個頂點 的偏心率 被定義為 和其它頂點的距離的最大值,也即是這個點和離其最遠點的距離[4]。
一張圖的半徑 被定義為最小的偏心率:[4]
一張圖的直徑 被定義為最大的偏心率:,也即最遠的兩點間的距離。若要求得一張圖的直徑,首先要求得任意兩點之間的最短路徑,在這些所有的最短路徑中,取其長度最長者,即是這張圖的直徑[4]。
一張半徑為 的圖的中心點是所有的偏心率為 的頂點。若 是一個中心點,那麼可用數學符號表示為 。一張圖可以有不止一個中心點[4]。
邊緣點和中心點的定義類似。一張直徑為 的圖的邊緣點是所有的偏心率為 的頂點。若 是一個邊緣點,那麼 。一張圖可以有多個邊緣點[4]。
例子
在圖1中,頂點 到頂點 的距離 ,而頂點 到頂點 的距離 。
頂點 | ||||||
偏心率 | 3 | 3 | 2 | 2 | 2 | 3 |
在圖2中,例如,距離頂點 的最遠點是頂點 ,那麼 。每一個頂點的偏心率如上表所示,所以圖1的半徑為2,而直徑為3。
導言中定義的頂點間的距離也可以被擴展至加權圖[註 3](英語:weighted graph)。如在圖3中,頂點3到頂點5的距離為 。
參見
注釋
參考資料
參考文獻
Wikiwand in your browser!
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.