algorithm - 使用 n 个节点之间的 k 个链接最小化总距离

Question

我遇到了以下问题，我不知道解决方案，也找不到“查找”术语来进一步调查。

假设我们有 N 个有序节点 (n_1,n_2....n_N)，每个节点之间的固定距离为 1。所以距离(n_1，n_N)= N-1。现在我们可以连接任意两个节点，从而有效地将它们的距离减少到 1。假设我们可以有 k 个这样的连接。

问题是:我们如何选择连接哪些节点以最小化任意两个节点之间的总距离？

这个问题是某个经过充分研究的问题的已知变体吗？是否存在有效的解决方案(或者我们只想最小化任意两个节点之间的最大距离的变体)

谢谢

Answer 1

您可能对“On the sum of all distances in a graph or digraph”感兴趣。该论文将您的“总距离”称为图形的“传输”。您的“最大距离”通常称为图形的“直径”。对两者进行了讨论，证明了图传输的一些性质，证明了传输与直径相互独立。

天真地，您有 n-choose-k 个选项可以尝试。如果 n 和 k 很大，那就太糟糕了。如果其中一个很小，那还不错。

有比这更好的工作。 This Mathoverflow question询问减少顶点之间的平均距离，这与图的传输成正比。有两个答案，我都不能保证。它还指a paper直接解决了这个问题。

最小化图形的直径在 this paper 中处理。 .

您可以考虑将这个问题提交给 Math stackexchange。