“图距离”的版本间的差异

来自集智百科 - 复杂系统|人工智能|复杂科学|复杂网络|自组织
跳到导航 跳到搜索
第1行： 第1行：
−
本词条由Ryan初步翻译
+
{{#seo:
−
由CecileLi初步审校
+
|keywords=图论,图测地线,测地距离
−
 
+
|description=最短路径,图度量,中心顶点，边缘顶点。
−
{{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}}
+
}}
−
 
 
 
在'''[[图论 Graph Theory]]'''的数学领域定义中，图中两个顶点之间的距离是'''最短路径 Shortest Path'''(也称为'''<font color="#ff8000">图测地线 Graph Geodesic</font>''')中连接它们的边的数目。这也被称为'''<font color="#ff8000">测地距离 Geodesic Distance</font>'''。<ref>{{cite journal |last=Bouttier  |first=Jérémie |author2=Di Francesco,P. |author3=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|doi=10.1016/S0550-3213(03)00355-9|arxiv=cond-mat/0303272 }}</ref>但，两个顶点之间可能有不止一条最短路径。<ref>{{cite web |url=http://mathworld.wolfram.com/GraphGeodesic.html |title=Graph Geodesic |accessdate= 2008-04-23|last=Weisstein |first=Eric W. |authorlink=Eric W. Weisstein |work=MathWorld--A Wolfram Web Resource |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 }}</ref>一般地，如果两个顶点间没有路径连接，也就是说，如果它们属于不同的'''<font color="#ff8000">连通分支 Connected Components</font>'''，那么这两点间的距离就被定义为无穷大。
 
在'''[[图论 Graph Theory]]'''的数学领域定义中，图中两个顶点之间的距离是'''最短路径 Shortest Path'''(也称为'''<font color="#ff8000">图测地线 Graph Geodesic</font>''')中连接它们的边的数目。这也被称为'''<font color="#ff8000">测地距离 Geodesic Distance</font>'''。<ref>{{cite journal |last=Bouttier  |first=Jérémie |author2=Di Francesco,P. |author3=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|doi=10.1016/S0550-3213(03)00355-9|arxiv=cond-mat/0303272 }}</ref>但，两个顶点之间可能有不止一条最短路径。<ref>{{cite web |url=http://mathworld.wolfram.com/GraphGeodesic.html |title=Graph Geodesic |accessdate= 2008-04-23|last=Weisstein |first=Eric W. |authorlink=Eric W. Weisstein |work=MathWorld--A Wolfram Web Resource |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 }}</ref>一般地，如果两个顶点间没有路径连接，也就是说，如果它们属于不同的'''<font color="#ff8000">连通分支 Connected Components</font>'''，那么这两点间的距离就被定义为无穷大。
  
第29行： 第28行：
  
  
−
在半径为<math>r</math>的图中，'''中心顶点 central vertex'''是离心率为 <math>r</math>顶点，即距离等于半径的顶点，或者等效于一个能够满足<math>\epsilon(v) = r</math> 的顶点<math>v</math>。
+
在半径为<math>r</math>的图中，'''中心点 central vertex'''是离心率为 <math>r</math>顶点，即距离等于半径的顶点，或者等效于一个能够满足<math>\epsilon(v) = r</math> 的顶点<math>v</math>。
  
  
−
在直径为<math>d</math>的图中，'''边缘顶点 peripheral vertex''' 是离心率为 <math>d</math>顶点，即距离等于直径的顶点。定义，如果<math>\epsilon(v) = d</math>，<math>v</math>是次要的。
+
在直径为<math>d</math>的图中，'''边缘点 peripheral vertex''' 是离心率为 <math>d</math>顶点，即距离等于直径的顶点。定义，如果<math>\epsilon(v) = d</math>，<math>v</math>是次要的。
  
  
−
'''<font color="#ff8000">伪周边顶点 Pseudo-Peripheral Vertex</font>''' <math>v</math>具有这样的属性：对于任何顶点 <math>u</math>，如果<math>v</math>距离<math>u</math>越远，那么<math>u</math>距离 <math>v</math>越远。定义，如果一个顶点''u''对于每个顶点''v''都有<math>d(u,v) = \epsilon(u)</math>保持<math>\epsilon(u)=\epsilon(v)</math>，则''u''是伪周边顶点。
+
'''<font color="#ff8000">伪边缘点 Pseudo-Peripheral Vertex</font>''' <math>v</math>具有这样的属性：对于任何顶点 <math>u</math>，如果<math>v</math>距离<math>u</math>越远，那么<math>u</math>距离 <math>v</math>越远。定义，如果一个顶点''u''对于每个顶点''v''都有<math>d(u,v) = \epsilon(u)</math>保持<math>\epsilon(u)=\epsilon(v)</math>，则''u''是伪周边顶点。
  
  
第41行： 第40行：
  
  
−
对于每对顶点，都有一条连接它们的唯一最短路径的图，则将该图称为'''<font color="#ff8000">测地图 geodetic graph</font>'''。例如，所有的树状图都是测地图。<ref>[[Øystein Ore]], Theory of graphs [3rd ed., 1967], Colloquium Publications, American Mathematical Society,p.104</ref>
+
对于每对顶点，都有一条连接它们的唯一最短路径的图，则将该图称为'''<font color="#ff8000">测地图 geodetic graph</font>'''。例如，所有的树状图都是测地图。<ref>Øystein Ore, Theory of graphs [3rd ed., 1967], Colloquium Publications, American Mathematical Society,p.104</ref>
  
 
<br>
 
<br>
第69行： 第68行：
  
  
−
 
+
本词条由Ryan初步翻译
 +
由CecileLi初步审校
  
  
  
 
[[Category:图论]]
 
[[Category:图论]]

2020年10月30日 (五) 17:08的版本

在图论 Graph Theory的数学领域定义中，图中两个顶点之间的距离是最短路径 Shortest Path(也称为图测地线 Graph Geodesic)中连接它们的边的数目。这也被称为测地距离 Geodesic Distance。[1]但，两个顶点之间可能有不止一条最短路径。[2]一般地，如果两个顶点间没有路径连接，也就是说，如果它们属于不同的连通分支 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]之间由弧组成的最短有向路径的长度，但前提是至少存在一条这样的路径。[3] 与无向图不同， [math]\displaystyle{ d(u,v) }[/math] 不一定与[math]\displaystyle{ d(v,u) }[/math]一致，而且可能一个是符合定义的，而另一个不符合。


相关概念

一个由点集根据图中点集的距离定义的度度量空间 metric space被称为图度量 Graph Metric。


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


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


伪边缘点 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]，则u是伪周边顶点。


依据图的顶点到给定起始顶点的距离将集合划分成多个子集称为图的层次结构 Level Structure of The Graph。


对于每对顶点，都有一条连接它们的唯一最短路径的图，则将该图称为测地图 geodetic graph。例如，所有的树状图都是测地图。[4]


寻找伪周边的算法 Algorithm for finding pseudo-peripheral vertices

通常,外围稀疏矩阵 sparse matrix算法需要具有高离心率的起始点。外围顶点会是首选，但往往难以计算。在大多数情况下，可以使用伪周边顶点。通过以下算法，能轻松找到伪周边顶点:

  1. 选择顶点 [math]\displaystyle{ u }[/math]。
  2. 在所有尽可能远离[math]\displaystyle{ u }[/math]的顶点中，让[math]\displaystyle{ v }[/math]是一个最小度的顶点。
  3. 如果[math]\displaystyle{ \epsilon(v) \gt \epsilon(u) }[/math]，那么令 [math]\displaystyle{ u=v }[/math] 并重复步骤2，否则 [math]\displaystyle{ u }[/math]是一个伪周边顶点。

参见=

参考文献

  1. ↑ Bouttier, Jérémie; Di Francesco,P.; Guitter, E. (July 2003). "Geodesic distance in planar graphs". Nuclear Physics B. 663 (3): 535–567. arXiv:cond-mat/0303272. doi:10.1016/S0550-3213(03)00355-9. By distance we mean here geodesic distance along the graph, namely the length of any shortest path between say two given faces
  2. ↑ 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
  3. ↑ F. Harary, Graph Theory, Addison-Wesley, 1969, p.199.
  4. ↑ Øystein Ore, Theory of graphs [3rd ed., 1967], Colloquium Publications, American Mathematical Society,p.104


本词条由Ryan初步翻译 由CecileLi初步审校

取自“https://wiki.swarma.org/index.php?title=图距离&oldid=17445”