我能用Stoer算法找到最大割集吗？比方说，我用Stoer算法否定了所有的边权值，并求出了这个图的最小割集，结果割集是原图的最大割集吗？添加了：在Stoer算法中，如果我选择最不紧密连接的顶点，并选择由相位割集返回的所有割集中最大的一个，那么它是全局最大割集吗？为什么或者为什么不？有什么例子吗？
浏览 1提问于2016-12-09得票数 0
1回答
无向加权图划分
、、
维基百科的搜索给我带来了Kernighan-Lin和Fiduccia-Mattheyses算法，但它们似乎是为了解决其他分区问题。
有标准的算法来解决这个问题吗？
浏览 1提问于2015-03-06得票数 1
回答已采纳
1回答
我可以找到的所有算法都使用最大流/最小割集属性来计算将源和接收器分开的最小加权割集。然而，所有这些算法都使用加权和作为最小值的定义，而在我的用例中，权重不是绝对数，而是机会，因此在乘法下必须是最小的，而不是加法来提供适当的最小割集。我无法证明已知的最大流/分钟切割算法背后的思想和属性仍然适用于乘法而不是加法。这些算法能被调整到最小的产品重量削减吗？如果没有，我可以用什么算法来计算这样的切割呢？
浏览 2提问于2018-03-10得票数 1
回答已采纳
1回答
枚举图的最小割集
、、
我已经知道一些随机的mincut算法，但是对于小的图，我想通过枚举找到mincut，就像Karger和Stein的算法中顶点< 6的图一样。这是这个算法的伪代码。
浏览 6提问于2013-04-29得票数 0
1回答
我被要求为以下问题开发一个算法：A流网络G，其边的最大容量为1G的最大流f_x_xa正整数K_。，如果K大于或等于max，删除所有穿过G的最小割集的边，如果K仍然大于零，删除随机边，并且新的最大流是零如果K小于，则删除与G最小割集相关的边的K，且新的最大流为delete 。我需要一
浏览 0提问于2020-06-21得票数 0
回答已采纳
6回答
我一直在读关于流网络的文章，但我所能找到的都是最大流算法，如Ford-Fulkerson，push-relabel等。给定最大流-最小割集定理，是否可以使用这些算法中的一种来使用最大流算法在图上找到最小割集？多么?
到目前为止，我找到的最好的信息是，如果我找到“饱和”边，即流量等于容量的边，这些边对应于最小切割。
浏览 6提问于2010-12-19得票数 59
1回答
我们知道NP -完全和NP-硬，和NP类.我想总结一些关于以下问题的建议，这是从麻省理工学院2008年中期考试开始的。( b)求最大哈密顿循环( d)找出最大切割
怎样才能简单地对这些问题进行分类？即NP或NP-完全或NP-硬。
浏览 1提问于2015-03-27得票数 2
1回答
我遇到了许多问题，这些问题可以被描述为图问题。它一般是NP-硬的，但有时可以证明它是平面的.因此，我有兴趣学习这些问题和算法。据我所知：
希望有人能完成这份清单。
浏览 1提问于2011-06-21得票数 7
回答已采纳
我看到了一种在流网络N=(V，E，c，s，t)中找到最小切分的方法：
*可能还有其他最小的削减，但我要回答的是这样获得的最低削减。
浏览 3提问于2014-01-01得票数 0
1回答
请给出几种无向图最小割集的确定性算法，以及它们的复杂度。(顺便说一句，我知道福特-富尔克森算法有一个无向版本，它为每个有向边缘增加了一个相反的平行边，有人能告诉我这个算法的时间复杂度是多少，或许可以给我更多的参考？)
谢谢。
浏览 7提问于2015-09-16得票数 2
我们知道，福特-富尔克森算法(FFA)将同时产生最大流和最小割解。我的问题是:如果仅限于整数图，多条最大流路径的存在是否意味着多条最小切割路径的存在？我的方法是，如果我们知道FFA可以帮助我们找到不同的最大流量路径，那么我们就知道可以找到不同的对应最小切割。但是我们如何知道FFA是否可以找到不同的最大流量路径呢？
提前感谢！
浏览 1提问于2018-11-11得票数 0
设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割集吗？但是，当所有边都有相同的容量时，最小割集将保持不变。
我说的对吗？如何证明这一点？
浏览 2提问于2016-10-27得票数 7
1回答
我正在阅读这篇维基文章：和我有几个问题。
首先，本文指出“有向图的闭包是一组顶点C，因此没有边离开C”。然而，在算法部分下的最大流段的中，它指出“割集的同一侧的顶点集自动形成闭包C”，边的图表示C={s,1,5,3,2}。但是，很明显，有一些边从闭包中出来，例如边(2，t)，(s，7)。
浏览 1提问于2022-02-09得票数 1
回答已采纳
1回答
无向赋权图的s-t割
、、、、
我在网上了解到，最小割集等于最大流，并且有一些标准算法可以求解有向图的s-t最小割集。但我似乎找不到太多关于无向图的s-t割的材料，我看到人们提到我可以用相反方向的两条有向边替换无向边，以将无向图转换为有向图。然而，当我找到新的有向图的最大流量或最小切割时，为什么它与原始的无向图有任何关系？我设想新的有向图的最小割线通常应该只包含uv和vu边中的一条，而不是两条边都包含。
浏览 38提问于2019-03-02得票数 2
3回答
免责声明:这个是的作业问题。最后期限已经过去了，所以讨论可以继续进行，而不必担心这个问题。
我正在努力解决的问题是确定图G= (V，E)中的一个特定的最小s-t割集是否是唯一的。按照，使用最大流算法可以很简单地找到一些最小裁剪，但是如何显示它是最小剪切呢？
浏览 5提问于2011-10-06得票数 13
回答已采纳
扫码
添加站长 进交流群
领取专属 10元无门槛券
手把手带您无忧上云
相关资讯
热门标签
云服务器
ICP备案
对象存储
即时通信 IM
腾讯会议活动推荐
腾讯云开发者
