集智百科 - 复杂系统|人工智能|复杂科学|复杂网络|自组织

更改

图距离 (查看源代码)

2020年9月2日 (三) 21:54的版本

添加571字节 、 2020年9月2日 (三) 21:54
无编辑摘要
第9行： 第9行：  
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>{{cite journal |last=Bouttier  |first=Jérémie |author2=Di Francesco,P. |author3=Guitter, E. |date=July 2003   
 
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>{{cite journal |last=Bouttier  |first=Jérémie |author2=Di Francesco,P. |author3=Guitter, E. |date=July 2003   
   −
在图论的数学领域中，图中两个顶点之间的距离是最短路径(也称为图测地线)中连接它们的边的数目。这也被称为测地距离。3 = Guitter，e. | date = July 2003
+
在'''<font color="#ff8000">图论 Graph Theory</font>'''的数学领域中，图中两个顶点之间的距离是'''<font color="#ff8000">最短路径 Shortest Path</font>'''(也称为'''<font color="#ff8000">图测地线 Graph Geodesic</font>''')中连接它们的边的数目。这也被称为'''<font color="#ff8000">测地距离 Geodesic Distance</font>'''。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|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|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>
第47行： 第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.
   −
如果两个顶点间没有路径连接，也就是说，如果它们属于不同的连通分支，那么按照惯例，距离被定义为无穷大。
+
如果两个顶点间没有路径连接，也就是说，如果它们属于不同的'''<font color="#ff8000">连通分支 Connected Components</font>'''，那么按照惯例，距离被定义为无穷大。
      第65行： 第65行：  
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.
   −
一个度量空间定义在一个集合上的点集合上，该集合上的图的距离称为图度量。
+
一个'''<font color="#ff8000">度量空间 Metric Space</font>'''定义在一个集合上的点集合上，该集合上的图的距离称为'''<font color="#ff8000">图度量 Graph Metric</font>'''。
    
The vertex set (of an undirected graph) and the distance function form a metric space, if and only if the graph is [[connected (graph theory)|connected]].
 
The vertex set (of an undirected graph) and the distance function form a metric space, if and only if the graph is [[connected (graph theory)|connected]].
第79行： 第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.
   −
一个顶点的偏心率是它与其他顶点之间最大的距离。它可以被认为是一个节点距离图中离它最远的节点有多远。
+
一个顶点的'''<font color="#ff8000">偏心率 Eccentricity</font>'''是它与其他顶点之间最大的距离。它可以被认为是一个节点距离图中离它最远的节点有多远。
      第119行： 第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 是伪外围的,
+
一个'''<font color="#ff8000">伪周边顶点 Pseudo-Peripheral Vertex</font>'''具有这样的属性: 对于任何顶点 <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>.
第133行： 第133行：  
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.
   −
图的顶点按照它们与给定顶点之间的距离划分成子集的过程称为图的层次结构。
+
图的顶点按照它们与给定顶点之间的距离划分成子集的过程称为'''<font color="#ff8000">图的层次结构 Level Structure of The Graph</font>'''。
      第141行： 第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.
   −
对于每一对顶点，有一条唯一的最短路径连接它们，这样的图称为大地图。例如，所有的树都是大地图。
+
对于每一对顶点，有一条唯一的最短路径连接它们，这样的图称为'''<font color="#ff8000">测地图 Geodetic Graph</font>'''。例如，所有的树都是测地图。
      第157行： 第157行：  
# Choose a vertex <math>u</math>.
 
# Choose a vertex <math>u</math>.
   −
Choose a vertex <math>u</math>.
+
Choose a vertex <math>u</math>.
    
选择顶点<math>u</math>。
 
选择顶点<math>u</math>。
第163行： 第163行：  
# 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>是一个最小度的顶点。
第169行： 第169行：  
# 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>是一个伪周边顶点。
Ryan
75

个编辑

取自“https://wiki.swarma.org/index.php/特殊:移动版差异/13618”