顶点之间的距离和偏心距

两个顶点之间的距离

它是顶点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；这是最大的偏心率。