集智百科 - 复杂系统|人工智能|复杂科学|复杂网络|自组织

图距离 Distance (graph theory)

在图论 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。 

--Ricky 是我功力太渣吗，我读不懂这句话啊......

当且仅当图是连接的时，（无向图的）顶点集和距离函数构成度量空间。


顶点[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算法需要具有高离心率的起始点。边缘点会是首选，但往往难以计算。在大多数情况下，可以使用伪边缘点。通过以下算法，能轻松找到伪边缘点:

  1. 选择顶点 [math]\displaystyle{ u }[/math]。
  2. 在所有尽可能远离[math]\displaystyle{ u }[/math]的顶点中，让[math]\displaystyle{ v }[/math]是一个最小度的顶点。
  3. 如果[math]\displaystyle{ \epsilon(v) \gt \epsilon(u) }[/math]，那么令 [math]\displaystyle{ u=v }[/math] 并重复步骤2，否则 [math]\displaystyle{ u }[/math]是一个伪边缘点。

参见

参考文献

  1. ↑ 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
  2. ↑ 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
  3. ↑ F. Harary, Graph Theory, Addison-Wesley, 1969, p.199.
  4. ↑ Øystein Ore, Theory of graphs [3rd ed., 1967], Colloquium Publications, American Mathematical Society,p.104


编者推荐

集智相关文章

搭建图与网络之间的桥梁：网络科学的下一个突破在哪里？

网络是认识世界的强力手段，图论则是网络科学的数学基础，但两个领域近年来的结合并不密切。来自中欧大学的网络科学研究者，在Nature子刊Communications Physics上发表文章 Bridging the gap between graphs and networks，讨论如何将网络科学解决现实问题的经验引入图论运营，同时将图论中的前沿数学成果带入网络科学。在数据驱动下，架起图与网络之间的桥梁，网络科学将有机会迎来更大的突破。


集智课程

图网络解决优化问题——图网络读书会

图神经网络是深度学习领域的前沿热点议题，尤其是图网络（GraphNetworks）提出以来，深度学习有了实现因果推理的潜力。为了持续追踪相关领域的前沿进展，集智俱乐部联合北师大系统科学学院张江课题组，组织了以图网络为主题的线上读书会，研讨最新论文，孕育研究思路。本系列课程为图网络论文解读活动“图网络解决优化问题”篇。


本中文词条作者为Ryan翻译，CecileLi审校，薄荷编辑，欢迎在讨论页面留言。

本词条内容源自wikipedia及公开资料，遵守 CC3.0协议。

取自“https://wiki.swarma.org/index.php?title=图距离_Distance_(graph_theory)&oldid=21060”