圖論算法

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中所建議的），則數學肯定會經歷。