常见概念

常见概念

oriented graph：有向图

bidirectional edges：双向边

平面图：若能将无向图 \(G=(V,E)\) 画在平面上使得任意两条无重合顶点的边不相交，则称 \(G\) 是平面图。

无向正权图上某一点的偏心距：记为 \(ecc(u) = \max \big\{ dist(u, v) \big\}\) ，即以这个点为源，到其他点的所有最短路的最大值。如下图 \(A\) 点，\(ecc(A)\) 即为 \(12\) 。

图的直径：定义为 \(d = \max \big\{ ecc(u) \big\}\) ，即最大的偏心距，亦可以简化为图中最远的一对点的距离。

图的中心：定义为 \(arg=\min \big\{ ecc(u)\big\}\) ，即偏心距最小的点。如下图，图的中心即为 \(B\) 点。

图的绝对中心：可以定义在边上的图的中心。

图的半径：图的半径不同于圆的半径，其不等于直径的一半（但对于绝对中心定义上的直径而言是一半）。定义为 \(r = \min \big\{ ecc(u) \big\}\) ，即中心的偏心距。计算方式：使用全源最短路，计算出所有点的偏心距，再加以计算。