跳转到内容

距离 (图论)

维基百科,自由的百科全书

图论中,一张无向图里,两顶点之间的距离是指他们之间最短路径(英語:shortest path[註 1]的长度,两顶点之间的距离也被称为测地距离(英語:geodesic distance[1]。需要注意的是两个顶点之间可能有多条最短路径[2],如果两个顶点之间不存在路径(即他们属于不同的连通分量),那么按照传统它们距离被定义为无穷大。

有向图中,如果从顶点 到顶点 存在有向路径(英語:directed path),那么距离 被定义为从顶点  到顶点  之间最短有向路径的长度[3]。不同于无向图,在有向图中 不一定和 相等[註 2],甚至有可能出现从顶点 到顶点 存在有向路径,而从顶点 到顶点 却不存在有向路径的情况。

相关概念

[编辑]

一个顶点 偏心率  被定义为 和其它顶点的距离的最大值,也即是这个点和离其最远点的距离[4]

一张图的半径  被定义为最小的偏心率:[4]

一张图的直径  被定义为最大的偏心率:,也即最远的两点间的距离。若要求得一张图的直径,首先要求得任意两点之间的最短路径,在这些所有的最短路径中,取其长度最长者,即是这张图的直径[4]

一张半径为 的图的中心点是所有的偏心率为 顶点。若 是一个中心点,那么可用数学符号表示为 。一张图可以有不止一个中心点[4]

边缘点和中心点的定义类似。一张直径为 的图的边缘点是所有的偏心率为 的顶点。若 是一个边缘点,那么 。一张图可以有多个边缘点[4]

例子

[编辑]
图1
图2
图3

有向图

[编辑]

在图1中,顶点 到顶点 的距离 ,而顶点 到顶点 的距离

直径和半径

[编辑]
顶点
偏心率 3 3 2 2 2 3

在图2中,例如,距离顶点 的最远点是顶点 ,那么 。每一个顶点的偏心率如上表所示,所以图1的半径为2,而直径为3。

加权图

[编辑]

导言中定义的顶点间的距离也可以被扩展至加权图[註 3](英語:weighted graph)。如在图3中,顶点3到顶点5的距离为

参见

[编辑]

注释

[编辑]
  1. ^ 两点间的最短路径也被称为图的测地线(英語:graph geodesic)。
  2. ^ 见例1。
  3. ^ 加权图的含义是每一条边可以有各自的长度。

参考资料

[编辑]
  1. ^ Bouttier, Jérémie; Di Francesco,P.; Guitter, E. Geodesic distance in planar graphs. Nuclear Physics B. July 2003, 663 (3): 535–567 [2008-04-23]. doi:10.1016/S0550-3213(03)00355-9. (原始内容存档于2008-10-04). 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. at MathWorld--A Wolfram Web Resource. Wolfram Research, Inc. [2008-04-23]. (原始内容存档于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: 199. 
  4. ^ 4.0 4.1 4.2 4.3 4.4 Chartrand G., Johns G., Oellermann O.R. On Peripheral Vertices in Graphs. Bodendiek R., Henn R. (编). Topics in Combinatorics and Graph Theory. Physica-Verlag HD. 1990. 

参考文献 

[编辑]