筆記：網路流-基本知識
- 2020 年 4 月 4 日
- 筆記
容量網路的定義
設一個有向連通圖(N=langle V,Erangle)，記(n=|V|,m=|E|).
·容量：每條邊(langle i,jrangle)都對應一個非負實數(c(i,j))
·(N)有兩個特殊頂點(s)和(t)，(s)稱作發點（或源，Source），(t)稱作收點（或匯，Termination）.其餘的頂點稱作中間節點。
·稱(N)為容量網路，記作(N=langle V,E,c,s,trangle).
容量網路上的可行流與最大流
設(f:Erightarrow mathbb{R} ^*)，其中(mathbb{R} ^*)為非負實數集
容量限制
[forall langle i,j rangle in E, f(i,j)le c(i,j) ]
平衡條件
[forall iin V-{s,t}\ sum_{langle j,irangle in E}f(j,i)=sum_{langle i,jrangle in E}f(i,j) ]
滿足以上條件的，稱(f)是(N)上的一個可行流。稱發點(s)的凈流出量為(f)的流量，記作(v(f))，即：
[v(f)=sum_{langle s,jrangle in E}f(s,j)-sum_{langle j,srangle in E}f(j,s) ]
最大流
流量最大的可行流稱作最大流，求給定容量網路(N)上的最大流(f^*)的問題，稱作最大流問題。
網路流建模
多源/多匯問題
具有多個源和多個匯的網路，可以通過在源之前（或者匯之後）添加一個節點的方式轉換為單源單匯問題，如下圖
正向邊反向邊共存問題
如果兩個頂點之間有方向相反的兩條邊連接，可以在其中一條邊上增加一個頂點（如下圖綠色頂點），這樣可以保證每兩個頂點之間只有一條邊。
最大流問題的線性規劃表述
一個最大流問題可以描述成如下的LP模型
[max v(f)\ {rm s.t.}quadquad f(i,j)le c(i,j), langle i,jrangle in E \ sum_{langle j,irangle in E}f(j,i)-sum_{langle i,jrangle in E}f(i,j)=0, forall iin V-{s,t}\ v(f)-sum_{langle s,jrangle in E}f(s,j)+sum_{langle j,srangle in E}f(j,s)=0, f(i,j)ge 0, langle i,jrangle in E \ v(f)ge 0 ]
割集、割集的容量、最小割集
設容量網路(N=langle V,E,c,s,trangle，Asubset V)且(sin A, tin overline A)，稱:
[(A,overline A)={langle i，jrangle|langle i，jranglein E且iin A,jin overline A} ]
為(N)的割集；割集可以這麼理解：將這個網路劃分為兩個部分，源(s)位於其中一個部分，匯(t)位於另一部分，而這兩個部分相互不連通，為了使這兩部分不連通所需要砍掉的邊構成的集合就是割集。
稱：
[c(A,overline A)=sum_{langle i,jrangle in (A,overline A)}c(i,j) ]
為割集((A,overline A))的容量。容量最小的割集稱作最小割集。
