图距离

本词条由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.

In the mathematical field of graph theory, the distance between two vertices in a graph is the number of edges in a shortest path (also called a graph geodesic) connecting them. This is also known as the geodesic distance. Notice that there may be more than one shortest path between two vertices.

Notice that there may be more than one shortest path between two vertices. If there is no path connecting the two vertices, i.e., if they belong to different connected components, then conventionally the distance is defined as infinite.

</ref> If there is no path connecting the two vertices, i.e., if they belong to different connected components, then conventionally the distance is defined as infinite.

一般地，如果两个顶点间没有路径连接，也就是说，如果它们属于不同的连通分支 Connected Components，那么这两点间的距离就被定义为无穷大。

In the case of a directed graph the distance [math]\displaystyle{ d(u,v) }[/math] between two vertices [math]\displaystyle{ u }[/math] and [math]\displaystyle{ v }[/math] is defined as the length of a shortest directed path from [math]\displaystyle{ u }[/math] to [math]\displaystyle{ v }[/math] consisting of arcs, provided at least one such path exists. Notice that, in contrast with the case of undirected graphs, [math]\displaystyle{ d(u,v) }[/math] does not necessarily coincide with [math]\displaystyle{ d(v,u) }[/math], and it might be the case that one is defined while the other is not.

In the case of a directed graph the distance [math]\displaystyle{ d(u,v) }[/math] between two vertices [math]\displaystyle{ u }[/math] and [math]\displaystyle{ v }[/math] is defined as the length of a shortest directed path from [math]\displaystyle{ u }[/math] to [math]\displaystyle{ v }[/math] consisting of arcs, provided at least one such path exists. Notice that, in contrast with the case of undirected graphs, [math]\displaystyle{ d(u,v) }[/math] does not necessarily coincide with [math]\displaystyle{ d(v,u) }[/math], and it might be the case that one is defined while the other is not.

在有向图中，两个顶点之间 [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]一致，而且可能一个是符合定义的，而另一个不符合。

Related concepts 相关概念

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.

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

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

The eccentricity [math]\displaystyle{ \epsilon(v) }[/math] of a vertex [math]\displaystyle{ v }[/math] is the greatest distance between [math]\displaystyle{ v }[/math] and any other vertex; in symbols that is [math]\displaystyle{ \epsilon(v) = \max_{u \in V}d(v,u) }[/math]. It can be thought of as how far a node is from the node most distant from it in the graph.

The eccentricity [math]\displaystyle{ \epsilon(v) }[/math] of a vertex [math]\displaystyle{ v }[/math] is the greatest distance between [math]\displaystyle{ v }[/math] and any other vertex; in symbols that is [math]\displaystyle{ \epsilon(v) = \max_{u \in V}d(v,u) }[/math]. It can be thought of as how far a node is from the node most distant from it in the graph.

一个顶点的离心率 Eccentricity是它与其他顶点之间最大的距离。这可以用来判断一个节点距离图中最远节点的距离。

The radius [math]\displaystyle{ r }[/math] of a graph is the minimum eccentricity of any vertex or, in symbols, [math]\displaystyle{ r = \min_{v \in V} \epsilon(v) = \min_{v \in V}\max_{u \in V}d(v,u) }[/math].

The radius [math]\displaystyle{ r }[/math] of a graph is the minimum eccentricity of any vertex or, in symbols, [math]\displaystyle{ r = \min_{v \in V} \epsilon(v) = \min_{v \in V}\max_{u \in V}d(v,u) }[/math].

图的半径[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] 。

The diameter [math]\displaystyle{ d }[/math] of a graph is the maximum eccentricity of any vertex in the graph. That is, [math]\displaystyle{ d }[/math] is the greatest distance between any pair of vertices or, alternatively, [math]\displaystyle{ d = \max_{v \in V}\epsilon(v) }[/math]. To find the diameter of a graph, first find the shortest path between each pair of vertices. The greatest length of any of these paths is the diameter of the graph.

The diameter [math]\displaystyle{ d }[/math] of a graph is the maximum eccentricity of any vertex in the graph. That is, [math]\displaystyle{ d }[/math] is the greatest distance between any pair of vertices or, alternatively, [math]\displaystyle{ d = \max_{v \in V}\epsilon(v) }[/math]. To find the diameter of a graph, first find the shortest path between each pair of vertices. The greatest length of any of these paths is the diameter of the graph.

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

A central vertex in a graph of radius [math]\displaystyle{ r }[/math] is one whose eccentricity is [math]\displaystyle{ r }[/math]—that is, a vertex that achieves the radius or, equivalently, a vertex [math]\displaystyle{ v }[/math] such that [math]\displaystyle{ \epsilon(v) = r }[/math].

A central vertex in a graph of radius [math]\displaystyle{ r }[/math] is one whose eccentricity is [math]\displaystyle{ r }[/math]—that is, a vertex that achieves the radius or, equivalently, a vertex [math]\displaystyle{ v }[/math] such that [math]\displaystyle{ \epsilon(v) = r }[/math].

半径[math]\displaystyle{ r }[/math]图中的中心顶点的离心率是 [math]\displaystyle{ r }[/math]&mdash，也就是说，距离为半径的顶点，或者等效于一个顶点[math]\displaystyle{ v }[/math]，这样 [math]\displaystyle{ \epsilon(v) = r }[/math] 。

A peripheral vertex in a graph of diameter [math]\displaystyle{ d }[/math] is one that is distance [math]\displaystyle{ d }[/math] from some other vertex—that is, a vertex that achieves the diameter. Formally, [math]\displaystyle{ v }[/math] is peripheral if [math]\displaystyle{ \epsilon(v) = d }[/math].

A peripheral vertex in a graph of diameter [math]\displaystyle{ d }[/math] is one that is distance [math]\displaystyle{ d }[/math] from some other vertex—that is, a vertex that achieves the diameter. Formally, [math]\displaystyle{ v }[/math] is peripheral if [math]\displaystyle{ \epsilon(v) = d }[/math].

直径[math]\displaystyle{ d }[/math]图中的边缘顶点与其他顶点之间的距离为[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{ u }[/math]，如果[math]\displaystyle{ v }[/math]离[math]\displaystyle{ u }[/math]越远，那么 [math]\displaystyle{ u }[/math]离 [math]\displaystyle{ v }[/math]越远。形式上，一个顶点 u 是伪外围的/伪周边的,

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].

如果对于每个顶点 v 都有[math]\displaystyle{ d(u,v) = \epsilon(u) }[/math]保持[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