问题标签 [minimum-cut]

如果有人可以帮助我，那就太好了。

我有一个无向图，其中每个顶点都有权重，而没有边有权重。我想找到一组总权重最小的节点，它们的删除会使图表断开连接。例如，在删除一个权重为 10 的节点使图断开连接和删除总权重为 6 的 2 个节点使图断开连接之间，结果集应包含这 2 个节点。

这个问题有什么已知的算法吗？

这是我到目前为止所做的。我使用networkx（python）制作了我的代码。我已经将我的图表更改为定向。例如，对于节点 1，我考虑 1in 和 1out 节点。我通过节点 1 的权重将 1in 连接到 1out。我还添加了 s 和 t 节点（我不确定它是否正确）。我还定义了新有向图中每条边的容量。

运行代码时，我收到此错误：NetworkXUnbounded: Infinite capacity path, flow unbounded above.

谢谢

我最近对图论感兴趣。我遇到了有向图的 st 切割。我在网上了解到最小割等于最大流量，并且有标准算法可以解决有向图的最小割。

但是我似乎找不到太多关于无向图的 st 割的材料，我看到有人提到我可以用两个相反方向的有向边替换一个无向边，以将无向图转换为有向图。但是，当我找到新的有向图的最大流或最小割时，为什么它与原始无向图有任何关系？我想新的有向图的最小切割通常应该只包含uv和vu边之一，但不能同时包含两者。

我只是看不出转换后的有向图与原始无向图有什么关系。

我一直在学习流程图，根据我所学到的，流程图是一个有向的加权图，它具有可以计算的某个最大流量。但是，有没有办法用一定范围内的值随机加权图形并逐渐改变权重以最大化最大流量？

流网络中的临界边G = (V,E)被定义为这样一条边，即降低该边的容量会导致最大流量减少。另一方面，瓶颈边缘是这样的边缘，其容量的增加也会导致网络中最大流量的增加。所有关键边缘也是瓶颈边缘吗？我无法证明这一点或给出反例。

我将不胜感激任何帮助！

我正在寻找最小多切算法的实现。我的问题类似于此处定义的问题，我引用：

最小多切。输入包含一个加权的无向图 G = (V,E)，对于 E 中的每条边具有非负权重 c_k，以及一组终端对 {(s1,t1);(s2,t2)... (sk,tk)}。多割是一组边，其删除会断开每个终端对。

不同之处在于我正在考虑有向图。我知道这个问题是 NP 难的，但是为了获得更有效的算法，可以进行一些近似。但是，我找不到任何实现，甚至找不到明确的伪算法。

任何帮助都感激不尽！

我需要证明给定一个网络流 G 和一个最大流 f，通过一个最小割，所有饱和边都在这个最小割中。即，我试图通过矛盾假设存在饱和但不在最小切割中的边缘 e，并且我想证明这与切割的奇异性相矛盾，但我不确定为什么这是真的。很乐意为如何从这里继续提供帮助，谢谢！