顶点间距离和偏心率

两个顶点之间的距离

它是顶点U和顶点V之间最短路径中的边数。如果有多条路径连接两个顶点，则最短路径被认为是这两个顶点之间的距离。

符号 − d(U,V)

从一个顶点到另一个顶点可能存在任意数量的路径。在这些路径中，您只需要选择最短的一条。

示例

看一下下面的图：

这里，从顶点“d”到顶点“e”的距离，或简称为“de”，是1，因为它们之间有一条边。从顶点“d”到顶点“e”有很多路径：

• da, ab, be
• df, fg, ge
• de（它被认为是顶点之间的距离）
• df, fc, ca, ab, be
• da, ac, cf, fg, ge

顶点的偏心率

从一个顶点到所有其他顶点的最大距离被认为是该顶点的偏心率。

符号 − e(V)

获取从特定顶点到图中所有其他顶点的距离，在这些距离中，偏心率是距离中最大的一个。

示例

在上图中，“a”的偏心率是3。

从“a”到“b”的距离是1（'ab'），

从“a”到“c”的距离是1（'ac'），

从“a”到“d”的距离是1（'ad'），

从“a”到“e”的距离是2（'ab'-'be'）或（'ad'-'de'），

从“a”到“f”的距离是2（'ac'-'cf'）或（'ad'-'df'），

从“a”到“g”的距离是3（'ac'-'cf'-'fg'）或（'ad'-'df'-'fg'）。

因此，偏心率是3，这是从顶点“a”到距离最大的“ag”之间的最大距离。

换句话说，

e(b) = 3

e(c) = 3

e(d) = 2

e(e) = 3

e(f) = 3

e(g) = 3

连通图的半径

所有顶点中最小偏心率被认为是图G的半径。所有顶点到所有其他顶点之间最大距离中的最小值被认为是图G的半径。

符号 − r(G)

在图中所有顶点的偏心率中，连通图的半径是所有这些偏心率中的最小值。

示例 −在上图中，r(G) = 2，这是“d”的最小偏心率。

图的直径

所有顶点中最大偏心率被认为是图G的直径。所有顶点到所有其他顶点之间最大距离中的最大值被认为是图G的直径。

符号 − d(G)

在图中所有顶点的偏心率中，连通图的直径是所有这些偏心率中的最大值。

示例 −在上图中，d(G) = 3；这是最大偏心率。

Mahesh Parahar

更新于：2019年8月23日

4K+ 次浏览

开启你的职业生涯

完成课程获得认证

开始学习