计算图的直径,如果按照定义直接计算,复杂度会是$O(n^3)$。实际通常采取估算的方法,估算过程会涉及到一个重要的概念——离心率(eccentricity)。离心率与直径有一些推论,这里集中证明,作为备忘。以下推论适用全联通图,无向/有向,无权/有权均可,但是权重需要非负。

定义1 离心率

对任意点$v$的离心率是该点到图中其他点最短距离的最大值,

\[\epsilon(v) = \max_{w \in V} dist(v,w)\]

其中$dist(v,w)$是点$v$到$w$最短距离,$V$是节点集合。

定义2 直径$\Delta(G)$

直径是两点最短距离中的最大值,根据离心率定义,可以如下表示

\[\Delta(G) = \max_{v \in V}\epsilon(v)\]

根据上面定义,离心率和直径建立了联系。

推论1 开阔的直径上下界

\[\epsilon(v) \le \Delta(G) \le 2*\epsilon(v)\]

证明:

下界根据定义容易证明,省略。证明上界,设直径由点$x$和$y$确定,根据离心率定义,容易推得如下

\[\Delta(G) = dist(x,y) \le dist(x,v)+dist(v,y) \le 2 *\epsilon(v)\]

证毕!

推论2 离心率上下界

$\epsilon(v)$是特定点$v$离心率,$w(\in V)$是任意其他点(包括$v$),$v$相对于$w$固定

\[\max(\epsilon(v) - dist(v,w), dist(v,w)) \le \epsilon(w) \le dist(w,v) + \epsilon(v)\]

证明:

证明上界,设$x$是$w$离心率的另一个端点,(可以想象为两点之间直线最短,如果绕道x连接两点,距离必然变长)

\[\epsilon(w) \le dist(w,v)+dist(v,x) \le d(w,v) + \epsilon(v)\]

证明下界,其中$dist(v,w)$与$\epsilon(w)$的关系易得,略去。$\epsilon(v)-dist(v,w)$与$\epsilon(w)$关系,可以将$-dist(v,w)$移到不等式另外一边,得到形式与上届一致,证明方法一致,省略。

证毕!

定义3 $\epsilon_L(v)$为当前点离心率下界,$\epsilon_U(v)$为离心率上界。

推论3 紧凑的直径上下界

\[\max_{v \in V}\epsilon_L(v)\le \Delta(G) \le \min(\max_{v \in V}\epsilon_U(v), 2*\min_{v \in V}\epsilon_U(v))\]

证明:

根据$推论1$,很容易证明,省略。

证毕!