让我们将图的方差定义为边权的方差。我正在尝试设计一种算法，给定一个图G，构造一个具有最小方差的生成树T。
我很难开始解决这个问题。到目前为止，我注意到如果这样一个生成树中每条边的权重平均值是已知的，那么可以用每条边的权重与平均权重的偏差的平方代替权重，并将图输入到任何最小生成树查找算法中来解决问题。
显然，我不知道我要构建的树中每条边的平均权重，但我意识到平均值必须在G的两条边之间，并且也许可以利用这个信息。
我试图将问题化简为寻找修改后边权的G的最小生成树问题。我考虑了对G的每条边运行一个算法，每次假设初始边在T中最接近平均值并且给定权重0，而其他边的权重等于它们与初始边权重的偏差的平方。这种方法没有进展，因为如果平均值不等于任何一条边的权重，则取决于平均值在2个最接近的边权重之间的位置，基于它们的权重排序的顺序将是不同的，当输入MST查找算法时会产生不同的生成树。这是我不知道如何处理的问题（或者它是否能够被处理）。
因为这是作业，所以我更喜欢得到一些提示来引导我朝着正确的方向前进，而不是一个解决方案。
我很难开始解决这个问题。到目前为止，我注意到如果这样一个生成树中每条边的权重平均值是已知的，那么可以用每条边的权重与平均权重的偏差的平方代替权重，并将图输入到任何最小生成树查找算法中来解决问题。
显然，我不知道我要构建的树中每条边的平均权重，但我意识到平均值必须在G的两条边之间，并且也许可以利用这个信息。
我试图将问题化简为寻找修改后边权的G的最小生成树问题。我考虑了对G的每条边运行一个算法，每次假设初始边在T中最接近平均值并且给定权重0，而其他边的权重等于它们与初始边权重的偏差的平方。这种方法没有进展，因为如果平均值不等于任何一条边的权重，则取决于平均值在2个最接近的边权重之间的位置，基于它们的权重排序的顺序将是不同的，当输入MST查找算法时会产生不同的生成树。这是我不知道如何处理的问题（或者它是否能够被处理）。
因为这是作业，所以我更喜欢得到一些提示来引导我朝着正确的方向前进，而不是一个解决方案。