75
个编辑
更改
跳到导航
跳到搜索
第9行：
第9行： − 在图论的数学领域中，图中两个顶点之间的距离是最短路径(也称为图测地线)中连接它们的边的数目。这也被称为测地距离。3 = Guitter，e. | date = July 2003+ 第47行：
第47行： − 如果两个顶点间没有路径连接，也就是说，如果它们属于不同的连通分支，那么按照惯例，距离被定义为无穷大。+ 第65行：
第65行： − 一个度量空间定义在一个集合上的点集合上，该集合上的图的距离称为图度量。+ 第79行：
第79行： − 一个顶点的偏心率是它与其他顶点之间最大的距离。它可以被认为是一个节点距离图中离它最远的节点有多远。+ 第119行：
第119行： − 一个伪周边顶点具有这样的属性: 对于任何顶点 <math>u</math>，如果<math>v</math>离<math>u</math>越远，那么 <math>u</math>离 <math>v</math>越远。形式上，一个顶点 u 是伪外围的,+ 第133行：
第133行： − 图的顶点按照它们与给定顶点之间的距离划分成子集的过程称为图的层次结构。+ 第141行：
第141行： − 对于每一对顶点，有一条唯一的最短路径连接它们，这样的图称为大地图。例如，所有的树都是大地图。+ 第157行：
第157行： − Choose a vertex <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.+ 第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.+
无编辑摘要
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
在'''<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>
</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>'''，那么按照惯例，距离被定义为无穷大。
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]].
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>'''是它与其他顶点之间最大的距离。它可以被认为是一个节点距离图中离它最远的节点有多远。
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,
一个'''<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>.
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>'''。
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>'''。例如，所有的树都是测地图。
# Choose a vertex <math>u</math>.
# 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.
在所有尽可能远离<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.
如果<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>是一个伪周边顶点。