图距离

本词条由Ryan初步翻译 由CecileLi初步审校

"Geodesic distance" redirects here. For distances on the surface of a sphere, see Great-circle distance. For distances on the surface of the Earth, see Geodesics on an ellipsoid. For geodesics in differential geometry, see Geodesic.

在图论 Graph Theory的数学领域定义中，图中两个顶点之间的距离是最短路径 Shortest Path(也称为图测地线 Graph Geodesic)中连接它们的边的数目。这也被称为测地距离 Geodesic Distance。但，两个顶点之间可能有不止一条最短路径。一般地，如果两个顶点间没有路径连接，也就是说，如果它们属于不同的连通分支 Connected Components，那么这两点间的距离就被定义为无穷大。

在有向图 directed graph中，顶点 [math]\displaystyle{ u }[/math]和[math]\displaystyle{ v }[/math]之间的距离[math]\displaystyle{ d(u,v) }[/math]被定义为从[math]\displaystyle{ u }[/math] 到 [math]\displaystyle{ v }[/math]之间由弧组成的最短有向路径的长度，但前提是至少存在一条这样的路径。 与无向图不同， [math]\displaystyle{ d(u,v) }[/math] 不一定与[math]\displaystyle{ d(v,u) }[/math]一致，而且可能一个是符合定义的，而另一个不符合。

相关概念

一个由点集根据图中点集的距离定义的度度量空间 metric space被称为图度量 Graph Metric。

当且仅当图是连接的时，（无向图的）顶点集和距离函数构成度量空间。

一个顶点 vertex[math]\displaystyle{ v }[/math]的离心率 Eccentricity [math]\displaystyle{ \epsilon(v) }[/math]是它与其他顶点之间最大的距离,用[math]\displaystyle{ \epsilon(v) = \max_{u \in V}d(v,u) }[/math]表示。 这可以用来判断一个节点距离图中最远节点的距离。

图的半径 radius[math]\displaystyle{ r }[/math]是任何顶点的最小离心率，用[math]\displaystyle{ r = \min_{v \in V} \epsilon(v) = \min_{v \in V}\max_{u \in V}d(v,u) }[/math] 表示。

图的直径 diameter [math]\displaystyle{ d }[/math]是图中任何顶点的最大离心率。即[math]\displaystyle{ d }[/math] 是任何一对顶点之间最大的距离，[math]\displaystyle{ d = \max_{v \in V}\epsilon(v) }[/math]。要找到图的直径，首先要找到每对顶点之间的最短路径。这些路径的最大长度是图的直径。

在半径为[math]\displaystyle{ r }[/math]的图中，中心顶点 central vertex是离心率为 [math]\displaystyle{ r }[/math]顶点，即距离等于半径的顶点，或者等效于一个能够满足[math]\displaystyle{ \epsilon(v) = r }[/math] 的顶点[math]\displaystyle{ v }[/math]。

在直径为[math]\displaystyle{ d }[/math]的图中，边缘顶点 peripheral vertex 是离心率为 [math]\displaystyle{ d }[/math]顶点，即距离等于直径的顶点。定义，如果[math]\displaystyle{ \epsilon(v) = d }[/math]，[math]\displaystyle{ v }[/math]是次要的。

伪周边顶点 Pseudo-Peripheral Vertex [math]\displaystyle{ v }[/math]具有这样的属性：对于任何顶点 [math]\displaystyle{ u }[/math]，如果[math]\displaystyle{ v }[/math]距离[math]\displaystyle{ u }[/math]越远，那么[math]\displaystyle{ u }[/math]距离 [math]\displaystyle{ v }[/math]越远。定义，如果一个顶点u对于每个顶点v都有[math]\displaystyle{ d(u,v) = \epsilon(u) }[/math]保持[math]\displaystyle{ \epsilon(u)=\epsilon(v) }[/math]，则u是伪周边顶点。

依据图的顶点到给定起始顶点的距离将集合划分成多个子集称为图的层次结构 Level Structure of The Graph。

对于每对顶点，都有一条连接它们的唯一最短路径的图，则将该图称为测地图 geodetic graph。例如，所有的树状图都是测地图。

Algorithm for finding pseudo-peripheral vertices 寻找伪周边的算法

Often peripheral sparse matrix algorithms need a starting vertex with a high eccentricity. A peripheral vertex would be perfect, but is often hard to calculate. In most circumstances a pseudo-peripheral vertex can be used. A pseudo-peripheral vertex can easily be found with the following algorithm:

Often peripheral sparse matrix algorithms need a starting vertex with a high eccentricity. A peripheral vertex would be perfect, but is often hard to calculate. In most circumstances a pseudo-peripheral vertex can be used. A pseudo-peripheral vertex can easily be found with the following algorithm:

通常周边稀疏矩阵算法需要一个高离心率的起始点。一个外围的顶点会是首选，但往往难以计算。在大多数情况下，可以使用伪周边顶点。通过以下算法，可以很容易地找到伪周边顶点:

1. Choose a vertex [math]\displaystyle{ u }[/math].

Choose a vertex [math]\displaystyle{ u }[/math].

选择顶点[math]\displaystyle{ u }[/math]。

1. Among all the vertices that are as far from [math]\displaystyle{ u }[/math] as possible, let [math]\displaystyle{ v }[/math] be one with minimal degree.

Among all the vertices that are as far from [math]\displaystyle{ u }[/math] as possible, let [math]\displaystyle{ v }[/math] be one with minimal degree.

在所有尽可能远离[math]\displaystyle{ u }[/math]的顶点中，令[math]\displaystyle{ v }[/math]是一个最小度的顶点。

1. If [math]\displaystyle{ \epsilon(v) \gt \epsilon(u) }[/math] then set [math]\displaystyle{ u=v }[/math] and repeat with step 2, else [math]\displaystyle{ u }[/math] is a pseudo-peripheral vertex.

If [math]\displaystyle{ \epsilon(v) \gt \epsilon(u) }[/math] then set [math]\displaystyle{ u=v }[/math] and repeat with step 2, else [math]\displaystyle{ u }[/math] is a pseudo-peripheral vertex.

如果[math]\displaystyle{ \epsilon(v) \gt \epsilon(u) }[/math]那么令 [math]\displaystyle{ u=v }[/math]并重复步骤2，否则 [math]\displaystyle{ u }[/math]是一个伪周边顶点。

See also 另请参见

• Distance matrix

距离矩阵

• Resistance distance

电阻距离

• Betweenness centrality

介数中心性

• Centrality

中心性

• Closeness

封闭性

• Degree diameter problem for graphs and digraphs

图和有向图的度数直径问题

• Metric graph

指标图

Notes 注释

Category:Graph theory

范畴: 图论

This page was moved from wikipedia:en:Distance (graph theory). Its edit history can be viewed at 图距离/edithistory