最小方差生成树的多项式时间算法
让我们把图的方差定义为其边权的方差。我所要解决的任务是设计一个算法，在给定图G的情况下，构造一个具有最小方差的生成树T。
我很难搞清楚这件事。到目前为止，我已经注意到，如果这样的生成树中的平均边权是已知的，那么问题可以通过将每条边的权重替换为其偏差的平方，即平均权重，并将该图输入到任何MST查找算法中来解决。
显然，我不知道任何关于平均边缘权重在树中，我正在试图构造，但它发生在我的平均值必须落在2个边之间的G和也许这个信息可以被利用。
这是家庭作业，所以我更喜欢一个小提示给我正确的方向，而不是一个解决方案。
共有1个答案
想法1：当你构建最小权值生成树时，你只需要能够两两比较边。
想法2：
权重x的边和权重y的边的两两比较，当你将权重和猜测g之间的差平方时，只在g=(x+y)/2处改变。
-
本文向大家介绍Kruskal的最小生成树算法，包括了Kruskal的最小生成树算法的使用技巧和注意事项，需要的朋友参考一下 有一个连通图G(V,E)并给出了每个边的权重或成本。Kruskal的算法将使用图形和成本找到最小生成树。 这是合并树方法。最初，有不同的树，此算法将采用成本最小的那些边合并它们，并形成一棵树。 在此问题中，所有边均根据其成本列出并排序。从列表中，取出成本最低的边并添加到树中，
-
主要内容：生成树,最小生成树数据结构提供了 3 种存储结构，分别称为线性表、树和图，如图 1 所示。 图 1 3 种存储结构 a) 是线性表，b) 是树，c) 是图。 在图存储结构中，a、b、c 等称为顶点，连接顶点的线称为边。 线性表是最简单的存储结构，很容易分辨。树和图有很多相似之处，它们的区别是：树存储结构中不允许存在环路，而图存储结构中可以存在环路（例如图 1 c) 中，c-b-f-c、b-a-f-b 等都是环路）。
-
最小生成树 一个有 n 个结点的带权无向图，在满足所有顶点都连接的前提下使得所有的边的权总和最小，即为最小生成树(Minimum Spanning Tree MST)。最小生成树可以用kruskal（克鲁斯卡尔）算法或prim（普里姆）算法求出。 N个顶点，一定有N-1条边 包含所有顶点 所有顶点都可以直接或间接连接到另外的顶点 普里姆算法 普里姆算法在找最小生成树时，将顶点分为两类，一类是在查找
-
我一直在读生成树的概念及其类型。这就是我所理解的： 生成树：图G中连接所有顶点的边数最小的子集 最小生成树：它是边权的总和最小的生成树。 现在，这是否意味着，在检索MST时， > 如果我们遇到G中的一条路径，它有更多的边（与其他路径相比），但在边权重总和上的权重最小（与所有其他路径相比），我们将不把它视为MST？ MST的概念是否只有在G有多个生成树的情况下才起作用？其他跨树=mst？ 谢谢你的帮
-
我需要一些关于Prim的算法问题的帮助： 设T是图G的一个由Prim算法得到的最小生成树。设Gnew是在G上增加一个新的顶点和一些带权的边，将新的顶点连接到G上的一些顶点而得到的图，我们能把其中一条新的边加到T上构造Gnew的最小生成树吗？如果你回答是，请解释是怎样做的；如果没有，请解释原因。 提前谢谢！！
-
这里有一个图，我需要用Prim和Kruskal的算法找到G的最小生成树。 我用普里姆的算法找到了最小生成树。这是我的尝试。 我很难用Kruskal的算法找到最小生成树。我看过许多与Kruskal的图算法相关的视频，但最终得到的图与Prim的算法相同。 谁能给我演示一下如何用Kruskal的算法找到图的最小生成树吗？