让我们有一个图表。当我们删除一条边时，会创建 2 辆“汽车”，从边的每个顶点创建一辆。当这两辆车相遇时，它们会停下来。问题是创建一棵生成树，以使通过每个顶点的汽车数量之和最小。
增加的困难是，如果一个顶点有 n 辆车从它经过，那么成本是 K^n 而不是 n*K。
一些想法。我们可以找到最短的无弦周期作为开始，但这些无弦周期的位置，即它们是否相互接触，会改变度量，从而改变最短周期。
这不是最小生成树问题。我想解决这个问题，因为每辆车都代表一个变量，而生成树是计算优化问题的最有效方法。当来自同一边缘的 2 辆车相遇并停止时，我从优化中减少了一个变量。
编辑：
过程是这样的。我们删除了许多边以使图成为生成树。每条移除的边会创建 2 辆汽车，在被移除的边的每个顶点上都有一辆，它们需要彼此相遇。我们为每辆双车固定一条路径。然后我们检查有多少汽车（从我们移除的所有边）通过每个顶点。如果从一个顶点通过的汽车数量为 n，则成本为 K^n，其中 K 是一个常数。然后我们将所有成本相加，这就是需要最小化的全局成本。
如果有不清楚的地方，请告诉我。 https://mathoverflow.net/questions/86301/spanning-tree-that-minimizes-a-dynamic-metric