什么是最小割

来源：百度知道 编辑：UC知道 时间：2024/09/28 07:17:09
请高手回答详细点..初学者...时间多的可以说一说最大流和最小割的关系 -.-! 本人学的是Free Pascal

割就是流网络G=(V,E)的割(S,T)将划分成S和T=V-S两部分，使得s∈S，t∈T
也就是原点和汇点在两个不同的子集中
最小割是指流网络中容量最小的割
在流网络中，最小割的容量等于最大流的流量（Ford-Fulkerson定理）

都最小割了还初学者啊 呵呵