在图论中，一张无向图里，两顶点之间的距离是指他们之间最短路径（）的长度，两顶点之间的距离也被称为测地距离（）。需要注意的是两个顶点之间可能有多条最短路径，如果两个顶点之间不存在路径（即他们属于不同的连通分量），那么按照传统它们距离被定义为无穷大。
在有向图中，如果从顶点 u 到顶点 v 存在有向路径（），那么距离 d(u,v) 被定义为从顶点 u 到顶点 v 之间最短有向路径的长度。不同于无向图，在有向图中 d(u,v) 不一定和 d(v,u) 相等，甚至有可能出现从顶点 u 到顶点 v 存在有向路径，而从顶点 v 到顶点 u 却不存在有向路径的情况。
相关概念
一个顶点 v 的偏心率 \epsilon(v) 被定义为 v 和其它顶点的距离的最大值，也即是这个点和离其最远点的距离
一张图的直径 d 被定义为最大的偏心率：d = \max_{v \in V}\epsilon(v)，也即最远的两点间的距离。若要求得一张图的直径，首先要求得任意两点之间的最短路径，在这些所有的最短路径中，取其长度最长者，即是这张图的直径。
一张半径为 r 的图的中心点是所有的偏心率为 r 的顶点。若 v 是一个中心点，那么可用数学符号表示为 \epsilon(v) = r。一张图可以有不止一个中心点。
边缘点和中心点的定义类似。一张直径为 d 的图的边缘点是所有的偏心率为 d 的顶点。若 v 是一个边缘点，那么 \epsilon(v) = d。一张图可以有多个边缘点。
例子
有向图
在图1中，顶点 B 到顶点 C 的距离 d(B,C)=1 ，而顶点 C 到顶点 B 的距离 d(C,B)=3。
直径和半径
在图2中，例如，距离顶点 V_1 的最远点是顶点 V_6 ，那么 \epsilon(V_1) = 3。每一个顶点的偏心率如上表所示，所以图1的半径为2，而直径为3。
加权图
导言中定义的顶点间的距离也可以被扩展至加权图（）。如在图3中，顶点3到顶点5的距离为 d(3,5)=7。
参见
- 连通图
- 最短路问题
- 图论术语
注释
参考资料
参考文献
*
评论 (0)