注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

hhfighting的博客

以责人之心责己,以恕己之心恕人

 
 
 

日志

 
 
 
 

“Max Flow & Min Cut ”简单入门篇  

2014-08-04 10:53:26|  分类: 专业知识 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
最近在做三维重建表面提取的时候,参考别人的算法使用基于图的优化理论去抽取surface。用到的知识是graph cut的最小割问题,于是系统学习了一下network flow的Max flow和min cut问题。下面做个学习总结。
1 基本概念
(1)图构造:
    包括两个terminal节点:source(s节点)和sink(t节点)。
    节点间edge的权值,称作capacity。
(2)最大流:
    需求从source流向sink的最大流。因为并不是每个edge通过的flow都能达到其capacity,因此会有最大流的问题存在。
(3)最小割
    割是对图进行cut,目的是将source与sink分离,使得一部分节点只与source相连,另外一部分节点与sink相连。割的容量是从source group连向sink group的边的容量的总和。最小割就是所有割中容量最小的划分方法。下面给出一个图的几个割,灰色圈住部分为source group,割容量见图的右下角。
“Max Flow  Min Cut ”简单入门篇 - hhfighting - hhfighting的博客
source group除了s不包含任何节点,这种割也是存在的。

“Max Flow  Min Cut ”简单入门篇 - hhfighting - hhfighting的博客
note:割的容量只是从source group到sink group的edge的capacity之和,不包括从sink group到source group(如上图的节点7->节点3: 6)。
“Max Flow  Min Cut ”简单入门篇 - hhfighting - hhfighting的博客
(4)重要定理
       最大流=最小割
2 流的计算过程
“Max Flow  Min Cut ”简单入门篇 - hhfighting - hhfighting的博客
 
3 相关算法
目前没有对具体的算法进行研究,看到有一篇不错的博客给出了两种算法的详细过程,先保存下:
http://blog.sina.com.cn/s/blog_60a0e97e0101bfj9.html
  评论这张
 
阅读(651)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017