开发者社区

文档建议反馈控制台

文章/答案/技术大牛

发布

社区首页 >问答首页 >为什么网络流的全局最小割基数小于每个顶点的度数

问为什么网络流的全局最小割基数小于每个顶点的度数
EN

Stack Overflow用户

提问于 2019-12-15 08:30:58

回答 1查看 51关注 0票数 1

我得到了最小切割等于最大流量。但是为什么每个节点的度数必须大于全局最小割集的基数才有效呢

graph-algorithm

EN

Stack Overflow用户

回答已采纳

发布于 2019-12-15 21:23:55

对于每个节点，从图的其余部分剪切该节点将产生与该节点的度数相等的大小的切割，因此全局最小切割不能更大。

票数 1

EN

查看全部 1 条回答

页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持

原文链接：

https://stackoverflow.com/questions/59340312

复制

相似问题