【网络】网络流:最大流最小割问题
网络流问题中的最大流最小割问题。
反过来学习才是最好的掌握和理解路线:
第一、什么是网络流问题?
图中的浅蓝色数字,是实际走的流量,并且构成源点到终点的最大流量。
源节点1到节点4为什么不是7?
因为从节点4流出的水流,加起来才5! 换句话说,到节点4就流不过去这么多了。
至于为何是4,而不是5,同样道理,因为节点3到节点6的容量有限制!
分析到这里大家可能发现了,即使不按照图中浅蓝色数字分配,也可以找到其他水流分配路径,使最大水流量达到10。但没有比10更高的了。
第二、最大流、最小割
上图网络流就是求解最大流的一个实例。10就是求解的最大流。由此,可以引出最大流的一些基本的定义和概念
可以这样看,图就是一种管道,管道有最大通过流量的限制,图中边的权值就是所谓的“容量”。同时,注意有唯一的源点和汇点。
这里需要注意容量和流量的区别。其中f(u,v)的范围需要额外注意,是 0<= f(u,v) <= c(u,v),不会出现所谓的负流量。下图是对可行流的图示
有了可行流,我们还需要求最大流
解决最大流问题的常用到Ford-Fulkerson方法,之所以称其方法而不是算法,是因为在这种思想下包含着若干种时间复杂度不同的实现。
最小割
就是从图G(V,E)中去除一些边,使得图G中源点S到终点T不连通。如果去除的这些边的权和最小,就是最小割。这个权和可以证明等于网络的最大流量!(很明显在上图2中,如果切除边2->4、3->5,就是一个最小割,两条边的权和为7=最大流量7。)
因此 最大流等价于最小割!!! 求解最大流问题,也可以转化为最小割。
求最大流和求最小割集是两类不同的算法。
求解最小割集普遍采用Stoer-Wagner算法
第三、图形分割算法(基于图论的方法)
图形切割算法通过向图G(V,E)添加S点和T点,将图中所有的顶点,与S和T建立边,并根据能量约束方程赋予边权值。就将图形分割与最小割问题相关联!
最后,最小割将图G分为两部分,图中所有顶点分别被划分到两个集合S-node、T-node中。此即图形分割!
Graph cuts是一种十分有用和流行的能量优化算法,在计算机视觉领域普遍应用于前背景分割(Image segmentation)、立体视觉(stereo vision)、抠图(Image matting)等。
首先用一个无向图G=<V,E>表示要分割的图像,V和E分别是顶点(vertex)和边(edge)的集合。此处的Graph和普通的Graph稍有不同。而Graph Cuts图是在普通图的基础上多了2个顶点,这2个顶点分别用符号”S”和”T”表示,统称为终端顶点。其它所有的顶点都必须和这2个顶点相连形成边集合中的一部分。所以Graph Cuts中有两种顶点,也有两种边。
第一种顶点和边是:第一种普通顶点对应于图像中的每个像素。每两个邻域顶点(对应于图像中每两个邻域像素)的连接就是一条边。这种边也叫n-links。
第二种顶点和边是:除图像像素外,还有另外两个终端顶点,叫S(source:源点,取源头之意)和T(sink:汇点,取汇聚之意)。每个普通顶点和这2个终端顶点之间都有连接,组成第二种边。这种边也叫t-links。
最小割问题:就是从图G(V,E)中去除一些边,使得图G中源点S到终点T不连通。如果去除的这些边的权和最小,就是最小割。这个权和可以证明等于网络的最大流量!(很明显在上图2中,如果切除边2->4、3->5,就是一个最小割,两条边的权和为7。)参考链接
网络流问题:
http://wenku.baidu.com/view/7ed3c241a8956bec0975e32b.html
http://www.cnblogs.com/ShaneZhang/p/3755479.html
最大流/最小割算法总结:http://blog.csdn.net/euler1983/article/details/5954650
图像分割:
http://blog.csdn.net/zouxy09/article/details/8532111
最小割问题:就是从图G(V,E)中去除一些边,使得图G中源点S到终点T不连通。如果去除的这些边的权和最小,就是最小割。这个权和可以证明等于网络的最大流量!(很明显在上图2中,如果切除边2->4、3->5,就是一个最小割,两条边的权和为7。)
转载自:http://blog.csdn.net/jingmiaa/article/details/52814814