基本概念

数据结构—图：一个图G(V,E)是由一系列的顶点（vertices，V）和边（edges，E）构成的数据结构，给每条边赋予一定的数值代表该边的权值（使用中可以用于表示特定的意义），这样的图成为网络（weighted graph），边没有方向的图称为无向图（undirected graph），其边用(Vi,Vj)表示，边有方向的图成为有向图（directed graph），其边用表示。如下图所示：
图中的相关概念：
源点(source)：图中有一个点很特殊，只出不进，叫做源点。
汇点(sink)：图中与源点相对应的另一个特殊点，只进不出，叫做汇点。
容量(capacity)和流量(flow)：每条有向边上有两个量，容量和流量，从i到j的容量通常用c[i,j]表示,流量则通常是f[i,j]。
最大流(max-flow)：从源点出发，选择一条路径到达汇点，其中经过的所有边中容量最小的边的容量即为该路径的最大流。如下图中由顶点1经顶点2、4到达顶点6的最大流为1。

Max-flow/Min-cut

graph-cut算法是基于有向图的一种最优分界线的自动生成算法，常用于前景背景分割，立体视觉，纹理合成及图像拼接等领域。graph-cut算法中要求所处理的图为有向图，可将无向图中正反两个方向都赋予相同的权值即可得到可采用graph-cut算法处理的有向图，其算法流程可以简单表示如
1.Find the path from source to sink
2.While (path exists)
3.flow += maximum capacity in the path
4.Build the residual graph (“subtract” the flow)
5.Find the path in the residual graph
6.End

其中步骤1即为图的遍历；步骤4中的残余图是在沿源点到达汇点的边的权值减去该路径的最大流，同时在其反方向即该路径上从汇点到达源点的路径上边的权值加上该路径的最大流；
当循环结束后图被分割为两部分，一部分是源点可以到达的顶点，另一部分是源点不可到达的顶点，这样就将影像分为了两个部分，其分界处成为cut即分界线。此处将原始图中边的上的权值视为开销的话该算法得到的cut分界线就是使开销最小的全局最优的结果之一（结果并不一定是唯一的）。

为便于理解可以将源点视为水源，将汇点视为水槽，边的权值看作水管的粗细，每段水管只能用一次，只有水源和水槽可以存储水，水管不具备储水能力(在图示例中有水从顶点2流到顶点4就有相应的水从顶点4流回顶点2，即f[2,4]=0），这样当水槽里蓄到一定量的水后就再也没有可以由水源到达水槽可用的水管了。
相关资料：
maxfow/mincut代码
grahp-cut算法介绍ppt（牛津大学）
garph-cut算法介绍资料
相关论文：
“Graphcut Textures - Image and Video Synthesis Using Graph Cuts”
“Graph Cuts in Vision and Graphics: Theories and Applications”
“Interactive Graph Cuts for Optimal Boundary & Region Segmentation of Objects in N-D Images”
“Optimal Seamline Detection for Multiple Image Mosaicking via Graph Cuts”
“Graph Cut Algorithms in Vision Graphics and Machine Learning”
“Fast image blending using watersheds and graph cuts”
““GrabCut” — Interactive Foreground Extraction using Iterated Graph Cuts”