最小方差生成树的多项式时间算法
Polynomial time algorithm for minimum variance spanning tree
让我们将图的方差定义为其边权重的方差。我要解决的任务是设计一种算法，给定图 G 将构造具有最小方差的生成树 T。
我很难在这方面取得成功。到目前为止，我已经注意到，如果知道这种生成树中的平均边权重，那么可以通过将每条边的权重替换为其偏差的平方即平均权重并将图形馈送到任何 MST 发现中来解决问题算法。
显然，我对我试图构建的树中的平均边权重一无所知，但我突然想到，平均值必须落在 G 的两条边之间，也许可以利用此信息。
我正在尝试将问题减少到找到具有修改边权重的 G 的 MST。我考虑了 运行 G 的每条边的算法，每次都假设初始边最接近 T 中的平均值并且给定权重 0，而其他边的权重等于它们与权重偏差的平方的初始边缘。这种方法无处可去，因为如果平均值不等于其中一条边的权重，那么根据它落在 2 个最近的边的权重之间的位置，基于它们的权重的边排序会不同，并且会产生不同的跨度将树输入 MST 查找算法时。这是我不知道如何处理（或者是否可以处理）的事情。
这是家庭作业，所以我更希望得到一个小提示而不是解决方案。
思路一：构建最小权生成树时，只需要能够两两比较边即可。
想法 2：
权重为 x 的边和权重为 y 的边的成对比较，当您对权重和猜测 g 之间的差进行平方时，仅在 g=(x+y)/2 处发生变化。
想法 3：
如果有|E|边，至多有 (|E| choose 2)+1 个对平均权重有本质不同的猜测 g。为每一个计算最小权重生成树。比较这些树的方差。
应该有更快的方法，但这是多项式时间算法。
让我们将图的方差定义为其边权重的方差。我要解决的任务是设计一种算法，给定图 G 将构造具有最小方差的生成树 T。
我很难在这方面取得成功。到目前为止，我已经注意到，如果知道这种生成树中的平均边权重，那么可以通过将每条边的权重替换为其偏差的平方即平均权重并将图形馈送到任何 MST 发现中来解决问题算法。
显然，我对我试图构建的树中的平均边权重一无所知，但我突然想到，平均值必须落在 G 的两条边之间，也许可以利用此信息。
我正在尝试将问题减少到找到具有修改边权重的 G 的 MST。我考虑了 运行 G 的每条边的算法，每次都假设初始边最接近 T 中的平均值并且给定权重 0，而其他边的权重等于它们与权重偏差的平方的初始边缘。这种方法无处可去，因为如果平均值不等于其中一条边的权重，那么根据它落在 2 个最近的边的权重之间的位置，基于它们的权重的边排序会不同，并且会产生不同的跨度将树输入 MST 查找算法时。这是我不知道如何处理（或者是否可以处理）的事情。
这是家庭作业，所以我更希望得到一个小提示而不是解决方案。
思路一：构建最小权生成树时，只需要能够两两比较边即可。
想法 2：
权重为 x 的边和权重为 y 的边的成对比较，当您对权重和猜测 g 之间的差进行平方时，仅在 g=(x+y)/2 处发生变化。
想法 3：
如果有|E|边，至多有 (|E| choose 2)+1 个对平均权重有本质不同的猜测 g。为每一个计算最小权重生成树。比较这些树的方差。
应该有更快的方法，但这是多项式时间算法。