让我们将图的方差定义为其边权重的方差。我试图解决的任务是设计一个算法，给定一个图 G 将构建一个具有最小方差的生成树 T。
我很难让球继续前进。到目前为止，我已经注意到，如果知道这种生成树中的平均边权重，那么可以通过将每条边的权重替换为其偏差的平方与平均权重的平方并将图形输入到任何 MST 发现中来解决问题算法。
显然，我对我试图构建的树中的平均边缘权重一无所知，但是我发现平均值必须落在 G 的 2 个边缘之间，也许可以利用这些信息。
我试图将问题减少到找到具有修改边缘权重的 G 的 MST。我考虑过为 G 的每条边运行一个算法，每次都假设初始边最接近 T 中的平均值并给定权重 0，而其他边的权重等于它们与初始边的权重的偏差的平方. 这种方法一无所获，因为如果平均值不等于其中一个边的权重，那么根据它落在 2 个最近边的权重之间的位置，基于它们的权重的边的排序会有所不同，并且会产生不同的跨度输入 MST 查找算法时的树。这是我不知道如何处理（或者甚至可以处理）的事情。
这是家庭作业，所以我更愿意给我一个小提示，让我朝着正确的方向前进，而不是一个解决方案。