7,129
个编辑
更改
跳到导航
跳到搜索
第4行：
第4行： + − In the [[mathematics|mathematical]] field of [[graph theory]], the '''distance''' between two [[vertex (graph theory)|vertices]] in a [[Graph (discrete mathematics)|graph]] is the number of edges in a [[shortest path problem|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 − 此处翻译编辑视图中有阅读视图无显示。 − 在'''[[图论 Graph Theory]]'''的数学领域定义中，图中两个顶点之间的距离是'''最短路径 Shortest Path'''(也称为'''<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> − − 特别地，在两个顶点之间可能有一条及以上的最短路径 − − {{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 − − { 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 − − |last=Weisstein |first=Eric W. |authorlink=Eric W. Weisstein |work=MathWorld--A Wolfram Web Resource − − − − |publisher= Wolfram Research − − |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 }} − − |quote=The length of the graph geodesic between these points d(u,v) is called the graph distance between u and v }} − − − − </ref> If there is no path connecting the two vertices, i.e., if they belong to different [[connected component (graph theory)|connected component]]s, 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.<ref>F. Harary, Graph Theory, Addison-Wesley, 1969, p.199.</ref> 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>一致，而且可能一个是符合定义的，而另一个不符合。 − − − − ==Related concepts 相关概念== + + − + + − − The vertex set (of an undirected graph) and the distance function form a metric space, if and only if the graph is 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>'''是它与其他顶点之间最大的距离。这可以用来判断一个节点距离图中最远节点的距离。 + − 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> 。 + − 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 problem|shortest path]] between each pair of [[vertex (graph theory)|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>。要找到图的直径，首先要找到每对顶点之间的最短路径。这些路径的最大长度是图的直径。 − − − − 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> 。 − − − − 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>是次要的。 第122行：
第48行： − + 第128行：
第54行： − 如果对于每个顶点 v 都有<math>d(u,v) = \epsilon(u)</math>保持<math>\epsilon(u)=\epsilon(v)</math>。+
无编辑摘要
{{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}}
{{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>'''，那么这两点间的距离就被定义为无穷大。
在[[有向图 directed graph]]中，顶点 <math>u</math>和<math>v</math>之间的距离<math>d(u,v)</math>被定义为从<math>u</math> 到 <math>v</math>之间由弧组成的最短有向路径的长度，但前提是至少存在一条这样的路径。<ref>F. Harary, Graph Theory, Addison-Wesley, 1969, p.199.</ref> 与无向图不同， <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'''.
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>'''。
根据'''<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]].
当且仅当图是连通的时，(无向图的)顶点集和距离函数构成度量空间。
当且仅当图是连通的时，(无向图的)顶点集和距离函数构成度量空间。
一个[[顶点 vertex]]<math>v</math>的'''<font color="#ff8000">离心率 Eccentricity</font>''' <math>\epsilon(v)</math>是它与其他顶点之间最大的距离,用<math>\epsilon(v) = \max_{u \in V}d(v,u)</math>表示。
这可以用来判断一个节点距离图中最远节点的距离。
图的'''半径 radius'''<math>r</math>是任何顶点的最小离心率，用<math>r = \min_{v \in V} \epsilon(v) = \min_{v \in V}\max_{u \in V}d(v,u)</math> 表示。
图的'''直径 diameter''' <math>d</math>是图中任何顶点的最大离心率。即<math>d</math> 是任何一对顶点之间最大的距离，<math>d = \max_{v \in V}\epsilon(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>是次要的。
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 是伪外围的/伪周边的,
'''<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>。
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>.
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>.