1回答
我正在寻找一个算法，以找到一个无向图的全局小割集。我想输入一个图和算法输出最小的边数，通过切割它们，可以将给定的图分成两部分。
算法应通过指示已找到答案或未找到答案而终止。我在网上搜索了一些文章，发现Karger的最小割集算法是随机的，它的输出可能不是精确的最小割集。我可
浏览 6提问于2016-03-16得票数 0
1回答
我可以找到的所有算法都使用最大流/最小割集属性来计算将源和接收器分开的最小加权割集。然而，所有这些算法都使用加权和作为最小值的定义，而在我的用例中，权重不是绝对数，而是机会，因此在乘法下必须是最小的，而不是加法来提供适当的最小割集。我无法证明已知的最大流/分钟切割算法背后的思想和属性仍然适用于乘法而不是加法。这些算法能被调整到最小</e
浏览 2提问于2018-03-10得票数 1
回答已采纳
我能用Stoer算法找到最大割集吗？比方说，我用Stoer算法否定了所有的边权值，并求出了这个图的最小割集，结果割集是原图的最大割集吗？添加了：在Stoer算法中，如果我选择最不紧密连接的顶点，并选择由相位割集返回的所有割集中最大的一个，那么它是全局最大割集吗？为什么或者为什么不？有什么例子吗？
浏览 1提问于2016-12-09得票数 0
1回答
带权值的Karger算法
、、、、
其目的是计算最小代价G的最小割集(即由最小边数构成的割集之间的最小成本削减)。给出了一种高概率的算法，在多项式时间内找到这样的最小代价最小削减。您的算法运行时间是多少？提示: Karger算法
方法二:当卡格的边缘收缩时，提高高权重的概率。
浏览 3提问于2019-08-17得票数 1
3回答
最小裁剪器
、、
编写一个程序，该程序接受一个无向图，并找到最小割集，即，如果删除，就会将图断开到两个或多个连通组件中的一组边。程序的时间复杂度应为O(n^2m)，其中n为顶点数，m为图中的边数。解决这一问题的一种算法是Karger算法，它是一种随机算法，它以较高的概率找到最小割集。以下是算法的高级概述：该算法通
浏览 0提问于2023-02-14得票数 5
6回答
我需要找到图上的最小割线。我一直在读关于流网络的文章，但我所能找到的都是最大流算法，如Ford-Fulkerson，push-relabel等。给定最大流-最小割集定理，是否可以使用这些算法中的一种来使用最大流算法在图上找到最小割集？多么?
到目前为止，我找到的最好的信息是，如果我找到“饱和”边，即流量等于容量的边，这些边对应于最小切割。的确，最小割线上的所有边都是饱和的，但我相信也可能有饱和的边在
浏览 6提问于2010-12-19得票数 59
1回答
给定一个加权有向图，我们想要找到全局最小割集--也就是说，一组边，如果去掉这些边，就会将图分成两半，并且与任何其他的割集相比，它们的总重量最小。考虑由全局最小割集(即s-t- U,V，其中s in U, t in V)分隔的节点集。注意:我们不关心从V到U的边缘。对于任何u in U, v in Vm，u-v-切不能小于s-t-cut，否则，s-t-削减将不
浏览 2提问于2016-01-24得票数 1
回答已采纳
1回答
枚举图的最小割集
、、
v1 v2 v3 v4 v2 1 0 3 0 v4 2 0 0 0
在我的代码中，矩阵是一个整型矩阵；现在我想通过枚举得到这个图的最小切入点。但我不知道该怎么做。我已经知道一些随机的mincut算法，但是对于小的图，我想通过枚举找到mincut，就像Karger和Stein的算法中顶点< 6的图一样。这是这个算法的伪代码。
浏览 6提问于2013-04-29得票数 0
1回答
我需要找到一个图中出现在从第一个顶点到最后一个顶点的每条路径中的最小边数。例如，在图像中，如果第一个顶点是V0，最后一个顶点是V8，那么从V0到V8的每条路径中出现的最少顶点数是2，并且它们是绿色的(或者代替V6-V8可能是V0-V3或V3-V6)。示例图像：我已经寻找了一段时间，但没有找到(或想到)任何算法来做到这一点……
浏览 1提问于2013-01-22得票数 3
回答已采纳
1回答
添加最小数量的边，这样即使从新创建的图中删除了一条边，仍然存在从任何顶点到任何其他顶点的路径。
我认为这个问题可以简化为将图的最小割集的大小从目前的最小割集1增加到2。但是，有什么有效的算法可以做到这一点呢？
浏览 1提问于2012-10-06得票数 3
回答已采纳
2回答
问题如下:给定一个DAG和一个数字0 < p ≤ 1，返回从源(即没有传入弧)到接收器(即没有传出弧)的至少断开路径p-fraction的顶点的最小基数集。对于p = 1，这个问题等价于最小切割。我正在考虑的一个算法是首先计算DAG的最小割集，然后尝试修剪它以满足条件。这本身就很有趣，看看我们找到的子集是否实际上是给定的特定p的最小割集。这个算法的问题在于它是浪费的，因为它计算了许多我们在最终答案中不需要的节点，实际上，首先是解
浏览 5提问于2015-09-21得票数 2
但所有的文章都描述了平面图的算法--不用说，我有非平面的无向图。此外，我更喜欢函数式C/C++代码，而不是高级算法描述。
浏览 3提问于2010-11-17得票数 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
1回答
然而，在算法部分下的最大流段的中，它指出“割集的同一侧的顶点集自动形成闭包C”，边的图表示C={s,1,5,3,2}。但是，很明显，有一些边从闭包中出来，例如边(2，t)，(s，7)。
浏览 1提问于2022-02-09得票数 1
回答已采纳
2回答
给定一个随机的无向图，我必须找到从一个顶点到另一个顶点的“瓶颈边”(编辑:最小割边)。我称之为“瓶颈边”(编辑:最小割边) --假设我有以下无向图： / | \ | | \ | /为了独立于所选的路径从A到H，边BE和DG必须始终被遍历，因此形成了“瓶颈”(编辑:最小切割)。有没有一个多项式时间的算法？
浏览 0提问于2011-04-28得票数 7
回答已采纳
正如我们所知，现在已经有了有效的算法来寻找有向图中的整体最小割集，例如Hao和Orlin (1994)。非常感谢。
浏览 0提问于2012-12-19得票数 0
1回答
我被要求为以下问题开发一个算法：A流网络G，其边的最大容量为1G的最大流f_x_xa正整数K_。，如果K大于或等于max，删除所有穿过G的最小割集的边，如果K仍然大于零，删除随机边，并且新的最大流是零如果K小于，则删除与G最小割集相关的边的K，且新的最大流为delete 。最后，我得到的最大流/最小
浏览 0提问于2020-06-21得票数 0
回答已采纳
1回答
我正在寻找一种有效的算法，可以帮助我列出一个图中的所有切割。该图是流网络(有向图)，并且具有固定的源和宿。我想找出所有可能的割集，源集在一边，sink集在另一边。请注意，优先考虑的是找到所有的割集，而不是最小割集。例如，考虑具有以下边列表的图: s-->a-->t ->b-->t
上图的割集是：{sa，sb}，{at，bt}，{sa，sb，at}，{sa，sb，bt}，{sa，sb，at，bt}
浏览 4提问于2013-02-24得票数 1
1回答
无向赋权图的s-t割
、、、、
我在网上了解到，最小割集等于最大流，并且有一些标准算法可以求解有向图的s-t最小割集。但我似乎找不到太多关于无向图的s-t割的材料，我看到人们提到我可以用相反方向的两条有向边替换无向边，以将无向图转换为有向图。然而，当我找到新的有向图的最大流量或最小切割时，为什么它与原始的无向图有任何关系？我设想新的有向图的最小割线通常应该只包含uv和vu边中的一条，而不是两条边都包含。
浏览 38提问于2019-03-02得票数 2
扫码
添加站长 进交流群
领取专属 10元无门槛券
手把手带您无忧上云
相关资讯
热门标签
云服务器
ICP备案
对象存储
即时通信 IM
实时音视频活动推荐
腾讯云开发者
