如何检查图形网络是否包含唯一的最大流量？是否有任何多项式时间算法可以做到这一点？谢谢！编辑：查找源和接收器之间的所有切口 . 对于每次切割，如果有两个边缘具有最小容量，则最大值不能是唯一的 . 返回false . 如果所有削减都具有单个最小容量，则返回true . 但我需要一个更有效的算法 .edit2：我需要知道图形网络是否具有唯一的最大流量（我只能以一种方式从源到接收器发送最大流量） .
我认为没有任何2级顶点，否则你可以收缩其中一个边缘并相应地更新另一个顶点的容量 . 类似的东西适用于平行边缘 . 我们可以找到任意最大流量，然后从图形中的流中删除一条边 . 检查还有另外一个量相同的流量 . 如果没有，请添加回删除的边缘并对另一边执行相同的操作 . 与您之前的尝试（找到所有切割，可以是指数）不同，此算法是gragh大小的多项式 .
1 回答
我认为没有任何2级顶点，否则你可以收缩其中一个边缘并相应地更新另一个顶点的容量 . 类似的东西适用于平行边缘 . 我们可以找到任意最大流量，然后从图形中的流中删除一条边 . 检查还有另外一个量相同的流量 . 如果没有，请添加回删除的边缘并对另一边执行相同的操作 . 与您之前的尝试（找到所有切割，可以是指数）不同，此算法是gragh大小的多项式 .