526
个编辑
更改
无编辑摘要
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
此处翻译编辑视图中有阅读视图无显示。
在'''<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>
Notice that there may be more than one shortest path between two vertices.<ref>
Notice that there may be more than one shortest path between two vertices.<ref>
特别地，在两个顶点之间可能有一条及以上的最短路径
{{cite web |url=http://mathworld.wolfram.com/GraphGeodesic.html |title=Graph Geodesic |accessdate= 2008-04-23
{{cite web |url=http://mathworld.wolfram.com/GraphGeodesic.html |title=Graph Geodesic |accessdate= 2008-04-23
</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>'''，那么这两点间的距离就被定义为无穷大。
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>一致，而且可能一个是符合定义的，而另一个不是。
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>'''是它与其他顶点之间最大的距离。它可以被认为是一个节点距离图中离它最远的节点有多远。
一个顶点的'''<font color="#ff8000">离心率 Eccentricity</font>'''是它与其他顶点之间最大的距离。这可以用来判断一个节点距离图中最远节点的距离。
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 = \min_{v \in V} \epsilon(v) = \min_{v \in V}\max_{u \in V}d(v,u)</math> 。
图的半径<math>r</math>是任何顶点的最小离心率，用符号可表示为<math>r = \min_{v \in V} \epsilon(v) = \min_{v \in V}\max_{u \in V}d(v,u)</math> 。
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 = \max_{v \in V}\epsilon(v)</math>。要找到图的直径，首先要找到每对顶点之间的最短路径。这些路径的最大长度是图的直径。
图的直径 <math>d</math>是图中任何顶点的最大离心率。也就是说， <math>d</math> 是任何一对顶点之间最大的距离，或者，<math>d = \max_{v \in V}\epsilon(v)</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>.
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>&mdash，也就是说，达到半径的顶点，或者等效于一个顶点<math>v</math>，这样 <math>\epsilon(v) = r</math> 。
半径<math>r</math>图中的中心顶点的离心率是 <math>r</math>&mdash，也就是说，距离为半径的顶点，或者等效于一个顶点<math>v</math>，这样 <math>\epsilon(v) = r</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>.
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>\epsilon(v) = d</math>，<math>v</math>是次要的。
直径<math>d</math>图中的边缘顶点与其他顶点之间的距离为<math>d</math>，即距离为直径的顶点。形式上，如果<math>\epsilon(v) = d</math>，<math>v</math>是次要的。
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>.