腾讯云
开发者社区
文档
建议反馈
控制台
登录/注册
首页
学习
活动
专区
工具
TVP
最新优惠活动
文章/答案/技术大牛
搜索
搜索
关闭
发布
精选内容/技术社群/优惠产品,
尽在小程序
立即前往
文章
问答
(6766)
视频
沙龙
1
回答
用Stoer
算法
求无向图的最大
割
集
、
我能用Stoer
算法
找到最大
割
集
吗?比方说,我用Stoer
算法
否定了所有的
边
权值,并求出了这个图的
最小
割
集
,结果
割
集
是原图的最大
割
集
吗?添加了:在Stoer
算法
中,如果我选择最不紧密连接的顶点,并选择由相位
割
集
返回的所有
割
集中最大的一个,那么它是全局最大
割
集
吗?为什么或者为什
浏览 1
提问于2016-12-09
得票数 0
3
回答
最小
裁剪器
、
、
编写一个程序,该程序接受一个无向图,并找到
最小
割
集
,即,如果删除,就会将图断开到两个或多个连通组件中的一组
边
。程序的时间复杂度应为O(n^2m),其中n为顶点数,m为图中的
边
数。解决这一问题的一种
算法
是Karger
算法
,它是一种随机
算法
,它以较高的概率找到
最小
割
集
。以下是
算法
的高级概述:从缩略图中随机选择一个
边
浏览 0
提问于2023-02-14
得票数 5
1
回答
输出精确边缘的全局小裁剪
算法
、
我正在寻找一个
算法
,以找到一个无向图的全局小
割
集
。我想输入一个图和
算法
输出
最小
的
边
数,通过切割它们,可以将给定的图分成两部分。
算法
应通过指示已找到答案或未找到答案而终止。我在网上搜索了一些文章,发现Karger的
最小
割
集
算法
是随机的,它的输出可能不是精确的
最小<
浏览 6
提问于2016-03-16
得票数 0
1
回答
每条路径中出现的
边
数最少
、
、
我需要找到一个图中出现在从第一个顶点到最后一个顶点的每条路径中的
最小
边数。示例图像:我已经寻找了一段时间,但没有找到(或想到)任何
算法
来做到这一点……
浏览 1
提问于2013-01-22
得票数 3
回答已采纳
6
回答
如何使用最大流
算法
在图上找到
最小
割线?
、
、
、
、
我需要找到图上的
最小
割线。我一直在读关于流网络的文章,但我所能找到的都是最大流
算法
,如Ford-Fulkerson,push-relabel等。给定最大流-
最小
割
集
定理,是否可以使用这些
算法
中的一种来使用最大流
算法
在图上找到
最小
割
集
?多么? 到目前为止,我找到的最好的信息是,如果我找到“饱和”
边
,即流量等于容量的
边
,这些
边
对应于
最小
切割。的确,<
浏览 6
提问于2010-12-19
得票数 59
1
回答
如何通过增加最少的
边
数来增加图的
最小
割
数
、
、
、
添加
最小
数量的
边
,这样即使从新创建的图中删除了一条
边
,仍然存在从任何顶点到任何其他顶点的路径。 我认为这个问题可以简化为将图的
最小
割
集
的大小从目前的
最小
割
集
1增加到2。但是,有什么有效的
算法
可以做到这一点呢?
浏览 1
提问于2012-10-06
得票数 3
回答已采纳
1
回答
寻找图中所有割线的
算法
、
我正在寻找一种有效的
算法
,可以帮助我列出一个图中的所有切割。该图是流网络(有向图),并且具有固定的源和宿。我想找出所有可能的
割
集
,源
集
在一
边
,sink
集
在另一
边
。请注意,优先考虑的是找到所有的
割
集
,而不是
最小
割
集
。例如,考虑具有以下边列表的图: s-->a-->t ->b-->t 上图的
割
集
是:{sa,sb},{at,bt
浏览 4
提问于2013-02-24
得票数 1
3
回答
在所有边的
边
容量增加1之后,图的
最小
割
集
是否相同?
、
设G= (V,E)是一个任意流网络,对每个
边
e都有一个源s和目标t,正整数容量c(e),(S,T)是相对于这些容量的
最小
s-t
割
集
。现在假设我们将每条
边
的容量增加1,即对于所有边,c_new(e) = c(e) +1,那么对于这些新的容量{c_new},(S,T)仍然是
最小
的s-t
割
集
吗?我的直觉是,如果G包含不同容量的
边
,容量的增加可能会导致不同的
最小
切割。但是,当所有边都有相同的容量时,
最小
<e
浏览 2
提问于2016-10-27
得票数 7
1
回答
带权值的Karger
算法
、
、
、
、
假设给出了一个无向无向图G= (V,E)和一些代价函数c:E→R>0,给出了每个
边
∈E的正代价c(e)。其目的是计算
最小
代价G的
最小
割
集
(即由
最小
边数构成的
割
集
之间的
最小
成本削减)。给出了一种高概率的
算法
,在多项式时间内找到这样的
最小
代价
最小
削减。您的
算法
运行时间是多少?提示: Karger
算法
方法一:做Karger n^c倍(仍然
浏览 3
提问于2019-08-17
得票数 1
1
回答
去除K
边
算法
后的最大流/
最小
割
流
、
我被要求为以下问题开发一个
算法
:A流网络G,其
边
的最大容量为1G的最大流f_x_xa正整数K_。,如果K大于或等于max,删除所有穿过G的
最小
割
集
的
边
,如果K仍然大于零,删除随机
边
,并且新的最大流是零如果K小于,则删除与G
最小
<
浏览 0
提问于2020-06-21
得票数 0
回答已采纳
1
回答
无向赋权图的s-t
割
、
、
、
、
我在网上了解到,
最小
割
集
等于最大流,并且有一些标准
算法
可以求解有向图的s-t
最小
割
集
。但我似乎找不到太多关于无向图的s-t
割
的材料,我看到人们提到我可以用相反方向的两条有向
边
替换无向
边
,以将无向图转换为有向图。然而,当我找到新的有向图的最大流量或
最小
切割时,为什么它与原始的无向图有任何关系?我设想新的有向图的
最小
割线通常应该只包含uv和vu
边
中的一条,而不是两条<
浏览 38
提问于2019-03-02
得票数 2
1
回答
有向图的闭包--最大闭包问题
、
、
、
然后,根据闭包的定义,闭包C(G) = {b,c},因为没有离开C.的
边
。那么,我在这里没有正确理解什么呢?谢谢!
浏览 1
提问于2022-02-09
得票数 1
回答已采纳
2
回答
福特-富尔克森
算法
找到哪个
最小
割线?
、
、
、
在一个网络中可以有多个
最小
切割。例如:有四个
最小
切割和福特-富尔克森找到一个“更接近”的s(来源)。我们能对所有网络说同样的话吗?也就是说,福特-富尔克森找到了离源头最近的切割?
浏览 5
提问于2015-04-03
得票数 6
1
回答
流网络上
最小
割
集
的方向性
、
我不确定我是否误解了
最小
切割,但我已经编写了一个使用edmond的
最小
切割
算法
,然后在流网络上使用了一个BFS。如果我让它做一个从A到B的
最小
割
集
,它工作,因为剩余流A->B = 0,所以它产生
集
{A},切成A->B (1)。但是,如果我告诉它做一个从B到A的
最小
割
集
,它就不能增加任何
边
(因为没有来自C的
边
),所以结果
集
是{C},切成B->C (
浏览 1
提问于2016-05-20
得票数 0
回答已采纳
1
回答
最佳群集化
、
、
对于每个
边
(i,j),都有一个付款Pi,j,它可以是正的、零的或负的。我们用簇来划分顶点。每次两个相邻顶点v1和v2属于不同的集群时,我们都会收到付款Pv1,v2。如何最大限度地提高支付总额?
浏览 1
提问于2016-12-13
得票数 1
1
回答
关于
最小
生成树的切割
、
我正在阅读有关
最小
生成树
算法
的文章。这里提到了cut。无向图G= ( V,E)的
割
集
(S,V-S)是V的一部分,如果它的权重是与割线相交的任何
边
的
最小
值,则称它是与割线相交的一条轻
边
。上述定义在Kruskal和Prims
算法
中是如何使用的?谢谢
浏览 1
提问于2011-11-25
得票数 0
回答已采纳
1
回答
照片上的Gomory-Hu树不工作了?
、
、
因此,
最小
切割树t应该是一个中心为"3“的恒星。显然不是这样的..。
浏览 0
提问于2014-08-13
得票数 1
回答已采纳
1
回答
最小
权乘积而不是无向图的和
、
、
、
我可以找到的所有
算法
都使用最大流/
最小
割
集
属性来计算将源和接收器分开的
最小
加权
割
集
。然而,所有这些
算法
都使用加权和作为
最小
值的定义,而在我的用例中,权重不是绝对数,而是机会,因此在乘法下必须是
最小
的,而不是加法来提供适当的
最小
割
集
。我无法证明已知的最大流/分钟切割
算法
背后的思想和属性仍然适用于乘法而不是加法。这些
算法<
浏览 2
提问于2018-03-10
得票数 1
回答已采纳
0
回答
对Ford-Fulkerson方法的修正
、
、
我想在具有整数容量的流网络G的所有
最小
割
数中找到一个包含
最小
边数的网络。我们如何修改G的容量来创建一个新的流网络G‘,其中G’中的任何
最小
割
集
都是G中具有最少
边
数的
最小
割
集
浏览 7
提问于2017-06-13
得票数 0
回答已采纳
2
回答
在图中寻找
最小
割
边
、
、
给定一个随机的无向图,我必须找到从一个顶点到另一个顶点的“瓶颈
边
”(编辑:
最小
割
边
)。我称之为“瓶颈
边
”(编辑:
最小
割
边
) --假设我有以下无向图: / | \ | | \ | /为了独立于所选的路径从A到H,
边
BE和DG必须始终被遍历,因此形成了“瓶颈”(编辑:
最小
切割)。有没有一个多项式时间的
算法
浏览 0
提问于2011-04-28
得票数 7
回答已采纳
点击加载更多
扫码
添加站长 进交流群
领取专属
10元无门槛券
手把手带您无忧上云
相关
资讯
什么是求最小独立边支配集的算法?用C语言实现:求最小独立边支配集的算法。内附完整代码。
R语言最大流最小割定理和最短路径算法分析交通网络流量拥堵问题
React技术栈的最小技能集
算法:44.最小子数组
什么是最小生成树算法?详述最小生成树算法的原理?用C语言实现最小生成树算法。内附完整代码。
热门
标签
更多标签
云服务器
ICP备案
对象存储
实时音视频
云直播
活动推荐
运营活动
广告
关闭
领券