更改

{{#seo:

|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>'''，那么这两点间的距离就被定义为无穷大。

在半径为<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''是伪周边顶点。

对于每对顶点，都有一条连接它们的唯一最短路径的图，则将该图称为'''<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>

 

[[Category:图论]]

[[Category:图论]]