在不影响图的最小生成树的情况下添加尽可能轻的边？
我们有一个图G并且希望在每个顶点对之间添加边，这些边尽可能轻，而不影响最小生成树。给定最小生成树和一对顶点，在不影响MST的情况下，如何计算它们之间添加的最轻边的权重？
我认为添加一条比两个顶点的每一条边缘都重的边缘会起作用，但在我所做的实验中，这似乎是错误的。
共有1个答案
生成树的边数由顶点数决定。因此，如果向MST添加一条边，则需要删除另一条边以获得生成树。但是，您不能删除任何边缘。显然，移除一条不在两个顶点之间路径上的边会断开图的连接。因此，您只能移除此路径上的一条边。如果你想找到最小生成树，你当然要去掉最重的边。
如果新的边的权重大于旧路径上最重的边的权重，则新的生成树比原生成树重。因此，新的边必须比这个边重，才能保持原来的MST。
-
我不确定如何处理这个问题。 给定一个无向图，每条边的颜色要么是红色，要么是蓝色。如何在时间复杂度（O（m+n）log n）中找到包含尽可能少的红边的最小生成树。其中m个顶点和n个边。 任何帮助都将不胜感激。
-
假设我选择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'的没有一条是一样的。
-
我一直在读生成树的概念及其类型。这就是我所理解的： 生成树：图G中连接所有顶点的边数最小的子集 最小生成树：它是边权的总和最小的生成树。 现在，这是否意味着，在检索MST时， > 如果我们遇到G中的一条路径，它有更多的边（与其他路径相比），但在边权重总和上的权重最小（与所有其他路径相比），我们将不把它视为MST？ MST的概念是否只有在G有多个生成树的情况下才起作用？其他跨树=mst？ 谢谢你的帮
-
我正在尝试找到一种有效的方法来检测给定的图形 G 是否具有两个不同的最小生成树。我还在尝试找到一种方法来检查它是否有 3 个不同的最小生成树。我所讨论的天真解决方案是运行一次 Kruskal 的算法并找到最小生成树的总权重。稍后，从图中删除一条边并再次运行 Kruskal 算法，并检查新树的权重是否是原始最小生成树的权重，以及图中的每个边的权重。运行时为 O（|五||E|log|V|）这根本不好，
-
我有一个问题需要我在Boost图库中找到一个有向图的最小生成树。 我的第一个尝试是使用深度优先搜索和dfs-visitor。我的计划是忽略除树边回调之外的所有边。这不起作用，我给出了下面的例子来说明原因。 我的问题是我是否可以让我的dfs-visitor在BGL中创建一个有向图的最小生成树。 下面是失败的例子。如果我有以下有向图 在深度优先搜索dfs-visitor中，1->0被分类为前沿。 如果
-
考虑一个有n个顶点和m条边的无向图。假设边有两种类型:m1红色边和m2绿色边。因此m=m1+m2。红色边缘的权重为1，绿色边缘的权重为2。设计并分析了一种计算这种图的最小生成树的有效算法