最小生成图-负权和正权
如果它一定是一棵树，你能解释一下连通性和极小性之间的矛盾吗。但是如果你认为它可能是其他的子图，那么你能给我一个例子，一个连通图可能不是树，它的权重更低。
共有1个答案
如果你有负权，你不能保证一个最小生成子图是树。考虑一个由3个顶点组成的完整图，所有边的权重为-1。
编辑有点误解了你的问题：
如果你有负权重：它可能不是一棵树
-
假设所有边的权值都为正，那么通过对每条边的，然后应用Kruskal或Prim得到最小乘积生成树。但如果某些权重为负值，我们就不能应用这个程序。因为我们需要包含奇数个负边，而这些边必须具有最大的权重。在这种情况下怎么办？
-
这是为什么大多数图算法不那么容易适应负数的后续问题？。 我认为最短路径(SP)存在负权重的问题，因为它将路径上的所有权重相加，并试图找到最小权重。 但我不认为最小生成树(MST)在负权值上有问题，因为它只取单个最小权值边，而不关心整体总权值。 我说的对吗？
-
假设我选择V(H)={a,e,f}和e(H)={ae,af,fe} 现在，对于每条边e∈e(H)，我们用e'记下了（来自原始图G的） 达到这个最小值的边。所以E'={bc,df,eg},因为bc=4,df=9,eg=8,是连接我的元件的最小边。我在H中有一个相对于代价函数C′的最小生成树，而a′是这棵树的边集。 但是我的A'的边和E'的没有一条是一样的。
-
设T=(V，E)是一棵顶点和边的树，代价已知。我们想构造一个最小权完备图G=(V,E')，它的唯一最小生成树是T。 示例：考虑下面的树T，红色边具有给定的代价。将添加虚线边以从这棵树构造一个完整的图。 作为其唯一MST而跨越T的最小权完备图G如下所示： 2）对MST的所有其他边，权重，按权重递减的顺序重复。进行只包括而不包括其他MST边的切割。此切割的任何未知非MST边的权重应为。 问题： 1）上
-
给了我一个问题，上面写着： 给定一个具有整数权值（正负两种）的连通有向图，发展一种求两顶点之间最短路径的算法。 我想我可以使用最小生成树算法，比如Kruskal的算法，然后用Dijkstra的算法来证明，因为在MST中，每个顶点只有一条内边，Dijkstra的算法即使在负权值下也能工作。 这听起来像是共食吗？ 附注。我很难证明MST包含有向图的每个顶点的最短路径。
-
最小生成树英文是Minimum Spanning Tree，对于最小生成树大家应该都不陌生，当然还有最大生成树，首先就简单总结一下算法里的生成树。 一、什么是生成树？ Spanning有跨越的意思，生成树一般来说每个节点都能访问到别的节点，是一个连通树。所以，一般考虑无向图里去造生成树。生成树又分最小和最大两种，其中最小生成树应用比较多。总结一下生成树的定义： 1. 首先它得是一个树的结构 2.