使用 n 个节点之间的 k 个链接最小化总距离
Minimize total distance using k links among n nodes
我遇到了以下问题，我不知道解决方案，也找不到 'lookup' 术语来进一步调查。
假设我们有 N 个有序节点 (n_1,n_2...n_N)，每个节点之间的固定距离为 1。所以 dist(n_1,n_N) = N-1。现在我们可以连接任意两个节点，从而有效地将它们的距离减少到 1。假设我们可以有 k 个这样的连接。
问题是：我们如何选择连接哪些节点以最小化任意两个节点之间的总距离？
这个问题是某个经过充分研究的问题的已知变体吗？是否存在有效的解决方案（或者我们只想最小化任意两个节点之间的最大距离的变体）
谢谢
您可能对“On the sum of all distances in a graph or digraph”感兴趣。该论文将您的 "total distance" 称为图表的 "transmission"。您的 "max distance" 通常称为图形的 "diameter"。讨论了两者，证明了图的传输的一些性质，并表明传输和直径是相互独立的。
天真地，您有 n-choose-k 个选项可以尝试。如果 n 和 k 很大，那就太糟糕了。如果其中一个很小，那就太好了。
有比这更好的工作。 This Mathoverflow question asks about reducing the mean distance between vertices, which is proportional to the transmission of the graph. There are two answers, neither of which I can vouch for. It also refers to a paper 直接解决了这个问题。
最小化图形的直径在 this paper 中处理。
您可以考虑将这个问题提交给 Math stackexchange。
我遇到了以下问题，我不知道解决方案，也找不到 'lookup' 术语来进一步调查。
假设我们有 N 个有序节点 (n_1,n_2...n_N)，每个节点之间的固定距离为 1。所以 dist(n_1,n_N) = N-1。现在我们可以连接任意两个节点，从而有效地将它们的距离减少到 1。假设我们可以有 k 个这样的连接。
问题是：我们如何选择连接哪些节点以最小化任意两个节点之间的总距离？
这个问题是某个经过充分研究的问题的已知变体吗？是否存在有效的解决方案（或者我们只想最小化任意两个节点之间的最大距离的变体）
谢谢
您可能对“On the sum of all distances in a graph or digraph”感兴趣。该论文将您的 "total distance" 称为图表的 "transmission"。您的 "max distance" 通常称为图形的 "diameter"。讨论了两者，证明了图的传输的一些性质，并表明传输和直径是相互独立的。
天真地，您有 n-choose-k 个选项可以尝试。如果 n 和 k 很大，那就太糟糕了。如果其中一个很小，那就太好了。
有比这更好的工作。 This Mathoverflow question asks about reducing the mean distance between vertices, which is proportional to the transmission of the graph. There are two answers, neither of which I can vouch for. It also refers to a paper 直接解决了这个问题。
最小化图形的直径在 this paper 中处理。
您可以考虑将这个问题提交给 Math stackexchange。