3回答
寻找最小瓶颈生成树
、、、
我知道a是真的，我可以证明，但是找到b和c部分的算法正在逃避我。
解决以下最小瓶颈树，其中边与最大的成本被称为瓶颈。(a) G的每个最小瓶颈生成树是G的最小生成树吗？证明你的主张。(b)对于给定的代价c，给出了G最小瓶颈生成树的<
浏览 7提问于2012-10-29得票数 2
回答已采纳
1回答
图中求最小生成树(MST)？
、、、、
给出了一个边上有权的无向图G和2 different最小生成树: T，T‘对于T‘中没有T’的每一个边e，T‘中有一个边e'，它不在T中，所以如果在T中用e'代替e (我们称之为T_new)，那么它仍然是G的最小生成树。我认为我离找到正确的算法太近了，但我坚持了一点：
I证明了weight(e)必须与weight(e)
浏览 9提问于2021-05-09得票数 1
2回答
基于DFS的MST算法
、、、
我有以下算法:对于边上具有正权函数的给定(有限无向简单)图G=(V，E)：
现在我需要了解这个算法在做什么。我已经证明了算法给了我一个G的生成树，我相信它是一个最小生成树，但是我没有<
浏览 4提问于2011-12-09得票数 0
回答已采纳
1回答
最小生成树唯一最小边与非唯一证明
、、、、
因此，我有一个练习，我应该证明或反驳：( 2)与1)相同，但现在所有的边权都是不同的。那么直观地，我理解对于1)由于不是所有的边权都是不同的，那么一个顶点可能有边e的路径，但也有另一个边e_1，这样如果权重(E)=权(e_1)，那么就有一个生成树，它不包含边e，因为这个图
浏览 3提问于2015-10-01得票数 2
回答已采纳
2回答
最小生成树和最短路径
、、、
我遇到了这样一个问题：
给定一个具有整数权重(正负)的连通有向图，开发一个算法来寻找两个顶点之间的最短路径。我想我可以使用最小生成树算法，例如kruskal的算法，然后使用可能的dijkstra算法来证明，因为在MST中，每个顶点只有一条进入边，dijkstra的算法甚至可以在负权重下工作。附注：我很难证明MST包含每个顶点<e
浏览 1提问于2012-11-08得票数 0
3回答
假设有一个图G，它的所有边都有对应于不同整数的权重。所以没有两条边具有相同的权重。设E是G的所有边，emax是E中具有最大权重的边。图G的另一个性质是每条边e都属于图G中的某个圈。我必须证明G的最小生成树不包含边emax。
我可以理解为什么这是真的，因为所有的边都是不同的，并且每条边都属于一个循环，所以最小生成树</em
浏览 2提问于2013-11-28得票数 6
回答已采纳
2回答
这是一种在连通的无向图G=(V，E)中求最小生成树的算法：
在图(S，V\S)中选择一些不属于横过它的B的边e的切线。这就是(S，V\S)作为剪裁的意思。边(u，w)也是交叉边。
(u，v)是该特定切割中最轻的交叉边。(s，u) 不是是“交
浏览 2提问于2018-03-30得票数 0
回答已采纳
2回答
，我需要用Prim的和Kruskal的算法找到G的最小生成树。我很难用Kruskal算法找到最小生成树。我看过很多与Kruskal的图形算法相关的视频，但我最终得到了与Prim算法相同的图形。
有人能
浏览 1提问于2019-03-17得票数 0
回答已采纳
2回答
我有一个连通的无向图，每个图的边都是黑色或白色的，还有一个整数k。我正在尝试编写一个算法，来判断是否存在恰好有k条黑边的生成树(不一定要找到真正的树)。我使用Kruskal的算法来找到生成树中可能的最小和最大黑边数量。如果k不在此范围内，则不可能存在具有k条边的生成树。
但我
浏览 0提问于2010-12-06得票数 3
考虑到Prim的算法，顶点的最小边缘要么已经在树中，要么最终会被选择。如果这句话是假的，谁能给我举个反例？
谢谢。
浏览 3提问于2022-03-25得票数 0
回答已采纳
1回答
反向删除算法:从包含所有边的图开始。然后按权重的递减顺序重复通过边缘。对于每条边，检查删除该边是否会断开该图的连接；如果不会，则删除它。
如何证明此算法计算MST？
浏览 3提问于2020-03-27得票数 0
2回答
我目前正在研究图及其算法，我注意到一个我不知道能确切证明的问题：
如果我们有一个连通的无向图G=(V，E)和每个边都有weight=1，那么每一棵从根建立的最短路径的生成树都是最小生成树吗？我用做了一些例子，我觉得这个问题的答案是正确的，但是有人可以告诉我如何证明这一点？另一个在我脑海中闪现的问题，是不是另一个方向也是正确<em
浏览 1提问于2015-12-21得票数 3
回答已采纳
2回答
我希望我的最小生成树算法基准与最好的。有人知道在哪里可以找到这些算法的C++实现吗？我大摇大摆地搜索了一下，却什么也没找到。如果这些算法是最好的，那么肯定有一个C++实现吗？--迄今最快的最小生成树算法是由David、Philip和Robert提出的，他发现了一种线性时间随机算法，它是Borů
浏览 2提问于2011-02-07得票数 11
回答已采纳
注:C‘为logc，基数为17用线性函数对每条边的代价进行变换，很容易证明结论是正确的。
我没有考虑具体的算法，比如贪婪的算法。我只考虑了变换后两棵树的权重之和之间的关系。如果G生成的一棵树有两个边a和b，
浏览 8提问于2020-08-12得票数 2
回答已采纳
我试图设计一个算法，其中给定一个连通加权图G= (V，E)和V中的一个顶点子集U将构造一个最小生成树，使得U中的所有顶点都是叶(其他顶点也可能是叶)，或者返回不存在这样的树(False)。这就是我所得到的全部，采用Prim的算法(公平警告，它非常糟糕；甚至不知道它是否有效/是否有效，或者使用什么数据结构，我会接受其他任何正确的算法)：
Let x be
浏览 3提问于2020-10-15得票数 2
回答已采纳
2回答
如果我们修改最短路径问题，使得两个顶点之间的路径的成本是其上边的成本的最大值，那么对于任何一对顶点u和v，它们之间遵循最小成本生成树的路径是最小成本路径。
我如何证明这种方法是正确的？这是有道理的，但我不确定。有没有人知道文献中是否存在这种算法？它有名字吗？
浏览 0提问于2011-11-02得票数 3
回答已采纳
4回答
通用最小生成树
、、
我正在阅读科门等地的最小生成树，下面是一般的最小生成树。
假设我们有一个连通的无向图G = (V，E)，它有一个加权函数w:E->R，我们希望为G找到一个最小生成树，这里我们用贪婪的方法。这种贪婪策略由以下“泛型”算法捕获，该算法一次生成最小生成树一条
浏览 3提问于2011-11-16得票数 2
回答已采纳
4回答
最小生成树子图
、、、、
我正在阅读我的书中的所有练习，准备下周复习一次课堂考试，我真的对这个子图问题感到困惑。
目前我的想法使我相信，既然我们已经有了最小生成树G，那么既然我们在最小生成树中有子节点，就必须存在G‘。如果X‘的节点集和边集分别是X的节点集和边集的子集，则X’是图X的子图。设(V，T)是G的最小生成树，
浏览 2提问于2012-10-29得票数 4
回答已采纳
扫码
添加站长 进交流群
领取专属 10元无门槛券
手把手带您无忧上云
相关资讯
热门标签
云服务器
ICP备案
对象存储
腾讯会议
实时音视频活动推荐
腾讯云开发者
