图距离

本词条由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]一致，而且可能一个是符合定义的，而另一个不符合。

相关概念

A metric space defined over a set of points in terms of distances in a graph defined over the set is called a graph metric.

A metric space defined over a set of points in terms of distances in a graph defined over the set is called a graph metric. 定义在一组点上的度量空间,是 根据在该集合上定义的图上的距离定义的，称为图度量。

根据度量空间 metric space定义， 在一个由集合组成的图中，集合内点上的度量空间距离被称为图度量 Graph Metric。

The vertex set (of an undirected graph) and the distance function form a metric space, if and only if the graph is connected.

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

一个顶点 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]是次要的。

A pseudo-peripheral vertex [math]\displaystyle{ v }[/math] has the property that for any vertex [math]\displaystyle{ u }[/math], if [math]\displaystyle{ v }[/math] is as far away from [math]\displaystyle{ u }[/math] as possible, then [math]\displaystyle{ u }[/math] is as far away from [math]\displaystyle{ v }[/math] as possible. Formally, a vertex u is pseudo-peripheral,

A pseudo-peripheral vertex [math]\displaystyle{ v }[/math] has the property that for any vertex [math]\displaystyle{ u }[/math], if [math]\displaystyle{ v }[/math] is as far away from [math]\displaystyle{ u }[/math] as possible, then [math]\displaystyle{ u }[/math] is as far away from [math]\displaystyle{ v }[/math] as possible. Formally, a vertex u is pseudo-peripheral,

伪周边顶点 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]。

if for each vertex v with [math]\displaystyle{ d(u,v) = \epsilon(u) }[/math] holds [math]\displaystyle{ \epsilon(u)=\epsilon(v) }[/math].

if for each vertex v with [math]\displaystyle{ d(u,v) = \epsilon(u) }[/math] holds [math]\displaystyle{ \epsilon(u)=\epsilon(v) }[/math].

The partition of a graph's vertices into subsets by their distances from a given starting vertex is called the level structure of the graph.

The partition of a graph's vertices into subsets by their distances from a given starting vertex is called the level structure of the graph.

图的顶点依据与它们与给定顶点之间的距离划分成子集的过程称为图的层次结构 Level Structure of The Graph。

A graph such that for every pair of vertices there is a unique shortest path connecting them is called a geodetic graph. For example, all trees are geodetic.

A graph such that for every pair of vertices there is a unique shortest path connecting them is called a geodetic graph. For example, all trees are geodetic.

如果对于每一对顶点，有一条唯一的最短路径连接它们，那么这样的图称为测地图 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