让我们将图的方差定义为其边的权重的方差 . 我试图解决的任务是设计一种算法，给定图G将构造具有最小方差的生成树T.
我很难在球上滚球 . 到目前为止，我已经注意到如果已知这样的生成树中的平均边缘权重，则可以通过将每个边缘的权重替换为其偏差的平方与平均权重并将图形馈入任何MST发现来解决问题 . 算法 .
显然，我对我想要构建的树中的平均边缘权重一无所知，但是我发现平均值必须落在G的2个边缘之间，并且可能这些信息可能被利用 .
我正在尝试通过修改边缘权重来减少找到G的MST的问题 . 我考虑为G的每个边缘运行算法，每次假设初始边缘在T中最接近平均值并且给定权重0而其他边缘得到的权重等于它们与初始边缘的权重的偏差的平方 . 这种方法无处可去，因为如果平均值不等于其中一条边的权重，那么根据它在2个最接近边的权重之间的位置，基于它们的权重的边的排序将是不同的并且将产生不同的 Span 当进入MST发现算法时，树木 . 这是我不知道如何处理（或甚至可以处理） .
这是家庭作业，所以我更喜欢一个小小的提示，让我朝着正确的方向而不是解决方案 .
1 回答
想法1：您只需要在构建最小权重生成树时成对比较边 .
想法2：
想法3：
应该有更快的方法，但这是一个多项式时间算法 .