图论算法

Question

给定的问题是

鉴于有n个顶点森林，加边缘使之成为一棵树， 直径最小。 我尝试了很多方法，但都没有通过系统测试用例。请提出一些算法来解决这个问题。

这是编辑的链接ncpc.idi.ntnu.no/ncpc2015/ncpc2015slides.pdf问题名称是Adjune the Networks。我无法理解在社论

更新中提供的解决方案：

https://www.quora.com/What-is-the-solution-for-Dreaming-on-IOI-2013

此链接提供了一个顶点v的社论

Answer 1

偏心提到的解决方案的最佳解释，表示为ecc(v)，被定义为ecc(v):=max_u d(u,v)，即作为到图中最远顶点的距离。图G的中心是其中ecc(v)=min_v max_u d(u,v)的任何顶点v，即中心是使偏心率最小化的顶点。

如果合并两棵树（来自不同连接的部件），T1和T2，通过将它们的中心c1和c2之间的边缘，你会得到一棵树T与diam T = max(diam T1, diam T2, 1+rad(T1)+rad(T2))。

以下方法的正确性应该从这些属性中显而易见。

下面是该算法一个想法，把我的头顶部：

• 让T1，T2，...，Tk是包括森林树木。
• 为每棵树Ti计算一个center vertexci。
• 以智能的方式通过在中心之间放置边来连接组件。

当然，现在的问题是如何巧妙地解决最后一颗子弹。直觉上我建议你先连接最大直径的treest（然后更新新树的直径并计算新树的中心）。也许是这样的：

而优先级队列中包含一个以上的树做

• 让T1和T2与最大直径的树。让c1和c2成为他们的中心;
• 连接c1和c2以形成新树T;
• 计算一个新的中心c的T，计算diam T并将T放回优先级队列（可以是使用直径作为密钥的最大堆）。

做

更新。我不确定是先加入最大直径树还是其他方式（即最小直径树首先）。但现在很容易做一个证明的草图（一旦你找到了方法），这是正确的路要走。

更新。如果您首先连接最大（如PDF中所建议的），则数学肯定会经历。