1回答
我的任务是，给定与图G中的E条道路相连的V个村庄，每条道路都标有一个正数。你必须至少达到这个数字的水平才能进入这条路。换句话说，如果一条道路标记为5，则您的级别必须至少为5或更高才能访问此道路。所以，我的解释是，我们只能在图中找到最大权重的边。但我还没有想出适用于这种情况的算法。
浏览 20提问于2019-10-12得票数 0
1回答
因此，完成此操作后，我们就得到了一个无向图。从数学上讲，为了我的目的，我认为我需要找到一种算法，在所有具有此图的最大尺寸匹配中，找到具有最大权重和的算法。这样的算法存在吗？我已经研究了“婚姻稳定问题”和“分配问题”，但这些问题是针对可分为两类(男性/女性，男性/任务)的图的。
浏览 4提问于2019-06-17得票数 0
23.1-5设e是连通图G=(V, E)的某个圈上的最大权边.证明了G'=(V, E - {e})的最小生成树也是G的最小生成树。也就是说，有一个G的最小生成树，它不包括e。问题是:我认为G 的所有最小生成树不包括 e 的命题是正确的。e 是某些周期上唯一的最大权边.是吗？添加e是的限制，这是某个循环中唯一的最大权重边.
浏览 1提问于2016-10-28得票数 1
回答已采纳
2回答
设G是一个加权无向图，e是G.Suppose中具有最大权的边，则G中有一个最小权生成树，其中包含下列语句的边e.Which是否总是正确的？c.Edge e不能包含在一个循环中。是前一年的一次考试，.
浏览 2提问于2013-12-24得票数 0
回答已采纳
1回答
我们知道，寻找两个顶点之间的最大权重路径是np困难的。但是如果我们限制边权重，例如。所有的边权重都小于某个特定值x。我清楚地定义了下面的问题。我有一个有向图G(V，E)，其中每条边的权重都在1到|V|之间。我想找到两个顶点u和v之间的最大权重路径。
这个问题是多项式时间可解的吗？
浏览 1提问于2018-03-11得票数 0
假设给定的图G (有n个顶点，m条边)的最小生成树T和一个权重为w的新边e= (u，v)，我们将添加到G中。
I)检查T是否仍为MST。II)如果不是，给出一个有效的算法来寻找图G+ e的最小生成树。
浏览 4提问于2013-05-29得票数 2
回答已采纳
3回答
假设有一个图G，它的所有边都有对应于不同整数的权重。所以没有两条边具有相同的权重。设E是G的所有边，emax是E中具有最大权重的边。图G的另一个性质是每条边e都属于图G中的某个圈。我必须证明G的最小生成树不包含边emax。
我可以理解为什么这是真的，因为所有的边都是不同的，并且每条边都属于一个循环，所以最小生成树算法可以简单地选
浏览 2提问于2013-11-28得票数 6
回答已采纳
1回答
考虑一个连通加权有向图G = (V, E, w)。路径P的胖度是P中任何边的最大权重。
如何找到图的最小可能的胖度？Dijkstra的算法能用来找出最小的脂肪吗？
浏览 0提问于2017-10-04得票数 1
回答已采纳
因此，这个问题涉及一个基于AdjacencyList的图G。这个图正好有n个边和n个顶点。它也有一个，而且只有一个周期。在循环中找到最大权重的边缘的最快算法是什么(就大O符号而言)？我非常肯定这可以在O(n)中完成，但是我很难弄清楚具体的内容，因为您必须验证您的结果处于一个循环中。我考虑这个问题的最初方法是一个简单的深度优先搜索，您可以用它在O(n)时间内找到整个图中的最大加权边(因为V+E = 2n)。然后，您可以进行另一项搜索，以
浏览 3提问于2015-03-30得票数 0
回答已采纳
2回答
给出了图G的充要条件，使图有一个唯一的最小生成树，另外，怎样才能满足这些条件呢？1)将V(G)划分为两个子集，每个子集中有一个端点的最小权边是唯一的。2)G的任意循环中的最大权边是唯一的。
但我不确定这是否是correct.Even，如果这是正确的，我不能证明它的正确性。
浏览 16提问于2016-12-16得票数 1
2回答
加权图G的最小瓶颈生成树是G的生成树，使得生成树中任意边的最大权最小。MBST不一定是MST (最小生成树)。
请举一个例子，说明这些陈述是有意义的。
浏览 2提问于2013-01-12得票数 35
回答已采纳
2回答
我想在网络图中找到'n‘最大加权边。如何实现这一目标。我构造了一个图如下：现在，我想找出上n‘边权值，即顶n’callDurations。
浏览 0提问于2018-09-21得票数 6
回答已采纳
5回答
设G= (V，E)是无向图。若F.中G的每个圈至少有一条边，则称边的F⊆E集为⊆反馈边集。(b)设G是一个具有正边权的加权无向图。我的解决方案(需要建议)：
( a) 最小大小反馈边集：，由于图是不加权的，我们可以使用DFS。我们像往常一样从任何顶点开始DFS。当我们遇到一个后边缘，我们把它插入到一组反馈边
浏览 6提问于2012-05-29得票数 15
1回答
MST定理证明
、、、、
设G = (V，E)是包含圈的加权无向连通图，设e是圈中所有边的最大权边。我需要证明G存在一个不包含e的最小生成树。
这个想法直观地清晰，我可以在一个循环中展示它，由3个节点组成。
浏览 2提问于2015-11-22得票数 2
回答已采纳
有一个具有正权重边的有向图G，我们将路径的成本定义为具有最小权重的边和最大权重的边之间的差异。目标是在其他路径中找到一条代价最大的路径。我们不需要返回路径本身，只需要返回最大开销。如果x是顶点数，y是边数，那么x < 10^5和y < min(x^2,10^5)。时间限制为1秒。 基于这些限制，我认为这个问题必须在O(x+y)时间内解决。因此，根据问题的性质和对其他算法的研究，我认为在可能的解上可能包含多个DFS(如SCC
浏览 30提问于2020-12-02得票数 2
回答已采纳
2回答
最大权无关集( MWIS )是一个NP-完全问题，如果P=NP，则不能在足够好的时间复杂度内找到一个解。我已经找到了，但它似乎只适用于具有唯一MWIS的二分图。
如果有人能帮助我提供一些参考，或者更好地使用一个工作算法的伪代码，我将非常高兴。
浏览 6提问于2015-06-18得票数 3
回答已采纳
中的完全匹配概念
从图中选择一个顶点，并在每一步中找到其最近的近邻顶点，然后删除它们并执行循环，直到图中没有顶点为止。u]["weight"] graph_minimum_match.add_e
浏览 2提问于2020-11-21得票数 1
回答已采纳
你得到一个有向无环图G= (V，E)。每个有向边e_ w_e _E具有与其相关联的权重∈。给定两个顶点s，t∈V，使得s没有入边，t没有出边，我们感兴趣的是从s开始到t结束的最大权有向路径。路径的权重是构成该路径的有向边的权重之和。(如果一个有向图中没有有向圈，则它是无圈的。)
我如何使用动态编程技术来解决这个问题？我已经被困了一段时间了，任何提示都很感谢:d
浏览 1提问于2018-11-18得票数 0
扫码
添加站长 进交流群
领取专属 10元无门槛券
手把手带您无忧上云
相关资讯
热门标签
云服务器
ICP备案
对象存储
腾讯会议
云直播活动推荐
腾讯云开发者
