圖論總結(超強大)-資料下載頁

　　

【正文】 n^3)。想法：假設d=d(t)，我們將試著一次性的找到很多到t的長度為d的路徑。為了做到這個，我們看前面得到的層次圖（我們不考慮所有的后向邊以及兩個端點在同一層的邊）。我們現在嘗試著在這個圖中執行盡量多的流量，然后我們才重新計算剩余圖。術語：一個充滿了這個剩余圖的流稱之為塊流。因此我們的目標就是在這個剩余圖中在O(n^2)的時間內找到一個塊流。我們定義c(v)=頂點v的容量：也就c_in[v],c_out[v]的最小值，這里c_in[v]是所有v的入邊的容量的和，而c_out[v]類似。算法：找到具有最小容量c的頂點v。如果他的容量是0，oh yeah我們就可以把他和與他相關聯的邊都刪除掉，并且更新他的鄰居的容量值。如果c不為0，那么我們將從s運送c個單位流到v，然后從v運送到t。你可能覺得這不又回到原來的問題了么？但是，這里有點值得注意：因為v具有最小的容量，我們可以使用任何的貪心策略來從其他頂點流入流出c的流量而不會被堵住。這一點意味著，我們可以在O(m)的時間內充滿v。（* daizinnd，想了好久才明白具體怎么做的首先，為了從s運送c到v，我們從v開始向上考慮，把任意一條從v向上的邊給充滿，如果不能夠充滿，說明還沒有安置的流量就這些了，全部扔在這條邊上就是了，為什么一定能夠找到這樣一條邊呢，：）然后假設我們剛才填充的這條邊是uv，那么我們就有一些流量需要在u繼續往上進行處理，使用剛才在v點同樣的辦法，直到一直處理到了s，一路上肯定是不會出現什么障礙的。然后我們將c從v運送到t，我們在構造這個層次圖的時候很容易就可以保證所有從s出發的路徑都會在t終結，這樣就好辦了，使用上面同樣的辦法，只是處理的方向是從v到t了。這樣，我們剛才處理的過程就容易得到下面的下面所謂的性質了。*）上面的算法給了我們一個可以在O(mn)的時間內充滿這個層次圖的算法，下面進一步分析。為了得到我們需要的界，我們需要這樣一個性質：當我們在上面的對每個新的頂點v執行算法的步驟中，保證對每條邊我們只檢查一次，對其做完所有需要的操作之后才會去做下一條邊。這點意味著，我們可以把運行時間分成兩個部分來考慮：a）花在被充滿的邊上的時間 b）花在沒有被充滿的邊上的時間。對于a），因為我們每次充滿一條邊就會把它從圖中刪除，所以a）的總時間是O(m)。因此我們的時間主要由b）來決定，而b）對應的邊在對每個新的頂點v的執行過程中至多出現O(n)次，因此總的時間是O(n^2)。而我們可以在O(m)的時間內重新計算新的層次圖，所以我們就可以在O(n m + n n^2)時間完成整個算法，也就是O(n^3)。. 擴展模型 Extended models. 有上下界的流問題問題模型：給定一個加權的有向圖，滿足：(1)容量限制條件：(2)流量平衡條件：(2)中的，即除了源匯外，所有點都滿足流量平衡條件，則稱G為有源匯網絡；否則，即不存在源匯，所有點都滿足流量平衡條件，則稱G為無源匯網絡。將這類問題由易到難一一解決：問題[1] 求無源匯的網絡有上下界的可行流12st2,63,73,4+∞由于下界是一條弧上的流必需要滿足的確定值。下面引入必要弧的概念：必要弧是一定流要滿的弧。必要弧的構造，將容量下界的限制分離開了，從而構造了一個沒有下界的網絡G’：1． 將原弧(u,v)分離出一條必要弧：。（紅色表示）2． 原弧：。+∞12st441233 由于必要弧的有一定要滿的限制，將必要弧“拉”出來集中考慮：+∞12st441233 添加附加源x, 附加匯y。想像一條不限上界的(y, x)，用必要弧將它們“串”起來，即對于有向必要弧(u, v)，添加(u, y)，(x, v)，容量為必要弧容量。這樣就建立了一個等價的網絡。+∞12st441233yx233一個無源匯網絡的可行流的方案一定是必要弧是滿的。若去掉(y, x)后，附加源x到附加匯y的最大流，能使得x的出弧或者y的入弧都滿，充要于原圖有可行流。+∞12st441233yx233算法：1. 按上述方法構造新網絡(分離必要弧，附加源匯)2. 求附加源x到附加匯y的最大流3. 若x的出弧或y的入弧都滿，則有解，將必要弧合并回原圖；否則，無解。問題[2] 求有源匯的網絡有上下界的可行流12st2,63,73,4加入邊(t, s)，下界為0(保證不會連上附加源匯x, y)，不限上界，將問題[2]轉化為問題[1]來求解。12stT2,63,73,4+∞問題[3]求有源匯的網絡有上下界的最大流算法：1. 先轉化為問題[2]來求解一個可行流。若可行無解，則退出。由于必要弧是分離出來的，所以就可以把必要弧（附加源匯及其臨邊）及其上的流，暫時刪去。再將(T,S)刪去，恢復源匯。2. 再次，從S到T找增廣軌，求最大流。3. 最后將暫時刪去的下界信息恢復，合并到當前圖中。輸出解。這樣既不破壞下界(分離出來)也不超出上界(第2步滿足容量限制)，問題解決。問題[4]求有源匯的網絡有上下界的最小流算法：1. 同問題[3]。2. 從T到S找增廣軌，不斷反著改進。3. 同問題[3]。問題[3]與問題[4]的另一種簡易求法：注意問題[2]中，構造出的(t, s)，上下界幾乎沒什么限制。下面看看它的性質：定理：如果從s到t有一個流量為a的可行流f，那么從t到s連一條弧(t, s)，其流量下界b(t, s) = a，則這個圖一定有一個無源匯的可行流：除了弧(t, s)的容量為a外，其余邊的容量與f相同。證明：如果從s到t的最大流量為amax，那么從t到s連一條下界b(t, s) = a’ amax的弧(t, s)，則從在這個改造后的圖中一定沒有無源匯的可行流：否則將這個可行流中的弧(t, s)除去，就得到了原圖中s到t的流量為a’的流，大于最大流量amax，產生矛盾。 可以二分枚舉這個參數a，即下界b(t, s)，每次用問題[1]判斷是否有可行流。這樣就可以求出最大流。 同理，問題[4]要求最小流，只要二分枚舉上界c(t, s)即可。 因為樸素的預流推進算法O(N3)，總復雜度為O(N3 log2流量) 。思路：無源匯 (附加源匯+最大解決)有源匯 (附加(T,S)無源匯)習題：SGU194 Reactor CoolingSGU176 Flow Construction參考文獻：[1]安徽 周源，《一種簡易的方法求解流量有上下界的網絡中網絡流問題》，IOI2004國家集訓隊作業[2]江濤，《最大流在信息學競賽中應用的一個模型》，NOI2006冬令營. 最小費用流 Minimum cost flow對于有向帶權圖G=(V,E,C,W)，求一個圖上的流f，使得每條邊的流量與費用的乘積加起來的總和最小，且總流量等于d。下面是最小費用流問題的數學模型的表述： 最小費用最大流問題：總流量d為網絡的最大流的最小費用流問題。. 找最小費用路 Finding minimum cost path每次在殘量網絡中找最小費用路并沿著它增廣，直到不存這樣增廣路。算法：1. 用BellmanFord在殘量網絡中求st的最小費用路，若不存在，結束；否則轉2。2. 沿著找到的最小費用路改進殘量網絡。轉2。設v是最大流量，則算法最多迭代v次，故復雜度為。習題：FJOI 2002 蚯蚓問題. 找負權圈 Finding negative circle在最大流的殘量網絡中不斷的找負費用圈并沿著它增廣，直到不存這樣的負圈。易知，每次沿負費用圈增廣，總費用總是不斷的減小。算法：1. 用最大流算法求出網絡的任一個最大流的殘量網絡。2. 用BellmanFord算法找殘量網絡的負費用圈，若不存在，結束；否則轉3。3. 沿著找到的負費用圈改進殘量網絡。轉2。設c為容量最大值，w為費用最大值。因為每次消圈，費用至少少1，而初始費用不超過mcw，所以復雜度上限：，是偽多項式算法。但實際上，會比這個快多了。還有一個按照特定次序消圈的算法。所以最小費用流問題是P類的。習題：Ural 1237 Evacuation Plan. 網絡單純形 Network simplex algorithm我不會阿！！！. 匹配 Matching所有的匹配算法都基于增廣軌定理：一個匹配是最大匹配當且僅當沒有增廣軌。這個定理適用于任意圖。KuhnMunkresEdmondsGabow. 二分圖 Bipartite Graph由于二分圖（又稱二部圖）的特殊性，使得它可以轉化成流問題來解決。習題：Ural 1203 Conference (最小點覆蓋). 無權圖匈牙利算法 Unweighted Hopcroft and Karp algorithm匈牙利算法，匈牙利數學家Edmonds于1965年提出。. 帶權圖KM算法 Weighted –KuhnMunkres(KM) algorithm構造可行頂標：結點函數l，對任意弧滿足：。引入相等子圖：G的生成子圖，包含所有點，但只包含滿足的所有弧。下證相等子圖的一個性質定理：如果相等子圖有完美匹配，則該匹配是原圖的最大權匹配。證明：設M*是相等子圖的完美匹配，M是原圖的任意完美匹配。(1)是根據相等子圖定義。(2)是根據可行頂標定義。所以關鍵是尋找好的可行頂標，使相等子圖有完美匹配。算法思想：隨便構造一個可行頂標（例如Y結點頂標為0，X結點的頂標為它出發所有弧的最大權值，然后求相等子圖的最大匹配）若存在完美匹配，算法終止否則修改頂標使得相等子圖的邊變多，有更大機會存在完美匹配Kuhn和Munkras . 一般圖General Graph. 無權圖帶花樹算法 Unweighted Blossom (Edmonds)朱(永津)劉(振宏)算法（1965）Edmons算法（1968）Dictionary of Algorithms and Data Structures NISTWikipediaIntroduction to Algorithm單純的課本內容，并不能滿足學生的需要，通過補充，達到內容的完善 教育之通病是教用腦的人不用手，不教用手的人用腦，所以一無所能。教育革命的對策是手腦聯盟，結果是手與腦的力量都可以大到不可思議。.