会计学割的定义(dìngyì)s-t图1.一个源点和一个汇点2.有向边，<i,j>是从i到j的3.每一条边都有一个非负的权值4.容量cap(i,j)等于零，说明不存在(cúnzài)边s-t切割的代价1.S,T的容量是所有容量函数的总和2.最小割是S-T切割中所有可能的S-T切割的能量最小的割跨越S-T切割的流值是所有f(i,j)-f(j,i)的值注意(zhùyì)：如果一条弧的两个顶点分别属于(shǔyú)顶点集S和T（一个顶点在S,另一个在T），这条弧称为割CUT(S.T)的一条割边。从S指向T的割边是正向割边。从T指向S的割边是逆向割边。割CUT（S,T）中所有正向割边的容量和，称为割CUT（S,T）的容量。不同割的容量不同。最小割，就是指所有割中权重之和最小的一个割。/网络(wǎngluò)流和割的关系定理二：在网络(wǎngluò)中，如果f是一个流，CUT(S,T)是一个割，且f的值等于割CUT(S,T)的容量，那么f是一个最大流，CUT(S,T)是一个最小割。最大流最小割定理(dìnglǐ)结论一：最大流时，最小割cut(S,T)中，正向割边的流量=容量，逆向割边的流量为0。结论二：在最小割cut(S,T)中:1.源点s属于S2.如果i属于S，结点j满足：有弧<i,j>,并且c[i,j]>f[i,j],或者有弧<i,j>,并且f[i,j]>0,那么j属于S。//否则不是最小割。即，从s出发能找到的含有残留(cánliú)的点组成集合S，其余的点组成集合T。形象(xíngxiàng)的比喻：