GraphCut、最大流最小割定理

G=（V，E）；V为点集，E为边集；

节点集V中的节点分为：

（1）终端节点。不包含图像像素，用S和T表示。S为源点，T为汇点。图像分割中通常用S表示前景目标，标签设为1；T表示背景，标签为0。

（2）除了S和T以外的普通节点。每个节点与图像中的像素对应，记为集合P。

不同节点连接的边不同，可以分为：

（1）普通节点和源点/汇点之间的连接，记为T-links

（2）两个普通节点之间连接的边，记为N-links

图中每条边的权值W（Vi,Vj）非负，代表相邻两个像素在颜色、纹理上特性的相似度。

最大流最小割定理

S-T网络图中的非负权值可以理解为代价。一个割就是图中代表边集合E的其中一个子集C，且这个割的代价为子集C的所有连接边的权值的总和。用c（S，T）表示：

割是边的集合。把割断开，这个集合中的所有边也会断开，这时S和T就是两个部分。若某个割(边的其中一个集合)的这个集合中边的所有权值总和最小，也就是代价最小，这个割称为最小割。同样的，从源点流入汇点的流就为最大值，被称为最大流。

使用最大流最小割定理可以获得网络图的最小割。
在网络流图G中，用F表示网络图G的总流量，当最小割时的容量G即为源点到汇点的最大流值，算法用公式表示为:

在使用时需要初始化一个值为0的流，然后不断寻找从源点S到汇点T的增广路径，可以在正向边上增加流，也可以在反向边上减少流，当所有的路径满足正向边是满的或者反向边是空的时，此时网络图可以分为两个相互不流通的子集，并且子集内部相似度最高，算法结束。