问图论算法

EN

表示为ecc(v)的顶点v的偏心率被定义为ecc(v):=max_u d(u,v)，即到图中最远顶点的距离。图G的中心是对其具有ecc(v)=min_v max_u d(u,v)的任何顶点v，即中心是最小化偏心率的顶点。

如果您合并两个树(来自不同的连接组件)，T1和T2，通过在它们的中心c1和c2之间放置一条边，您将得到一个带有diam T = max(diam T1, diam T2, 1+rad(T1)+rad(T2))的树T。

从这些属性可以明显看出下面方法的正确性。

这里有一个算法的想法，不是我想出来的：

通过以智能的方式在中心之间放置边，让

• T1，T2，...，Tk成为构成每个树组件的forest.

• compute a center vertex ci的树。

当然，现在的问题是如何巧妙地解决最后一颗子弹。直观地说，我建议您首先连接直径最大的树(然后更新新树的直径并计算新树的中心)。可能是这样的：

while优先级队列包含多个树do

• 让T1和T2是直径最大的树；让c1和c2作为它们的c1和c2，以形成一棵新的树和<
• d44的新中心堆，计算diam T并将T放回优先级队列(可以是以直径为键的最大堆)。

done

更新。我不确定是先加入直径最大的树，还是反过来加入(即先加入直径最小的树)。但现在很容易做一个证明的草图(一旦你弄清楚该走哪条路)，证明这是正确的方式。

如果你首先连接最大的(如中所建议的)，那么这个数学运算肯定会通过。