最大流、最小割小结
Part I
网络流问题博大精深,目前我们只学习了其中的一点皮毛,初步认识了最大流问题及其 Edmonds-Karp 算法,了解最小割与最大流之间的联系,初步掌握了利用最大流解决某些二分图匹配问题的方法,因此在这里就谈谈我对网络流的理解。
网络流问题中最经典的是最大流问题,而这也是我们目前学习的重点,就从最大流问题开始叙述。
如图所示,假设需要把一些物品从结点
图 b 展示了一种可能的方案,其中每条边中的第一个数字表示实际运送的物品数目,而第二个数字就是题目中的上限。
这样的问题称为最大流问题(Maximum-Flow Problem)。对于一条边
首先需要明确,合法的情况必须满足如下限制:
- 容量限制,对于任意点对
(u,v) ,0≤f(u,v)≤c(u,v) - 物品在传输过程中不会额外增加,也不会意外减少,收到的物品数量与发出的物品数量言相等,即对于任意
v∈V∖{s,t} ,∑e∈δ_(v)f(e)=∑e∈δ+(v)f(e)
目标是最大化从
很显然可以想到一种直观的贪心算法:不断找
例如,对于下面的这个例子:
如果根据上面的贪心算法,先沿着
但是,可以举出反例。先沿着
比较两种策略,我们发现,后一种通过将原先得到的流给“推回去”(在 1 -> 2 这条边)而得到了新的流。因此,我们需要给一个“反悔”的机会。
为了方便,不妨对于每条边,只考虑其
关于如何“反悔”,具体地,图中的每条有向边
这个算法就是著名的 Ford-Fulkerson 算法,也常被称作 Edmonds-Karp 算法。需要注意的是,由于每次都要寻找增广路,最坏情况下算法效率可能会很低。
为什么该算法是正确的呢?先来介绍最小割问题。
所谓图的割,是指对于某个顶点集合
如果有
接下来就是证明部分了,思想非常玄妙,并非完全自己打的,参考了一些资料,主要是注重理解,先记下。
对于任意一个割,连接
而在所有可能的割中,存在一个容量最小的割,我们称其为最小割(minimum cut)。
这个最小割限制了一个网络的流
但是这和增广路又有什么关系呢?
利用上面讲的知识,我们可以推出一个最大流最小割定理:(《挑战程序设计竞赛》中也有讲,但我觉得没有下面的直观)
对于一个网络流图
- 流
f 是图G 的最大流 - 残留网络不存在增广路
- 对于
G 的某一个割(S,T) ,此时f=C(S,T)
首先证明 1 => 2:
我们利用反证法,假设流
接着证明 2 => 3:
因为残留网络不存在增广路,所以在残留网络中不存在路径从
因此有
最后证明 3 => 1:
由于
这样就说明了为什么找不到增广路时,所求得的一定是最大流。同时也证明了最小割最大流定理。
Part II
最近针对最小割的练习,我认为其中两道解题的关键都可以归纳为:把题目转化为“总-弃=得”,“总”是一定的,要最大化“得”,就要最小化“弃”,从而得到最小割模型,再根据最小割最大流定理,用所学的最大流算法解决。
除此之外,到目前为止,我们所解的网络流题目(虽然只有五六题)几乎都与二分图有关,无论是匹配还是点独立集等等。这应该是网络流当中很经典也很重要的组成部分,《挑战程序设计竞赛》上有专门介绍相关问题,我粗略看了其中的一部分,但还没有能够完全理解。接下来打算找时间看看,也结合《算法竞赛入门经典训练指南》一起,做做习题。个人感觉到了网络流部分的学习,需要较强的空间抽象思维能力,所以会觉得有些吃力。解题,建对模型是成功的一大半。
关于最大流的求解算法,目前只会 Edmonds-Karp。其实之前自己看过一点 Dinic,但只打了遍模板,没有做题巩固,现在都忘了。这就像我的 kmp 一样,来得快,去得也快,消失得无影无踪。“熟能生巧”真的很有道理,现在叫我打 EK,不用花 3 分钟都可以搞定。但是过了几个月再来看呢?
所以学习一定要自觉复习,才能掌握牢固。而且,为了让自己在遗忘时能回忆起来,一定要写好笔记。我自己也应该持续更新博客,记录学习过程中的点点滴滴。
网络流其实是一个很广的话题,最大流、最小割都还只是其中一个部分。(当然,就这个部分都需要长时间的练习和钻研才能掌握好)还有最小费用流之类的东西,果然还是有很长的路要走。越是到风景壮丽的地方,就会更加的崎岖险阻。希望即使集训结束后也能够自觉坚持,为即将到来的 NOIp 2017 做充分准备。