图距离
在图论 Graph Theory的数学领域定义中，图中两个顶点之间的距离是最短路径 Shortest Path（也称为图测地线 Graph Geodesic）中连接它们的边的数目。这也被称为测地距离 Geodesic Distance。[1]但，两个顶点之间可能有不止一条最短路径。[2]一般地，如果两个顶点间没有路径连接，也就是说，如果它们属于不同的连通分支 Connected Components，那么这两点间的距离就被定义为无穷大。
在有向图 directed graph中，顶点 [math]\displaystyle{ u }[/math]和[math]\displaystyle{ v }[/math]之间的距离[math]\displaystyle{ d(u,v) }[/math]被定义为从[math]\displaystyle{ u }[/math] 到 [math]\displaystyle{ v }[/math]之间由弧组成的最短有向路径的长度，但前提是至少存在一条这样的路径。[3] 与无向图不同， [math]\displaystyle{ d(u,v) }[/math] 不一定与[math]\displaystyle{ d(v,u) }[/math]一致，而且可能一个是符合定义的，而另一个不符合。
相关概念
一个由点集根据图中点集的距离定义的度度量空间 metric space被称为图度量 Graph Metric。
当且仅当图是连接的时，（无向图的）顶点集和距离函数构成度量空间。
顶点[math]\displaystyle{ v }[/math]的离心率 Eccentricity [math]\displaystyle{ \epsilon(v) }[/math]是它与其他顶点之间最大的距离,用[math]\displaystyle{ \epsilon(v) = \max_{u \in V}d(v,u) }[/math]表示。
这可以用来判断一个节点距离图中最远节点的距离。
图的半径 radius[math]\displaystyle{ r }[/math]是任何顶点的最小离心率，用[math]\displaystyle{ r = \min_{v \in V} \epsilon(v) = \min_{v \in V}\max_{u \in V}d(v,u) }[/math] 表示。
图的直径 diameter [math]\displaystyle{ d }[/math]是图中任何顶点的最大离心率。即[math]\displaystyle{ d }[/math] 是任何一对顶点之间最大的距离，[math]\displaystyle{ d = \max_{v \in V}\epsilon(v) }[/math]。要找到图的直径，首先要找到每对顶点之间的最短路径。这些路径的最大长度是图的直径。
在半径为[math]\displaystyle{ r }[/math]的图中，中心点 central vertex是离心率为 [math]\displaystyle{ r }[/math]顶点，即距离等于半径的顶点，或者等效于一个能够满足[math]\displaystyle{ \epsilon(v) = r }[/math] 的顶点[math]\displaystyle{ v }[/math]。
在直径为[math]\displaystyle{ d }[/math]的图中，边缘点 peripheral vertex 是离心率为 [math]\displaystyle{ d }[/math]顶点，即距离等于直径的顶点。定义，如果[math]\displaystyle{ \epsilon(v) = d }[/math]，[math]\displaystyle{ v }[/math]是次要的。
伪边缘点 Pseudo-Peripheral Vertex [math]\displaystyle{ v }[/math]具有这样的属性：对于任何顶点 [math]\displaystyle{ u }[/math]，如果[math]\displaystyle{ v }[/math]距离[math]\displaystyle{ u }[/math]越远，那么[math]\displaystyle{ u }[/math]距离 [math]\displaystyle{ v }[/math]越远。定义，如果一个顶点u对于每个顶点v都有[math]\displaystyle{ d(u,v) = \epsilon(u) }[/math]保持[math]\displaystyle{ \epsilon(u)=\epsilon(v) }[/math]，则u是伪周边顶点。
依据图的顶点到给定起始顶点的距离将集合划分成多个子集称为图的层次结构 Level Structure of The Graph。
对于每对顶点，都有一条连接它们的唯一最短路径的图，则将该图称为测地图 geodetic graph。例如，所有的树状图都是测地图。[4]
寻找伪边缘点的算法 Algorithm for finding pseudo-peripheral vertices
通常,外围稀疏矩阵 sparse matrix算法需要具有高离心率的起始点。外围顶点会是首选，但往往难以计算。在大多数情况下，可以使用伪周边顶点。通过以下算法，能轻松找到伪周边顶点:
- 选择顶点 [math]\displaystyle{ u }[/math]。
- 在所有尽可能远离[math]\displaystyle{ u }[/math]的顶点中，让[math]\displaystyle{ v }[/math]是一个最小度的顶点。
- 如果[math]\displaystyle{ \epsilon(v) \gt \epsilon(u) }[/math]，那么令 [math]\displaystyle{ u=v }[/math] 并重复步骤2，否则 [math]\displaystyle{ u }[/math]是一个伪周边顶点。
参见=
- 距离矩阵 Distance matrix
- 电阻距离 Resistance distance
- 介数中心性 Betweenness centrality
- 中心性 Centrality
- 封闭性 Closeness
- 图的度直径问题 Degree diameter problem（离散数学和有向图）
- 指标图 Metric graph
参考文献
- ↑ Bouttier, Jérémie; Di Francesco,P.; Guitter, E. (July 2003). "Geodesic distance in planar graphs". Nuclear Physics B. 663 (3): 535–567. arXiv:cond-mat/0303272. doi:10.1016/S0550-3213(03)00355-9.
By distance we mean here geodesic distance along the graph, namely the length of any shortest path between say two given faces
- ↑ Weisstein, Eric W. "Graph Geodesic". MathWorld--A Wolfram Web Resource. Wolfram Research. Retrieved 2008-04-23.
The length of the graph geodesic between these points d(u,v) is called the graph distance between u and v
- ↑ F. Harary, Graph Theory, Addison-Wesley, 1969, p.199.
- ↑ Øystein Ore, Theory of graphs [3rd ed., 1967], Colloquium Publications, American Mathematical Society,p.104
本词条由Ryan初步翻译 由CecileLi初步审校