-
25 votesanswersviews
生成树最小化连接到多个边的顶点数？
是否有算法可以找到无向图的生成树，从而最大限度地减少连接到多个边的顶点数？ 例如，给定一个4 x 4网格图，我们希望找到左侧的生成树（其中有7个顶点连接到多个边）而不是右边的生成树（有12个）： Edit: 如果我们只考虑平面图（甚至只考虑网格图），这个问题会更简单吗？ -
3 votesanswersviews
最小方差生成树的多项式时间算法
让我们将图的方差定义为其边的权重的方差 . 我试图解决的任务是设计一种算法，给定图G将构造具有最小方差的生成树T. 我很难在球上滚球 . 到目前为止，我已经注意到如果已知这样的生成树中的平均边缘权重，则可以通过将每个边缘的权重替换为其偏差的平方与平均权重并将图形馈入任何MST发现来解决问题 . 算法 . 显然，我对我想要构建的树中的平均边缘权重一无所知，但是我发现平均值必须落在G的2个边缘之间，并...