腾讯云
开发者社区
文档
建议反馈
控制台
登录/注册
首页
学习
活动
专区
工具
TVP
最新优惠活动
文章/答案/技术大牛
搜索
搜索
关闭
发布
精选内容/技术社群/优惠产品,
尽在小程序
立即前往
文章
问答
(9999+)
视频
沙龙
1
回答
用Stoer
算法
求无向图的最大
割
集
、
我能用Stoer
算法
找到最大
割
集
吗?比方说,我用Stoer
算法
否定了所有的边权值,并求出了这个图的
最小
割
集
,结果
割
集
是原图的最大
割
集
吗?添加了:在Stoer
算法
中,如果我选择最不紧密连接的顶点,并选择由相位
割
集
返回的所有
割
集中最大的一个,那么它是全局最大
割
集
吗?为什么或者为什么不?有什么例子吗
浏览 1
提问于2016-12-09
得票数 0
1
回答
最小
权乘积而不是无向图的和
、
、
、
我可以找到的所有
算法
都使用最大流/
最小
割
集
属性来计算将源和接收器分开的
最小
加权
割
集
。然而,所有这些
算法
都使用加权和作为
最小
值的定义,而在我的用例中,权重不是绝对数,而是机会,因此在乘法下必须是
最小
的,而不是加法来提供适当的
最小
割
集
。我无法证明已知的最大流/分钟切割
算法
背后的思想和属性仍然适用于乘法而不是加法。这些
算法<
浏览 2
提问于2018-03-10
得票数 1
回答已采纳
1
回答
带权值的Karger
算法
、
、
、
、
其目的是计算
最小
代价G的
最小
割
集
(即由
最小
边数构成的
割
集
之间的
最小
成本削减)。给出了一种高概率的
算法
,在多项式时间内找到这样的
最小
代价
最小
削减。您的
算法
运行时间是多少?提示: Karger
算法
方法一:做Karger n^c倍(仍然是多项式,在c的n上提高指数),并比较结果的
最小
割
集
。使用c- >=
浏览 3
提问于2019-08-17
得票数 1
1
回答
输出精确边缘的全局小裁剪
算法
、
我正在寻找一个
算法
,以找到一个无向图的全局小
割
集
。我想输入一个图和
算法
输出
最小
的边数,通过切割它们,可以将给定的图分成两部分。
算法
应通过指示已找到答案或未找到答案而终止。我在网上搜索了一些文章,发现Karger的
最小
割
集
算法
是随机的,它的输出可能不是精确的
最小
割
浏览 6
提问于2016-03-16
得票数 0
3
回答
最小
裁剪器
、
、
编写一个程序,该程序接受一个无向图,并找到
最小
割
集
,即,如果删除,就会将图断开到两个或多个连通组件中的一组边。程序的时间复杂度应为O(n^2m),其中n为顶点数,m为图中的边数。解决这一问题的一种
算法
是Karger
算法
,它是一种随机
算法
,它以较高的概率找到
最小
割
集
。以下是
算法
的高级概述: 初始化“收缩图”,即原始图的副本。
最小
割
集
是将收缩图中的两个剩余顶点连接起来
浏览 0
提问于2023-02-14
得票数 5
1
回答
图论-全局极小
割
集
及其含义
、
、
给定一个加权有向图,我们想要找到全局
最小
割
集
--也就是说,一组边,如果去掉这些边,就会将图分成两半,并且与任何其他的
割
集
相比,它们的总重量
最小
。考虑由全局
最小
割
集
(即s-t- U,V,其中s in U, t in V)分隔的节点
集
。注意:我们不关心从V到U的边缘。对于任何u in U, v in Vm,u
浏览 2
提问于2016-01-24
得票数 1
回答已采纳
1
回答
每条路径中出现的边数最少
、
、
我需要找到一个图中出现在从第一个顶点到最后一个顶点的每条路径中的
最小
边数。示例图像:我已经寻找了一段时间,但没有找到(或想到)任何
算法
来做到这一点……
浏览 1
提问于2013-01-22
得票数 3
回答已采纳
1
回答
枚举图的
最小
割
集
、
、
v1 0 1 0 2 v3 0 3 0 0在我的代码中,矩阵是一个整型矩阵; 现在我想通过枚举得到这个图的
最小
切入点我已经知道一些随机的mincut
算法
,但是对于小的图,我想通过枚举找到mincut,就像Karger和Stein的
算法
中顶点< 6的图一样。这是这个
算法
的伪代码。
浏览 6
提问于2013-04-29
得票数 0
6
回答
如何使用最大流
算法
在图上找到
最小
割线?
、
、
、
、
我需要找到图上的
最小
割线。我一直在读关于流网络的文章,但我所能找到的都是最大流
算法
,如Ford-Fulkerson,push-relabel等。给定最大流-
最小
割
集
定理,是否可以使用这些
算法
中的一种来使用最大流
算法
在图上找到
最小
割
集
?多么? 到目前为止,我找到的最好的信息是,如果我找到“饱和”边,即流量等于容量的边,这些边对应于
最小
切割。的确,
最小
割线上的所有边都是饱和的,但我相信
浏览 6
提问于2010-12-19
得票数 59
1
回答
有向图的闭包--最大闭包问题
、
、
、
然而,在
算法
部分下的最大流段的中,它指出“
割
集
的同一侧的顶点
集
自动形成闭包C”,边的图表示C={s,1,5,3,2}。但是,很明显,有一些边从闭包中出来,例如边(2,t),(s,7)。
浏览 1
提问于2022-02-09
得票数 1
回答已采纳
1
回答
如何通过增加最少的边数来增加图的
最小
割
数
、
、
、
添加
最小
数量的边,这样即使从新创建的图中删除了一条边,仍然存在从任何顶点到任何其他顶点的路径。 我认为这个问题可以简化为将图的
最小
割
集
的大小从目前的
最小
割
集
1增加到2。但是,有什么有效的
算法
可以做到这一点呢?
浏览 1
提问于2012-10-06
得票数 3
回答已采纳
1
回答
寻找图中所有割线的
算法
、
我正在寻找一种有效的
算法
,可以帮助我列出一个图中的所有切割。该图是流网络(有向图),并且具有固定的源和宿。我想找出所有可能的
割
集
,源
集
在一边,sink
集
在另一边。请注意,优先考虑的是找到所有的
割
集
,而不是
最小
割
集
。例如,考虑具有以下边列表的图: s-->a-->t ->b-->t 上图的
割
集
是:{sa,sb},{at,bt},{sa,sb,at},{sa,s
浏览 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包含不同容量的边,容量的增加可能会导致不同的
最小
切割。但是,当所有边都有相同的容量时,
最小
割
集
将保持不变。 我说
浏览 2
提问于2016-10-27
得票数 7
2
回答
在DAG中找到断开一定部分路径的
最小
顶点
集
、
、
、
、
问题如下:给定一个DAG和一个数字0 < p ≤ 1,返回从源(即没有传入弧)到接收器(即没有传出弧)的至少断开路径p-fraction的顶点的
最小
基数
集
。对于p = 1,这个问题等价于
最小
切割。我正在考虑的一个
算法
是首先计算DAG的
最小
割
集
,然后尝试修剪它以满足条件。这本身就很有趣,看看我们找到的子集是否实际上是给定的特定p的
最小
割
集
。这个
算法
的问题在于它是浪费的,因为它计算了许多我们在最终
浏览 5
提问于2015-09-21
得票数 2
1
回答
如何找到分隔一些节点对的整体
最小
割
集
正如我们所知,现在已经有了有效的
算法
来寻找有向图中的整体
最小
割
集
,例如Hao和Orlin (1994)。非常感谢。
浏览 0
提问于2012-12-19
得票数 0
1
回答
作为无向无权图输入的两个任意顶点之间的
最小
割
集
、
、
我有一个无向加权图,我需要找到两个顶点之间的
最小
割
集
。我可以修改我的设置,以便将问题简化为找到分隔两个给定顶点的
最小
割
集
。我想补充的是,权重是正数和小数。Stoer
算法
除了在裁剪的不同侧面保留指定的节点之外,什么都做,我很好奇是否有任何方法修改SW来做到这一点。 谢谢。
浏览 5
提问于2016-03-31
得票数 2
回答已采纳
1
回答
去除K边
算法
后的最大流/
最小
割
流
、
我被要求为以下问题开发一个
算法
:A流网络G,其边的最大容量为1G的最大流f_x_xa正整数K_。,如果K大于或等于max,删除所有穿过G的
最小
割
集
的边,如果K仍然大于零,删除随机边,并且新的最大流是零如果K小于,则删除与G
最小
割
集
相关的边的K,且新的最大流为delete 。最后,我
浏览 0
提问于2020-06-21
得票数 0
回答已采纳
1
回答
求给定最大流的
最小
割
算法
谁能给我一个关于在图(V,E,c,s,t,f)中找到
最小
割
集
的
算法
的想法,其中fv是最大流量,cv是容量?
浏览 2
提问于2012-03-07
得票数 0
1
回答
无向赋权图的s-t
割
、
、
、
、
我在网上了解到,
最小
割
集
等于最大流,并且有一些标准
算法
可以求解有向图的s-t
最小
割
集
。但我似乎找不到太多关于无向图的s-t
割
的材料,我看到人们提到我可以用相反方向的两条有向边替换无向边,以将无向图转换为有向图。然而,当我找到新的有向图的最大流量或
最小
切割时,为什么它与原始的无向图有任何关系?我设想新的有向图的
最小
割线通常应该只包含uv和vu边中的一条,而不是两条边都包含。
浏览 38
提问于2019-03-02
得票数 2
3
回答
合并字典上的键- Python
、
、
我想在python的图表中使用
最小
割
集
算法
,这样:合并字典的更多的琵琶方法是什么
浏览 0
提问于2015-07-29
得票数 1
回答已采纳
点击加载更多
扫码
添加站长 进交流群
领取专属
10元无门槛券
手把手带您无忧上云
相关
资讯
什么是求最小独立边支配集的算法?用C语言实现:求最小独立边支配集的算法。内附完整代码。
R语言最大流最小割定理和最短路径算法分析交通网络流量拥堵问题
React技术栈的最小技能集
算法:44.最小子数组
什么是最小生成树算法?详述最小生成树算法的原理?用C语言实现最小生成树算法。内附完整代码。
热门
标签
更多标签
云服务器
ICP备案
对象存储
实时音视频
云直播
活动推荐
运营活动
广告
关闭
领券