網(wǎng)絡(luò)流知識(shí)大全

2019-11-11 07:15:45

字體：大中小

供稿：網(wǎng)友

引入： 圖論中的一種理論與方法，研究網(wǎng)絡(luò)上的一類最優(yōu)化問題。很多系統(tǒng)中涉及流量問題，例如公路系統(tǒng)中車流量，網(wǎng)絡(luò)中的數(shù)據(jù)信息流，供油管道的油流量等。我們可以將有向圖進(jìn)一步理解為“流網(wǎng)絡(luò)”(flow network)，并利用這樣的抽象模型求解有關(guān)流量的問題。 一：最大流 1.簡(jiǎn)介求解網(wǎng)絡(luò)流的基本思想就是每次尋找增廣路(就是源點(diǎn)到匯點(diǎn)的一條可行路)然后ans+=增廣路能流過的流量，更新剩余網(wǎng)絡(luò)，然后再做增廣路，直到做不出增廣路。關(guān)于網(wǎng)絡(luò)流入門最難理解的地方就是剩余網(wǎng)絡(luò)了….為什么在找到一條增廣路后…不僅要將每條邊的可行流量減去增廣路能流過的流量…還要將每條邊的反向弧加上增廣路能流過的流量.?..原因是在做增廣路時(shí)可能會(huì)阻塞后面的增廣路…或者說做增廣路本來是有個(gè)順序才能找完最大流的…..但我們是任意找的…為了修正…就每次將流量加在了反向弧上…讓后面的流能夠進(jìn)行自我調(diào)整…剩余網(wǎng)絡(luò)的更新(就在原圖上更新就可以了) 最大流算法： 首先來看若干個(gè)概念（1）流網(wǎng)絡(luò)G=(V,E)是一個(gè)有向圖，其中每條邊(u,v)∈E均有一個(gè)非負(fù)容量c(u,v)>=0。如果(u,v)不屬于E，則假定c(u,v)=0。流網(wǎng)絡(luò)中有兩個(gè)特別的頂點(diǎn)：源點(diǎn)s和匯點(diǎn)t。（2）對(duì)一個(gè)流網(wǎng)絡(luò)G=(V,E)，其容量函數(shù)為c，源點(diǎn)和匯點(diǎn)分別為s和t。G的流f滿足下列三個(gè)性質(zhì)：容量限制：對(duì)所有的u，v∈V，要求f(u,v)<=c(u,v)。反對(duì)稱性：對(duì)所有的u，v∈V，要求f(u,v)=-f(v,u)。流守恒性：對(duì)所有u∈V-{s,t}，要求∑f(u,v)=0 (v∈V)。容量限制說明了從一個(gè)頂點(diǎn)到另一個(gè)頂點(diǎn)的網(wǎng)絡(luò)流不能超過設(shè)定的容量，就好像是一個(gè)管道只能傳輸一定容量的水，而不可能超過管道體積的限制；反對(duì)稱性說明了從頂點(diǎn)u到頂點(diǎn)v的流是其反向流求負(fù)所得，就好像是當(dāng)參考方向固定后，站在不同的方向看，速度一正一負(fù)；而流守恒性說明了從非源點(diǎn)或非匯點(diǎn)的頂點(diǎn)出發(fā)的點(diǎn)網(wǎng)絡(luò)流之和為0。一般的最大流問題就是在不違背上述原則的基礎(chǔ)上求出從源點(diǎn)s到匯點(diǎn)t的最大的流量值，顯然這個(gè)流量值應(yīng)該定義為從源點(diǎn)出發(fā)的總流量或是最后聚集到t的總流量，即流f的值定義為|f|=∑f(s,v) (v∈V)。（3）殘留網(wǎng)絡(luò) 在給定的流網(wǎng)絡(luò)G=(V,E)中，設(shè)f為G中的一個(gè)流，并考察一對(duì)頂點(diǎn)u，v∈V，在不超過容量c(u,v)的條件下，從u到v之間可以壓入的額外網(wǎng)絡(luò)流量，就是(u,v)的殘留容量，就好像某一個(gè)管道的水還沒有超過管道的上限，那么就這條管道而言，就一定還可以注入更多的水。殘留容量的定義為：cf(u,v)=c(u,v)-f(u,v)。而由所有屬于G的邊的殘留容量所構(gòu)成的帶權(quán)有向圖就是G的殘留網(wǎng)絡(luò) （4）增廣路徑增廣路徑p為殘留網(wǎng)絡(luò)Gf中從s到t的一條簡(jiǎn)單路徑。根據(jù)殘留網(wǎng)絡(luò)的定義，在不違反容量限制的條件下，G中所對(duì)應(yīng)的增廣路徑上的每條邊(u,v)可以容納從u到v的某額外正網(wǎng)絡(luò)流。而能夠在這條路徑上的網(wǎng)絡(luò)流的最大值一定是p中邊的殘留容量的最小值。 1：EK算法 EK算法基于一個(gè)基本的方法:Ford-Fulkerson方法即增廣路方法簡(jiǎn)稱FF方法增廣路方法是很多網(wǎng)絡(luò)流算法的基礎(chǔ) 一般都在殘留網(wǎng)絡(luò)中實(shí)現(xiàn) 其思路是每次找出一條從源到匯的能夠增加流的路徑調(diào)整流值和殘留網(wǎng)絡(luò) 不斷調(diào)整直到?jīng)]有增廣路為止 FF方法的基礎(chǔ)是增廣路定理(Augmenting Path Theorem):網(wǎng)絡(luò)達(dá)到最大流當(dāng)且僅當(dāng)殘留網(wǎng)絡(luò)中沒有增廣路 EK算法的思路非常的簡(jiǎn)單，就是一直找增廣路徑（BFS），假如有，記錄增廣路的最小值k，ans+=k ，并更新殘量網(wǎng)絡(luò)（要加反向弧） EK算法的時(shí)間復(fù)雜度是O(m^2n) 最多增廣mn次,bfs復(fù)雜度O(m) 下面來段代碼模板：

#include <iostream> #include <queue> #include <cstring> using namespace std; #define arraysize 201 int maxData = 0x7fffffff; int capacity[arraysize][arraysize]; //記錄殘留網(wǎng)絡(luò)的容量 int flow[arraysize]; //標(biāo)記從源點(diǎn)到當(dāng)前節(jié)點(diǎn)實(shí)際還剩多少流量可用 int PRe[arraysize]; //標(biāo)記在這條路徑上當(dāng)前節(jié)點(diǎn)的前驅(qū),同時(shí)標(biāo)記該節(jié)點(diǎn)是否在隊(duì)列中 int n,m; queue<int> myqueue; int BFS(int src,int des) { int i,j; while(!myqueue.empty()) myqueue.pop(); //隊(duì)列清空 for(i=1;i<m+1;++i) pre[i]=-1; //初始化前驅(qū) pre[src]=0; //源點(diǎn)的前驅(qū)是0 flow[src]= maxData; //源點(diǎn)具有無限大的流量 myqueue.push(src); //進(jìn)隊(duì) while(!myqueue.empty()) //隊(duì)列不為空 { int index=myqueue.front(); //獲取隊(duì)首 myqueue.pop(); if(index == des) break; //找到了增廣路徑 [終點(diǎn)] for(i=1;i<=m;++i) { if(i!=src && capacity[index][i]>0 && pre[i]==-1) { //不是源點(diǎn) 有容量不在隊(duì)列 pre[i] = index; //記錄前驅(qū) flow[i] = min(capacity[index][i],flow[index]); //關(guān)鍵：迭代的找到增量 //printf("ind:%d i:%d flowi:%d cap:%d flowind:%d/n",index,i,flow[i],capacity[index][i],flow[index]); myqueue.push(i); } } } if(pre[des]==-1) return -1; //殘留圖中不再存在增廣路徑 else return flow[des]; //返回這條路的流量 } int maxFlow(int src,int des) { int increasement= 0; int sumflow = 0; while((increasement=BFS(src,des))!=-1) { int k = des; //利用前驅(qū)尋找路徑 while(k!=src) { int last = pre[k]; capacity[last][k] -= increasement; //改變正向邊的容量 capacity[k][last] += increasement; //改變反向邊的容量[關(guān)鍵] k = last; } sumflow += increasement; } return sumflow; } int main() { int i,j; int start,end,ci; while(scanf("%d%d",&n,&m)!=EOF) { memset(capacity,0,sizeof(capacity)); memset(flow,0,sizeof(flow)); for(i=0;i<n;++i) { scanf("%d%d%d",&start,&end,&ci); if(start==end) //考慮起點(diǎn)終點(diǎn)相同的情況 continue; capacity[start][end] +=ci; //此處注意可能出現(xiàn)多條同一起點(diǎn)終點(diǎn)的情況 } cout<<maxFlow(1,m)<<endl; } return 0; }

2：Dinic算法

1、初始化流量，計(jì)算出剩余圖 2、一次bfs對(duì)頂點(diǎn)標(biāo)號(hào)，計(jì)算出層次圖，如果匯點(diǎn)不在層次圖內(nèi)，那么算法結(jié)束 3、一次dfs過程找增廣 4、轉(zhuǎn)步驟 2 頂點(diǎn)u的層次：level(u)=在剩余圖中從源點(diǎn)到u所經(jīng)過的最少邊數(shù) 層次圖：對(duì)于剩余圖中的任意一條邊(a,b), 當(dāng)且僅當(dāng)level(a)+1=level(b)時(shí),(a,b)是層次圖中的邊這里寫圖片描述復(fù)雜度O(n2*m) 程序簡(jiǎn)短對(duì)于較大規(guī)模的數(shù)據(jù)實(shí)際速度很快代碼：

#include<cstdio> #include<cstring> #include<cmath> #include<iostream>#include<algorithm>#include<queue> #define CL(a,num) memset(a,num,sizeof(a)); #define eps 1e-12 #define inf 0x7fffffff const double pi = acos(-1.0); typedef __int64 ll; const int maxn = 300 ; using namespace std; int n , m; int flow[maxn][maxn],dis[maxn] ;//dis[i],表示到原點(diǎn) s 的層數(shù) int bfs(){ CL(dis,-1); dis[1] = 0 ; queue<int>que; que.push(1); while(!que.empty()) { int k = que.front();que.pop() ; for(int i=1;i<=n;i++) { if(flow[k][i]>0&&dis[i]==-1)//可以到達(dá)&&還沒有訪問 { dis[i]=dis[k]+1;//建立dfs軌跡 que.push(i) ; } } } if(dis[n]>0) return 1;//有增逛路 return 0 ; } int dfs(int x,int mx){ int i,a; if(x==n) return mx; for(i=1;i<= n;i++) { if(dis[i]==dis[x]+1&&flow[x][i]>0) { if(a=dfs(i,min(mx,flow[x][i])))//流量與容量的最小值 { //printf("x:%d i:%d a:%d/n",x,i,a); flow[x][i]-=a; flow[i][x]+=a; return a ; } } } return 0; } int main() { int i ,s,e,c; while(scanf("%d%d",&m,&n)!=EOF) { CL(flow,0); for(i=0;i<m;i++) { scanf("%d%d%d",&s,&e,&c); flow[s][e] += c; } int ans=0; int res; while(bfs()) { while(res=dfs(1,inf)) ans+= res; } printf("%d/n",ans); } }

3：ISAP 之前的兩種算法是SAP算法，這里介紹一下ISAP算法算法基于這樣的一個(gè)事實(shí)：每次增廣之后，任意結(jié)點(diǎn)到匯點(diǎn)（在殘余網(wǎng)絡(luò)中）的最短距離都不會(huì)減小。這樣，我們可以利用d[i[表示結(jié)點(diǎn)i到匯點(diǎn)的距離的下界。然后再增廣過程當(dāng)中不斷地修改這個(gè)下界。增廣的時(shí)候和Dinic算法類似，只允許沿著d[i]==d[j]+1的弧(i,j)走。不難證明，d[i]滿足兩個(gè)條件：(1)d[t]=0;(2)對(duì)任意的弧(i,j) d[i]≤d[j]+1。因?yàn)樽顗牡那闆r就是s到t是一條鏈，此時(shí)等號(hào)成立。因此，當(dāng)d[s]≥n時(shí)，殘余網(wǎng)絡(luò)中不存在s-t路。那么與Dinic算法類似，事先逆向bfs，找增廣的過程就是沿著“允許弧”（即滿足f< c且d[i]==d[j]+1的弧）往前走。（稱為“前進(jìn)”）。如果向前走不動(dòng)了，那么就要考慮原路返回（稱為“撤退”）。此時(shí)把d[i]修改為min{d[j]}+1即可。因?yàn)橐獫M足d函數(shù)的條件(2)。修改后，原來的i值的個(gè)數(shù)就減少一個(gè)，而新i值的個(gè)數(shù)多一個(gè)。在程序中，用num數(shù)組來保存所有距離的個(gè)數(shù)，當(dāng)把距離值從x修改為y時(shí)，num[x]–-,num[y]++即可，然后檢查num[x]是否為0，如果是0，那么s-t不連通，算法終止。原因顯而易見：比如s-t的距離是3，如果距離為2的情況都已經(jīng)沒了，更別提走到距離為1的點(diǎn)了。這就是所謂的“gap優(yōu)化”。通過之前的分析，在數(shù)據(jù)結(jié)構(gòu)方面，該算法只比Dinic算法的數(shù)據(jù)結(jié)構(gòu)多了兩個(gè)數(shù)組：用于記錄父邊以便于撤退的數(shù)組p，以及標(biāo)記距離個(gè)數(shù)的數(shù)組num。增廣的時(shí)候分為兩步，第一步逆推求出可改進(jìn)量a（即殘余量的最小值）；第二步再逆推一遍，進(jìn)行增廣。主過程中，x走到匯點(diǎn)時(shí)增廣。在下面代碼中，由于我們是連續(xù)存的正向邊和反向邊，如0和1,2和3，等等。而他們分別與1異或后可以得到對(duì)方（二進(jìn)制最后一位變反，其他位不變），所以我們?cè)诟路聪蜻厱r(shí)用到了這一點(diǎn)。代碼：

int source; // 源點(diǎn)int sink; // 匯點(diǎn)int p[max_nodes]; // 可增廣路上的上一條弧的編號(hào)int num[max_nodes]; // 和 t 的最短距離等于 i 的節(jié)點(diǎn)數(shù)量int cur[max_nodes]; // 當(dāng)前弧下標(biāo)int d[max_nodes]; // 殘量網(wǎng)絡(luò)中節(jié)點(diǎn) i 到匯點(diǎn) t 的最短距離bool visited[max_nodes];bool bfs(){ memset(visited, 0, sizeof(visited)); queue<int> Q; Q.push(sink);visited[sink] = 1;d[sink] = 0; while (!Q.empty()) { int u = Q.front(); Q.pop(); for (iterator_t ix = G[u].begin(); ix != G[u].end(); ++ix) { Edge &e = edges[(*ix)^1]; if (!visited[e.from] && e.capacity > e.flow) visited[e.from] = true,d[e.from] = d[u] + 1,Q.push(e.from); } } return visited[source];}int augment(){ int u = sink, df = __inf;// 從匯點(diǎn)到源點(diǎn)通過 p 追蹤增廣路徑, df 為一路上最小的殘量 while (u != source) { Edge &e = edges[p[u]]; df = min(df, e.capacity - e.flow); u = edges[p[u]].from; } u = sink;// 從匯點(diǎn)到源點(diǎn)更新流量 while (u != source) { edges[p[u]].flow += df; edges[p[u]^1].flow -= df; u = edges[p[u]].from; } return df;}int max_flow(){ int flow = 0; bfs(); memset(num, 0, sizeof(num)); for (int i = 0; i < num_nodes; i++) num[d[i]]++; int u = source; memset(cur, 0, sizeof(cur)); while (d[source] < num_nodes) { if (u == sink) { flow += augment(); u = source; } bool advanced = false; for (int i = cur[u]; i < G[u].size(); i++) { Edge& e = edges[G[u][i]]; if (e.capacity > e.flow && d[u] == d[e.to] + 1) { advanced = true; p[e.to] = G[u][i]; cur[u] = i; u = e.to; break; } } if (!advanced) { // retreat int m = num_nodes - 1; for (iterator_t ix = G[u].begin(); ix != G[u].end(); ++ix) if (edges[*ix].capacity > edges[*ix].flow) m = min(m, d[edges[*ix].to]); if (--num[d[u]] == 0) break; // gap 優(yōu)化 num[d[u] = m+1]++; cur[u] = 0; if (u != source) u = edges[p[u]].from; } } return flow; }

二：最小割 1：定義割：流網(wǎng)絡(luò)圖G=(V,E)的一個(gè)劃分，記作[S,T]，將點(diǎn)集[V]劃分為S和T兩部分，且使得s屬于S，t屬于T，S+T=V。 最小割：一個(gè)網(wǎng)絡(luò)的最小割也就是該網(wǎng)絡(luò)中容量最小的割。 最大流最小割定理：流網(wǎng)絡(luò)圖G=(V,E)的最大流大小等于其最小割容量。帶權(quán)圖的割就是割集中邊或者有向邊的權(quán)和通俗的理解一下: 割集好比是一個(gè)恐怖分子把你家和自來水廠之間的水管網(wǎng)絡(luò)砍斷了一些然后自來水廠無論怎么放水水都只能從水管斷口嘩嘩流走了你家就停水了割的大小應(yīng)該是恐怖分子應(yīng)該關(guān)心的事畢竟細(xì)管子好割一些而最小割花的力氣最小下面介紹網(wǎng)絡(luò)流理論中一個(gè)最為重要的定理 最大流最小割定理:網(wǎng)絡(luò)的最大流等于最小割 具體的證明分三部分 1.任意一個(gè)流都小于等于任意一個(gè)割由于容量限制每一根的被砍的水管子流出的水流量都小于管子的容量每一根被砍的水管的水本來都要到你家的現(xiàn)在流到外面加起來得到的流量還是等于原來的流管子的容量加起來就是割所以流小于等于割由于上面的流和割都是任意構(gòu)造的所以任意一個(gè)流小于任意一個(gè)割

2.構(gòu)造出一個(gè)流等于一個(gè)割當(dāng)達(dá)到最大流時(shí) 根據(jù)增廣路定理殘留網(wǎng)絡(luò)中s到t已經(jīng)沒有通路了否則還能繼續(xù)增廣我們把s能到的的點(diǎn)集設(shè)為S 不能到的點(diǎn)集為T 構(gòu)造出一個(gè)割集C[S,T] S到T的邊必然滿流否則就能繼續(xù)增廣這些滿流邊的流量和就是當(dāng)前的流即最大流把這些滿流邊作為割就構(gòu)造出了一個(gè)和最大流相等的割

3.最大流等于最小割設(shè)相等的流和割分別為Fm和Cm 則因?yàn)槿我庖粋€(gè)流小于等于任意一個(gè)割任意F≤Fm=Cm≤任意C 定理說明完成

所以，我們就可以把最小割轉(zhuǎn)化為最大流，使用上面介紹的三種算法。

三:最大權(quán)閉合圖、最大密度子圖、混合圖歐拉回路

最大權(quán)閉合圖：（此部分轉(zhuǎn)載）這里閉合圖的概念就很好引出了。在一個(gè)圖中，我們選取一些點(diǎn)構(gòu)成集合，記為V，且集合中的出邊(即集合中的點(diǎn)的向外連出的弧)，所指向的終點(diǎn)(弧頭)也在V中，則我們稱V為閉合圖。最大權(quán)閉合圖即在所有閉合圖中，集合中點(diǎn)的權(quán)值之和最大的V，我們稱V為最大權(quán)閉合圖。這里寫圖片描述上圖中閉合圖有

{5}、{2,5}、{4,5} {2,4,5}、{3,4,5} {1,2,3,4,5}、{1,2,4,5}

最大權(quán)閉合圖為{3,4,5}。

針對(duì)本題而言，我們將實(shí)驗(yàn)與儀器間連一條有向邊，實(shí)驗(yàn)為起點(diǎn)(弧尾)，儀器為終點(diǎn)(弧頭)。則如果我們選擇一個(gè)閉合圖，那么這個(gè)閉合圖中包含的實(shí)驗(yàn)所需要的儀器也最這個(gè)閉合圖里。而最大權(quán)閉合圖即為題目的解。

了解了最大權(quán)閉合圖的概念，接下來我們就需要知道如何求最大權(quán)閉合圖。

首先我們將其轉(zhuǎn)化為一個(gè)網(wǎng)絡(luò)(現(xiàn)在不要問為什么,接下來會(huì)證明用網(wǎng)絡(luò)可以求解)。構(gòu)造一個(gè)源點(diǎn)S，匯點(diǎn)T。我們將S與所有權(quán)值為正的點(diǎn)連一條容量為其權(quán)值的邊，將所有權(quán)值為負(fù)的點(diǎn)與T連一條容量為其權(quán)值的絕對(duì)值的邊，原來的邊將其容量定為正無窮。

這里寫圖片描述上圖即被轉(zhuǎn)化為如左圖網(wǎng)絡(luò)。

首先引入結(jié)論，最小割所產(chǎn)生的兩個(gè)集合中，其源點(diǎn)S所在集合(除去S)為最大權(quán)閉合圖，接下來我們來說明一些結(jié)論。

證明:最小割為簡(jiǎn)單割。 1：引入一下簡(jiǎn)單割的概念：割集的每條邊都與S或T關(guān)聯(lián)。(請(qǐng)下面閱讀時(shí)一定分清最小割與簡(jiǎn)單割，容易混淆):那么為什么最小割是簡(jiǎn)單割呢？因?yàn)槌齋和T之外的點(diǎn)間的邊的容量是正無窮，最小割的容量不可能為正無窮。所以，得證。

2：證明網(wǎng)絡(luò)中的簡(jiǎn)單割與原圖中閉合圖存在一一對(duì)應(yīng)的關(guān)系。(即所有閉合圖都是簡(jiǎn)單割，簡(jiǎn)單割也必定是一個(gè)閉合圖)。證明閉合圖是簡(jiǎn)單割：如果閉合圖不是簡(jiǎn)單割(反證法)。那么說明有一條邊是容量為正無窮的邊，則說明閉合圖中有一條出邊的終點(diǎn)不在閉合圖中，矛盾。證明簡(jiǎn)單割是閉合圖：因?yàn)楹?jiǎn)單割不含正無窮的邊，所以不含有連向另一個(gè)集合(除T)的點(diǎn)，所以其出邊的終點(diǎn)都在簡(jiǎn)單割中，滿足閉合圖定義。得正。 3：證明最小割所產(chǎn)生的兩個(gè)集合中，其源點(diǎn)S所在集合(除去S)為最大權(quán)閉合圖。首先我們記一個(gè)簡(jiǎn)單割的容量為C,且S所在集合為N，T所在集合為M。則C=M中所有權(quán)值為正的點(diǎn)的權(quán)值(即S與M中點(diǎn)相連的邊的容量)+N中所有權(quán)值為負(fù)的點(diǎn)權(quán)值的絕對(duì)值(即N中點(diǎn)與T中點(diǎn)相連邊的容量)。記(C=x1+y1);(很好理解，不理解畫一個(gè)圖或想象一下就明白了)。我們記N這個(gè)閉合圖的權(quán)值和為W。則W=N中權(quán)值為正的點(diǎn)的權(quán)值-N中權(quán)值為負(fù)的點(diǎn)的權(quán)值的絕對(duì)值。記(W=x2-y2); 則W+C=x1+y1+x2-y2。因?yàn)槊黠@y1=y2，所以W+C=x1+x2; x1為M中所有權(quán)值為正的點(diǎn)的權(quán)值，x2為N中權(quán)值為正的點(diǎn)的權(quán)值。所以x1+x2=所有權(quán)值為正的點(diǎn)的權(quán)值之和(記為TOT). 所以我們得到W+C=TOT.整理一下W=TOT-C. 到這里我們就得到了閉合圖的權(quán)值與簡(jiǎn)單割的容量的關(guān)系。因?yàn)門OT為定值，所以我們欲使W最大，即C最小，即此時(shí)這個(gè)簡(jiǎn)單割為最小割，此時(shí)閉合圖為其源點(diǎn)S所在集合(除去S)。得正。至此，我們就將最大權(quán)閉合圖問題轉(zhuǎn)化為了求最小割的問題。求最小割用最小割容量=最大流，即可將問題轉(zhuǎn)化為求最大流的問題。【持續(xù)更新中…】

上一篇：建造者模式

下一篇：外觀模式