75
个编辑
更改
无编辑摘要
本词条由Ryan初步翻译
{{Redirect|Geodesic distance|distances on the surface of a sphere|Great-circle distance|distances on the surface of the Earth|Geodesics on an ellipsoid|geodesics in differential geometry|Geodesic}}
{{Redirect|Geodesic distance|distances on the surface of a sphere|Great-circle distance|distances on the surface of the Earth|Geodesics on an ellipsoid|geodesics in differential geometry|Geodesic}}
在图论的数学领域中，图中两个顶点之间的距离是最短路径(也称为图测地线)中连接它们的边的数目。这也被称为测地距离。3 = Guitter，e. | date = July 2003
在图论的数学领域中，图中两个顶点之间的距离是最短路径(也称为图测地线)中连接它们的边的数目。这也被称为测地距离。3 = Guitter，e. | date = July 2003
|title=Geodesic distance in planar graphs |journal= Nuclear Physics B|volume=663 |issue=3 |pages=535–567 |quote=By distance we mean here geodesic distance along the graph, namely the length of any shortest path between say two given faces
|title=Geodesic distance in planar graphs |journal= Nuclear Physics B|volume=663 |issue=3 |pages=535–567 |quote=By distance we mean here geodesic distance along the graph, namely the length of any shortest path between say two given faces|doi=10.1016/S0550-3213(03)00355-9|arxiv=cond-mat/0303272 }}</ref> Notice that there may be more than one shortest path between two vertices.<ref>
|title=Geodesic distance in planar graphs |journal= Nuclear Physics B|volume=663 |issue=3 |pages=535–567 |quote=By distance we mean here geodesic distance along the graph, namely the length of any shortest path between say two given faces
|title=Geodesic distance in planar graphs |journal= Nuclear Physics B|volume=663 |issue=3 |pages=535–567 |quote=By distance we mean here geodesic distance along the graph, namely the length of any shortest path between say two given faces |doi=10.1016/S0550-3213(03)00355-9|arxiv=cond-mat/0303272 }}</ref>
Notice that there may be more than one shortest path between two vertices.<ref>
注意，在两个顶点之间可能有一个以上的最短路径
注意，在两个顶点之间可能有一个以上的最短路径
|last=Weisstein |first=Eric W. |authorlink=Eric W. Weisstein |work=MathWorld--A Wolfram Web Resource
|last=Weisstein |first=Eric W. |authorlink=Eric W. Weisstein |work=MathWorld--A Wolfram Web Resource
|publisher= Wolfram Research
|publisher= Wolfram Research
|publisher= Wolfram Research
|publisher= Wolfram Research
|quote=The length of the graph geodesic between these points d(u,v) is called the graph distance between u and v }}
|quote=The length of the graph geodesic between these points d(u,v) is called the graph distance between u and v }}
|quote=The length of the graph geodesic between these points d(u,v) is called the graph distance between u and v }}
|quote=The length of the graph geodesic between these points d(u,v) is called the graph distance between u and v }}
</ref> If there is no path connecting the two vertices, i.e., if they belong to different [[connected component (graph theory)|connected component]]s, 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 component (graph theory)|connected component]]s, 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.
</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.
如果两个顶点间没有路径连接，也就是说，如果它们属于不同的连通分支，那么按照惯例，距离被定义为无穷大。
In the case of a directed graph the distance <math>d(u,v)</math> between two vertices <math>u</math> and <math>v</math> is defined as the length of a shortest directed path from <math>u</math> to <math>v</math> consisting of arcs, provided at least one such path exists. Notice that, in contrast with the case of undirected graphs, <math>d(u,v)</math> does not necessarily coincide with <math>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>d(u,v)</math> between two vertices <math>u</math> and <math>v</math> is defined as the length of a shortest directed path from <math>u</math> to <math>v</math> consisting of arcs, provided at least one such path exists. Notice that, in contrast with the case of undirected graphs, <math>d(u,v)</math> does not necessarily coincide with <math>d(v,u)</math>, and it might be the case that one is defined while the other is not.
在有向图的情况下，两个顶点之间 <math>u</math>和<math>v</math>的距离<math>d(u,v)</math>被定义为从<math>u</math> 到 <math>v</math>由弧组成的最短有向路径的长度，前提是至少存在一条这样的路径。请注意，与无向图的情况不同， <math>d(u,v)</math> 不一定与<math>d(v,u)</math>一致，而且可能一个是被定义的，而另一个不是。
==Related concepts==
==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'''.
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>\epsilon(v)</math> of a vertex <math>v</math> is the greatest distance between <math>v</math> and any other vertex; in symbols that is <math>\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>\epsilon(v)</math> of a vertex <math>v</math> is the greatest distance between <math>v</math> and any other vertex; in symbols that is <math>\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 radius <math>r</math> of a graph is the minimum eccentricity of any vertex or, in symbols, <math>r = \min_{v \in V} \epsilon(v) = \min_{v \in V}\max_{u \in V}d(v,u)</math>.
The radius <math>r</math> of a graph is the minimum eccentricity of any vertex or, in symbols, <math>r = \min_{v \in V} \epsilon(v) = \min_{v \in V}\max_{u \in V}d(v,u)</math>.
图的半径 < math > r </math > 是任何顶点的最小离心率，或者，在符号中，< math > r = min { v } epsilon (v) = min { v } max { u in v } d (v，u) </math > 。
图的半径<math>r</math>是任何顶点的最小偏心率，或者，在符号中，<math>r = \min_{v \in V} \epsilon(v) = \min_{v \in V}\max_{u \in V}d(v,u)</math> 。
The diameter <math>d</math> of a graph is the maximum eccentricity of any vertex in the graph. That is, <math>d</math> is the greatest distance between any pair of vertices or, alternatively, <math>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>d</math> of a graph is the maximum eccentricity of any vertex in the graph. That is, <math>d</math> is the greatest distance between any pair of vertices or, alternatively, <math>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 > d </math > 是图中任何顶点的最大离心率。也就是说，< math > d </math > 是任何一对顶点之间最大的距离，或者，< math > d = max _ { v }/epsilon (v) </math > 。要找到图的直径，首先要找到每对顶点之间的最短路径。这些路径的最大长度是图的直径。
图的直径 <math>d</math>是图中任何顶点的最大偏心率。也就是说， <math>d</math> 是任何一对顶点之间最大的距离，或者，<math>d = \max_{v \in V}\epsilon(v)</math>。要找到图的直径，首先要找到每对顶点之间的最短路径。这些路径的最大长度是图的直径。
A central vertex in a graph of radius <math>r</math> is one whose eccentricity is <math>r</math>—that is, a vertex that achieves the radius or, equivalently, a vertex <math>v</math> such that <math>\epsilon(v) = r</math>.
A central vertex in a graph of radius <math>r</math> is one whose eccentricity is <math>r</math>—that is, a vertex that achieves the radius or, equivalently, a vertex <math>v</math> such that <math>\epsilon(v) = r</math>.
半径 < math > r </math > 图中的中心顶点的离心率是 < math > r </math > ——也就是说，达到半径的顶点，或者等效于一个顶点 < math > v </math > ，这样 < math > epsilon (v) = r </math > 。
半径<math>r</math>图中的中心顶点的偏心率是 <math>r</math>&mdash，也就是说，达到半径的顶点，或者等效于一个顶点<math>v</math>，这样 <math>\epsilon(v) = r</math> 。
A peripheral vertex in a graph of diameter <math>d</math> is one that is distance <math>d</math> from some other vertex—that is, a vertex that achieves the diameter. Formally, <math>v</math> is peripheral if <math>\epsilon(v) = d</math>.
A peripheral vertex in a graph of diameter <math>d</math> is one that is distance <math>d</math> from some other vertex—that is, a vertex that achieves the diameter. Formally, <math>v</math> is peripheral if <math>\epsilon(v) = d</math>.
直径 < math > d </math > 图中的边缘顶点与其他顶点之间的距离为 d < math > d </math > ，即达到直径的顶点。形式上，如果 < math > epsilon (v) = d </math > ，< math > v </math > 是次要的。
直径<math>d</math>图中的边缘顶点与其他顶点之间的距离为<math>d</math>，即达到直径的顶点。形式上，如果<math>\epsilon(v) = d</math>，<math>v</math>是次要的。
A pseudo-peripheral vertex <math>v</math> has the property that for any vertex <math>u</math>, if <math>v</math> is as far away from <math>u</math> as possible, then <math>u</math> is as far away from <math>v</math> as possible. Formally, a vertex u is pseudo-peripheral,
A pseudo-peripheral vertex <math>v</math> has the property that for any vertex <math>u</math>, if <math>v</math> is as far away from <math>u</math> as possible, then <math>u</math> is as far away from <math>v</math> as possible. Formally, a vertex u is pseudo-peripheral,
一个伪周边顶点具有这样的属性: 对于任何顶点，如果 < math > u </math > ，如果 < math > v </math > 离 < math > u </math > 越远越好，那么 < math > u </math > 离 < math > 越远越好。形式上，一个顶点 u 是伪外围的,
一个伪周边顶点具有这样的属性: 对于任何顶点 <math>u</math>，如果<math>v</math>离<math>u</math>越远，那么 <math>u</math>离 <math>v</math>越远。形式上，一个顶点 u 是伪外围的,
if for each vertex ''v'' with <math>d(u,v) = \epsilon(u)</math> holds <math>\epsilon(u)=\epsilon(v)</math>.
if for each vertex ''v'' with <math>d(u,v) = \epsilon(u)</math> holds <math>\epsilon(u)=\epsilon(v)</math>.
if for each vertex v with <math>d(u,v) = \epsilon(u)</math> holds <math>\epsilon(u)=\epsilon(v)</math>.
if for each vertex v with <math>d(u,v) = \epsilon(u)</math> holds <math>\epsilon(u)=\epsilon(v)</math>.
如果对于每个顶点 v 都有 < math > d (u，v) = epsilon (u) </math > 保存 < math > epsilon (u) = epsilon (v) </math > 。
如果对于每个顶点 v 都有<math>d(u,v) = \epsilon(u)</math>保持<math>\epsilon(u)=\epsilon(v)</math>。
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.
对于每一对顶点，有一条唯一的最短路径连接它们，这样的图称为大地图。例如，所有的树都是大地图。
==Algorithm for finding pseudo-peripheral vertices==
==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:
Choose a vertex <math>u</math>.
Choose a vertex <math>u</math>.
选择顶点 < math > u </math > 。
选择顶点<math>u</math>。
# Among all the vertices that are as far from <math>u</math> as possible, let <math>v</math> be one with minimal [[degree (graph theory)|degree]].
# Among all the vertices that are as far from <math>u</math> as possible, let <math>v</math> be one with minimal [[degree (graph theory)|degree]].
Among all the vertices that are as far from <math>u</math> as possible, let <math>v</math> be one with minimal degree.
Among all the vertices that are as far from <math>u</math> as possible, let <math>v</math> be one with minimal degree.
在所有尽可能远离 < math > u </math > 的顶点中，让 < math > v </math > 是一个最小度的顶点。
在所有尽可能远离<math>u</math>的顶点中，让<math>v</math>是一个最小度的顶点。
# If <math>\epsilon(v) > \epsilon(u)</math> then set <math>u=v</math> and repeat with step 2, else <math>u</math> is a pseudo-peripheral vertex.
# If <math>\epsilon(v) > \epsilon(u)</math> then set <math>u=v</math> and repeat with step 2, else <math>u</math> is a pseudo-peripheral vertex.
If <math>\epsilon(v) > \epsilon(u)</math> then set <math>u=v</math> and repeat with step 2, else <math>u</math> is a pseudo-peripheral vertex.
If <math>\epsilon(v) > \epsilon(u)</math> then set <math>u=v</math> and repeat with step 2, else <math>u</math> is a pseudo-peripheral vertex.
如果 < math > epsilon (v) > epsilon (u) </math > 然后设置 < math > u = v </math > 并用步骤2重复，否则 < math > u </math > 是一个伪周边顶点。
如果<math>\epsilon(v) > \epsilon(u)</math>然后设置 <math>u=v</math>并重复步骤2，否则 <math>u</math>是一个伪周边顶点。
==See also==
==See also 另请参见==
* [[Distance matrix]]
* [[Distance matrix]]
距离矩阵
* [[Resistance distance]]
* [[Resistance distance]]
电阻距离
* [[Betweenness centrality]]
* [[Betweenness centrality]]
介数中心性
* [[Centrality]]
* [[Centrality]]
中心性
* [[Closeness (graph theory)|Closeness]]
* [[Closeness (graph theory)|Closeness]]
封闭性
* [[Degree diameter problem]] for [[Graph (discrete mathematics)|graph]]s and [[digraph (mathematics)|digraph]]s
* [[Degree diameter problem]] for [[Graph (discrete mathematics)|graph]]s and [[digraph (mathematics)|digraph]]s
图和有向图的度数直径问题
* [[Metric graph]]
* [[Metric graph]]
指标图