“图距离 Distance (graph theory)”的版本间的差异
（Moved page from wikipedia:en:Distance (graph theory) (history)） |
|||
| 第1行： | 第1行： | ||
| − | + | 本词条由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}} | ||
| 第11行： | 第11行： | ||
在图论的数学领域中，图中两个顶点之间的距离是最短路径(也称为图测地线)中连接它们的边的数目。这也被称为测地距离。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> | |
| − | |||
| − | |||
| − | |||
| − | |||
注意，在两个顶点之间可能有一个以上的最短路径 | 注意，在两个顶点之间可能有一个以上的最短路径 | ||
| 第33行： | 第29行： | ||
|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 | ||
| 第39行： | 第35行： | ||
|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 }} | ||
| 第45行： | 第41行： | ||
|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. | ||
| 第51行： | 第47行： | ||
</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. | ||
| − | + | 如果两个顶点间没有路径连接，也就是说，如果它们属于不同的连通分支，那么按照惯例，距离被定义为无穷大。 | |
| 第59行： | 第55行： | ||
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'''. | ||
| 第75行： | 第71行： | ||
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. | ||
| − | (无向图的) | + | 当且仅当图是连通的时，(无向图的)顶点集和距离函数构成度量空间。 |
| 第83行： | 第79行： | ||
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. | ||
| − | + | 一个顶点的偏心率是它与其他顶点之间最大的距离。它可以被认为是一个节点距离图中离它最远的节点有多远。 | |
| 第91行： | 第87行： | ||
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</math>是任何顶点的最小偏心率，或者，在符号中，<math>r = \min_{v \in V} \epsilon(v) = \min_{v \in V}\max_{u \in V}d(v,u)</math> 。 |
| 第99行： | 第95行： | ||
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</math> 是任何一对顶点之间最大的距离，或者，<math>d = \max_{v \in V}\epsilon(v)</math>。要找到图的直径，首先要找到每对顶点之间的最短路径。这些路径的最大长度是图的直径。 |
| 第107行： | 第103行： | ||
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>r</math>&mdash，也就是说，达到半径的顶点，或者等效于一个顶点<math>v</math>，这样 <math>\epsilon(v) = r</math> 。 |
| 第115行： | 第111行： | ||
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 > 图中的边缘顶点与其他顶点之间的距离为 | + | 直径<math>d</math>图中的边缘顶点与其他顶点之间的距离为<math>d</math>，即达到直径的顶点。形式上，如果<math>\epsilon(v) = d</math>，<math>v</math>是次要的。 |
| 第123行： | 第119行： | ||
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>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>. | ||
| 第129行： | 第125行： | ||
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 ( | + | 如果对于每个顶点 v 都有<math>d(u,v) = \epsilon(u)</math>保持<math>\epsilon(u)=\epsilon(v)</math>。 |
| 第145行： | 第141行： | ||
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: | ||
| 第163行： | 第159行： | ||
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]]. | ||
| 第169行： | 第165行： | ||
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. | ||
| 第175行： | 第171行： | ||
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 > | + | 如果<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]] | ||
| − | + | 指标图 | |
2020年9月2日 (三) 21:43的版本
本词条由Ryan初步翻译
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.引用错误：没有找到与</ref>对应的<ref>标签 Notice that there may be more than one shortest path between two vertices.[1]
Notice that there may be more than one shortest path between two vertices.[2] 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]\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.[3] 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.
一个度量空间定义在一个集合上的点集合上，该集合上的图的距离称为图度量。
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.
一个顶点的偏心率是它与其他顶点之间最大的距离。它可以被认为是一个节点距离图中离它最远的节点有多远。
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,
一个伪周边顶点具有这样的属性: 对于任何顶点 [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.
图的顶点按照它们与给定顶点之间的距离划分成子集的过程称为图的层次结构。
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.[4]
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 寻找伪周边的算法
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]\displaystyle{ u }[/math].
Choose a vertex [math]\displaystyle{ u }[/math].
选择顶点[math]\displaystyle{ u }[/math]。
- 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]是一个最小度的顶点。
- 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 另请参见
距离矩阵
电阻距离
介数中心性
中心性
封闭性
- Degree diameter problem for graphs and digraphs
图和有向图的度数直径问题
指标图
Notes
- ↑ |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 }}
- ↑
注意，在两个顶点之间可能有一个以上的最短路径
"Graph Geodesic". Retrieved 2008-04-23
Weisstein, Eric W. "Graph Geodesic". MathWorld--A Wolfram Web Resource. Wolfram Research. Retrieved 2008-04-23.
The length of the graph geodesic between these points d(u,v) is called the graph distance between u and v
.The length of the graph geodesic between these points d(u,v) is called the graph distance between u and v
{{cite web}}: Check date values in:|accessdate=(help); External link in|accessdate=|accessdate=at position 11 (help) - ↑ F. Harary, Graph Theory, Addison-Wesley, 1969, p.199.
- ↑ Øystein Ore, Theory of graphs [3rd ed., 1967], Colloquium Publications, American Mathematical Society, p. 104
Category:Graph theory
范畴: 图论
This page was moved from wikipedia:en:Distance (graph theory). Its edit history can be viewed at 图距离/edithistory