图距离 Distance (graph theory)

本词条由Ryan初步翻译

"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