用户:EtaoinWu/距离 (图论)
外观
在图论中,一张图两个点之间的距离是指他们之间最短路径的边数。这也被称为图的测地距离。[1] 两个点之间可能有多条最短路径。[2] 如果两个顶点之间没有路径(即他们属于不同的连通分量),那么按照传统它们距离被定义为无穷大。
在有向图的情况中,距离被定义为两个顶点 和 之间最短路径的边数(如果存在)[3]。注意到,与无向图不同, 不必与 相等。
相关概念
[编辑]一个利用图的距离定义的测度空间被称为图测度。当且仅当这张无向图是连通图时这形成了一个测度空间。
一个结点的偏心率 被定义为 和其它顶点的距离的最大值,也被认为是这个点离其最远点的距离。
一个图的半径 被定义为最小的偏心率:。
一张图的直径 被定义为最大的偏心率,即最大的两点距离:。
参考资料
[编辑]- ^ 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.
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. [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.