图距离
在图论 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
编者推荐
相关文章
自指机器的奥秘
该文是冯·诺依曼自动机器理论”系列文章的第六篇（下半部分），由集智俱乐部资深粉丝“东方和尚”将全书第一部分翻译成中文，张江做了详细点评。
自指——连接图形与衬底的金带
该文是为“自指机器奥秘”的补充材料，详细地介绍了从语言到计算机程序再到数理逻辑等领域中各种形式的自指现象。除此之外，该文也详细指出了对角线删除法则与自指等概念之间的联系。
集智相关课程
图网络解决优化问题——图网络读书会
图神经网络是深度学习领域的前沿热点议题，尤其是图网络（GraphNetworks）提出以来，深度学习有了实现因果推理的潜力。为了持续追踪相关领域的前沿进展，集智俱乐部联合北师大系统科学学院张江课题组，组织了以图网络为主题的线上读书会，研讨最新论文，孕育研究思路。本系列课程为图网络论文解读活动“图网络解决优化问题”篇。
本中文词条作者为Ryan翻译，CecileLi审校，薄荷编辑，欢迎在讨论页面留言。
本词条内容源自wikipedia及公开资料，遵守 CC3.0协议。