在图论 中，一张无向图 里，两顶点 之间的距离 是指他们之间最短路径 （英語：shortest path ）[ 註 1] 顶点 之间的距离 也被称为测地距离 （英語：geodesic distance ）[ 1] 顶点 之间可能有多条最短路径[ 2] 连通分量 ），那么按照传统它们距离被定义为无穷大。
在有向图 中，如果从顶点
u
{\displaystyle u}
v
{\displaystyle v}
有向路径 （英語：directed path ），那么距离
d
(
u
,
v
)
{\displaystyle d(u,v)}
u
{\displaystyle u}
v
{\displaystyle v}
最短有向路径 的长度[ 3]
d
(
u
,
v
)
{\displaystyle d(u,v)}
d
(
v
,
u
)
{\displaystyle d(v,u)}
[ 註 2]
u
{\displaystyle u}
v
{\displaystyle v}
v
{\displaystyle v}
u
{\displaystyle u}
一个顶点
v
{\displaystyle v}
偏心率
ϵ
(
v
)
{\displaystyle \epsilon (v)}
v
{\displaystyle v}
[ 4]
一张图的半径
r
{\displaystyle r}
r
=
min
v
∈
V
ϵ
(
v
)
{\displaystyle r=\min _{v\in V}\epsilon (v)}
[ 4]
一张图的直径
d
{\displaystyle d}
d
=
max
v
∈
V
ϵ
(
v
)
{\displaystyle d=\max _{v\in V}\epsilon (v)}
[ 4]
一张半径为
r
{\displaystyle r}
中心点 是所有的偏心率为
r
{\displaystyle r}
顶点 。若
v
{\displaystyle v}
ϵ
(
v
)
=
r
{\displaystyle \epsilon (v)=r}
[ 4]
边缘点 和中心点的定义类似。一张直径为
d
{\displaystyle d}
边缘点 是所有的偏心率为
d
{\displaystyle d}
v
{\displaystyle v}
ϵ
(
v
)
=
d
{\displaystyle \epsilon (v)=d}
[ 4]
图1 图2 图3
在图1中，顶点
B
{\displaystyle B}
C
{\displaystyle C}
d
(
B
,
C
)
=
1
{\displaystyle d(B,C)=1}
C
{\displaystyle C}
B
{\displaystyle B}
d
(
C
,
B
)
=
3
{\displaystyle d(C,B)=3}
顶点
V
1
{\displaystyle V_{1}}
V
2
{\displaystyle V_{2}}
V
3
{\displaystyle V_{3}}
V
4
{\displaystyle V_{4}}
V
5
{\displaystyle V_{5}}
V
6
{\displaystyle V_{6}}
偏心率
3
3
2
2
2
3
在图2中，例如，距离顶点
V
1
{\displaystyle V_{1}}
V
6
{\displaystyle V_{6}}
ϵ
(
V
1
)
=
3
{\displaystyle \epsilon (V_{1})=3}
导言中定义的顶点间的距离 也可以被扩展至加权图 [ 註 3] weighted graph ）。如在图3中，顶点3到顶点5的距离为
d
(
3
,
5
)
=
7
{\displaystyle d(3,5)=7}
^ 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 ^ Weisstein, Eric W. (编). Graph Geodesic . at MathWorld 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 ^ F. Harary. Graph Theory . Addison-Wesley. 1969: 199 . ^ 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.
