一.網絡流:流&網絡&割
1.網絡流問題(NetWork Flow Problem):
給定指定的一個有向圖,其中有兩個特殊的點源S(Sources)和彙T(Sinks),每條邊有指定的容量(Capacity),求滿足條件的從S到T的最大流(MaxFlow).
下面給出一個通俗點的解釋
(下文基本避開形式化的證明 基本都用此類描述叙述)
好比你家是彙 自來水廠(有需要的同學可以把自來水廠當成銀行之類 以下類似)是源
然後自來水廠和你家之間修了很多條水管子接在一起 水管子規格不一 有的容量大 有的容量小
然後問自來水廠開閘放水 你家收到水的最大流量是多少
如果自來水廠停水了 你家那的流量就是0 當然不是最大的流量
但是你給自來水廠交了100w美金 自來水廠拼命水管裡通水 但是你家的流量也就那麼多不變了 這時就達到了最大流。
-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
2.三個基本的性質:
如果 C代表每條邊的容量 F代表每條邊的流量
一個顯然的實事是F小于等于C 不然水管子就爆了
這就是網絡流的第一條性質 容量限制(Capacity Constraints):F<x,y> ≤ C<x,y>
再考慮節點任意一個節點 流入量總是等于流出的量 否則就會蓄水(爆炸危險...)或者平白無故多出水(有地下水湧出?)
這是第二條性質 流量守恒(Flow Conservation):Σ F<v,x> = Σ F<x,u>
當然源和彙不用滿足流量守恒 我們不用去關心自來水廠的水是河裡的 還是江裡的。
最後一個不是很顯然的性質 是斜對稱性(Skew Symmetry): F<x,y> = - F<y,x>
這其實是完善的網絡流理論不可缺少的 就好比中學實體裡用正負數來定義一維的位移一樣
百米起點到百米終點的位移是100m的話 那麼終點到起點的位移就是-100m
同樣的 x向y流了F的流 y就向x流了-F的流。
--------------------------------------------------------------------------------------------------------------------------------------------------
3.容量網絡&流量網絡&殘留網絡:
網絡就是有源彙的有向圖 關于什麼就是指邊權的含義是什麼
容量網絡就是關于容量的網絡 基本是不改變的(極少數問題需要變動)。
-------------------------------------------------------------------------------------------------------------------------------------------------------
流量網絡就是關于流量的網絡 在求解問題的過程中
通常在不斷的改變 但是總是滿足上述三個性質
調整到最後就是最大流網絡 同時也可以得到最大流值。
-------------------------------------------------------------------------------------------------------------------------------------------------------
----------------------------------------------------------------------------------------------------------------------------------------------------------------------
殘留網絡往往概括了容量網絡和流量網絡 是最為常用的
殘留網絡=容量網絡-流量網絡
這個等式是始終成立的 殘留值當流量值為負時甚至會大于容量值
流量值為什麼會為負?有正必有負,記住斜對稱性!
-------------------------------------------------------------------------------------------------------------------------------------------
---------------------------------------------------------------------------------------------------------------------------------------
4.割&割集:
無向圖的割集(Cut Set):C[A,B]是将圖G分為A和B兩個點集 A和B之間的邊的全集
A set of edges of a graph which, if removed (or "cut"), disconnects the graph (i.e., forms a disconnected graph).
網絡的割集:C[S,T]是将網絡G分為s和t兩部分點集 S屬于s且T屬于t 從S到T的邊的全集
帶權圖的割(Cut)就是割集中邊或者有向邊的權和。
通俗的了解一下:
割集好比是一個恐怖分子 把你家和自來水廠之間的水管網絡砍斷了一些
然後自來水廠無論怎麼放水 水都隻能從水管斷口嘩嘩流走了 你家就停水了。
割的大小應該是恐怖分子應該關心的事 畢竟細管子好割一些
而最小割花的力氣最小。
-------------------------------------------------------------------------------------------------------------------------------------------
二.計算最大流的基本算法
那麼怎麼求出一個網絡的最大流呢?
這裡介紹一個最簡單的算法:Edmonds-Karp算法 即最短路徑增廣算法 簡稱EK算法
EK算法基于一個基本的方法:Ford-Fulkerson方法 即增廣路方法 簡稱FF方法
增廣路方法是很多網絡流算法的基礎 一般都在殘留網絡中實作
其思路是每次找出一條從源到彙的能夠增加流的路徑 調整流值和殘留網絡 不斷調整直到沒有增廣路為止
FF方法的基礎是增廣路定理(Augmenting Path Theorem):網絡達到最大流當且僅當殘留網絡中沒有增廣路
證明略 這個定理應該能夠接受的吧
EK算法就是不斷的找最短路 找的方法就是每次找一條邊數最少的增廣 也就是最短路徑增廣
這樣就産生了三個問題:
-------------------------------------------------------------------------------------------------------------
1.最多要增廣多少次?
可以證明 最多O(VE)次增廣 可以達到最大流 證明略
2.如何找到一條增廣路?
先明确什麼是增廣路 增廣路是這樣一條從s到t的路徑 路徑上每條邊殘留容量都為正
把殘留容量為正的邊設為可行的邊 那麼我們就可以用簡單的BFS得到邊數最少的增廣路
3.如何增廣?
BFS得到增廣路之後 這條增廣路能夠增廣的流值 是路徑上最小殘留容量邊決定的
把這個最小殘留容量MinCap值加到最大流值Flow上 同時路徑上每條邊的殘留容量值減去MinCap
最後 路徑上每條邊的反向邊殘留容量值要加上MinCap 為什麼? 下面會具體解釋
-------------------------------------------------------------------------------------------------------------
這樣每次增廣的複雜度為O(E) EK算法的總複雜度就是O(VE^2)
事實上 大多數網絡的增廣次數很少 EK算法能處理絕大多數問題
平均意義下增廣路算法都是很快的
增廣路算法好比是自來水公司不斷的往水管網裡一條一條的通水
上面還遺留了一個反向邊的問題: 為什麼增廣路徑上每條邊的反向邊殘留容量值要加上MinCap?
因為斜對稱性! 由于殘留網絡=容量網絡-流量網絡
容量網絡不改變的情況下
由于增廣好比給增廣路上通了一條流 路徑說所有邊流量加MinCap
流量網絡中路徑上邊的流量加MinCap 反向邊流量減去MinCap
相對應的殘留網絡就發生相反的改變
這樣我們就完成了EK算法 具體實作可以用鄰接表存圖 也可以用鄰接矩陣存圖
鄰接表存圖 由于流量同時存在于邊與反向邊 為了友善求取反向邊 建圖把一對互為反向邊的邊建在一起
代碼很簡單 最好自己實作一下。
----------------------------------------------------------------------------------------------------------------------------------------
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
三.最大流最小割定理
下面介紹網絡流理論中一個最為重要的定理
最大流最小割定理(Maximum Flow, Minimum Cut Theorem):網絡的最大流等于最小割。
The maximum flow between vertices v_i and v_j in a graph G is exactly the weight of the smallest set of edges to disconnect G with v_i and v_j in different components.
具體的證明分三部分
1.任意一個流都小于等于任意一個割
這個很好了解 自來水公司随便給你家通點水 構成一個流
恐怖分子随便砍幾刀 砍出一個割
由于容量限制 每一根的被砍的水管子流出的水流量都小于管子的容量
每一根被砍的水管的水本來都要到你家的 現在流到外面 加起來得到的流量還是等于原來的流
管子的容量加起來就是割 是以流小于等于割
由于上面的流和割都是任意構造的 是以任意一個流小于任意一個割
2.構造出一個流等于一個割
當達到最大流時 根據增廣路定理
殘留網絡中s到t已經沒有通路了 否則還能繼續增廣
我們把s能到的的點集設為S 不能到的點集為T
構造出一個割集C[S,T] S到T的邊必然滿流 否則就能繼續增廣
這些滿流邊的流量和就是目前的流即最大流
把這些滿流邊作為割 就構造出了一個和最大流相等的割
3.最大流等于最小割
設相等的流和割分别為Fm和Cm
則因為任意一個流小于等于任意一個割
任意F≤Fm=Cm≤任意C
定理說明完成。
--------------------------------------------------------------------------------------------------------------------------------------------------------------------------
四.簡單的應用
Poj 1459是一個很典型的網絡流應用
把電流想象成水流。