User:EtaoinWu/距离 (图论)

在图论中，一张图两个点之间的距离是指他们之间最短路径的边数。这也被称为图的测地距离。 两个点之间可能有多条最短路径。 如果两个顶点之间没有路径（即他们属于不同的连通分量），那么按照传统它们距离被定义为无穷大。

在有向图的情况中，距离$d(u,v)$被定义为两个顶点 $u$ 和 $v$ 之间最短路径的边数（如果存在）。注意到，与无向图不同，$d(u,v)$ 不必与 $d(v,u)$相等。

相关概念

一个利用图的距离定义的测度空间被称为图测度。当且仅当这张无向图是连通图时这形成了一个测度空间。

一个结点$v$的偏心率 $\epsilon (v)$ 被定义为 $v$ 和其它顶点的距离的最大值，也被认为是这个点离其最远点的距离。

一个图的半径 $r$ 被定义为最小的偏心率：$r=\min _{v\in V}\epsilon (v)$。

一张图的直径 $d$ 被定义为最大的偏心率，即最大的两点距离：$d=\max _{v\in V}\epsilon (v)$。