algorithm - 图论算法

Question

给定的问题是

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

这是社论的链接ncpc.idi.ntnu.no/ncpc2015/ncpc2015slides.pdf问题名称是 Adjoin the Networks。我无法理解社论中提供的解决方案

更新:

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

这个链接为社论中提到的解决方案提供了最好的解释

Answer 1

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

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

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

这是算法的一个想法，出乎我的意料:

• 让T1 , T2 , ..., Tk是构成森林的树木。
• 计算一个center vertex ci对于每棵树 Ti .
• 通过以智能方式在中心之间放置边缘来连接组件。

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

while优先级队列包含不止一棵树do

• 让T1和 T2是直径最大的树；让 c1和 c2成为他们的中心；
• 连接c1和 c2形成一棵新树T ;
• 计算一个新的中心c的 T , 计算 diam T然后放T回到优先级队列(可以是最大堆，使用直径作为键)。

完成

更新。我不确定是先加入最大直径的树还是相反(即首先加入最小直径的树)。但是现在很容易画出证明的草图(一旦你弄清楚要走哪条路)这是正确的路要走。

更新。如果您先连接最大的(如 PDF 中的建议)，那么数学肯定会成功。