《冬令營論》PPT課件

1、兩極相通,淺析最大最小定理在信息學競賽中的應用,引入,我們在信息學競賽中經常會遇到一些涉及一個最大化問題和一個最小化問題的定理 怎樣利用這些定理幫助我們解題呢,Knig定理 最大流最小割定理,Knig定理,主要內容 在任何一個二部圖G中，最大匹配數r(G)等于最小覆蓋數c(G,Knig定理,證明 最大匹配數不超過最小覆蓋數 任取一個最小覆蓋Q，一定可以構造出一個與之大小相等的匹配M,r(G) c(G,r(G) = c(G,c(G) |Q| = |M| r (G) c(G) r(G,Knig定理,應用 二部圖最小覆蓋和最大匹配的互相轉化 例一 Muddy Fields,最大流最小割定理,近年來，

2、網絡流尤其是最大流問題越來越多的出現(xiàn)在各類信息學競賽當中 最大流最小割定理是整個最大流問題的基礎與核心，其主要內容是： 最大流的流量不超過最小割的容量 存在一個流x和一個割c，且x的流量等于c的容量,例二 Moving the Hay,一個牧場由R*C個格子組成 牧場內有N條干草運輸通道，每條連接兩個水平或垂直相鄰的方格，最大運輸量為Li (1,1)內有很多干草，F(xiàn)armer John希望將最多的干草運送到(R,C)內 求最大運輸量,例二 Moving the Hay,一個R=C=3的例子，最大運輸量為7 數據規(guī)模：R,C 200,分析,直接求最大流 以每個方格為點，每條通道為邊，邊的容量就是

3、它的最大運輸量 從(1,1)到(R,C)的最大運輸量就是將這兩個方格對應的點分別作為流網絡中的源和匯求出的最大流量 效率？ 點數最大40000，邊數最大80000,Time Limit Exceeded,分析,效率低下的原因 沒有利用題目的特點，直接套用經典算法 特點 題目中給出的是一個平面圖 圖中的一個點為源點s，另外一個點為匯點t，且s和t都在圖中的無界面的邊界上,分析,4,5,2,3,1,6,f1,f2,f3,f4,分析,效率低下的原因 沒有利用題目的特點，直接套用經典算法 特點 題目中給出的是一個平面圖 圖中的一個點為源點s，另外一個點為匯點t，且s和t都在圖中的無界面的邊界上 我們稱

4、這樣的平面圖為s-t平面圖,平面圖的性質,平面圖性質 （歐拉公式）如果一個連通的平面圖有n個點，m條邊和f個面，那么f=m-n+2 每個平面圖G都有一個與其對偶的平面圖G* G*中的每個點對應G中的一個面,對偶圖舉例,4,5,2,3,1,6,1,2,3,4,平面圖的性質,平面圖性質 （歐拉公式）如果一個連通的平面圖有n個點，m條邊和f個面，那么f=m-n+2 每個平面圖G都有一個與其對偶的平面圖G* G*中的每個點對應G中的一個面 對于G中的每條邊e e屬于兩個面f1、f2，加入邊(f1*， f2*,對偶圖舉例,4,5,2,3,1,6,1,2,3,4,平面圖的性質,平面圖性質 （歐拉公式）如果

5、一個連通的平面圖有n個點，m條邊和f個面，那么f=m-n+2 每個平面圖G都有一個與其對偶的平面圖G* G*中的每個點對應G中的一個面 對于G中的每條邊e e屬于兩個面f1、f2，加入邊(f1*， f2*) e只屬于一個面f，加入回邊(f*， f*,對偶圖舉例,4,5,2,3,1,6,1,2,3,4,平面圖與其對偶圖的關系,平面圖G與其對偶圖G*之間存在怎樣的關系呢？ G的面數等于G*的點數，G*的點數等于G的面數，G與G*邊數相同 G*中的環(huán)對應G中的割一一對應,4,5,2,3,1,6,1,2,3,4,s-t平面圖上最大流的快速求法,如何利用這些性質？ 直接求解 仍然困難 利用最大流最小割定

6、理轉化模型 根據平面圖與其對偶圖的關系，想辦法求出最小割,利用最短路求最小割,對于一個s-t平面圖，我們對其進行如下改造： 連接s和t，得到一個附加面,對于一個s-t平面圖，我們對其進行如下改造： 求該圖的對偶圖G*，令附加面對應的點為s*，無界面對應的點為t,對于一個s-t平面圖，我們對其進行如下改造： 刪去s*和t*之間的邊,1,2,3,4,5,6,7,8,1,3,2,4,5,7,6,8,s,t,s,t,利用最短路求最小割,一條從s*到t*的路徑，就對應了一個s-t割！ 更進一步，如果我們令每條邊的長度等于它的容量，那么最小割的容量就等于最短路的長度！ 分析一下時間復雜度 新圖中的點數和邊

7、數都是O(n)的 使用二叉堆優(yōu)化的Dijkstra算法求最短路，時間復雜度為O(nlog2n,1,2,3,4,5,6,7,8,1,3,2,4,5,7,6,8,s,t,s,t,利用最短路求最大流,我們可以利用最短路算法得到的距離標號構造一個最大流 定理2.1 可以在O(nlog2n)的時間內求出s-t平面圖上的最大流,小結,回顧 得到簡單的最大流模型 利用最大流最小割定理進行模型轉化 根據平面圖的性質解決最小割問題 構造得到最大流,最大最小定理,對比以上兩個定理 定義3.1 最大最小定理是一類描述同一個對象上的一個最大化問題的解和一個最小化問題的解之間的關系的定理,最大最小定理,共同點 考察的兩

8、個最優(yōu)化問題互為對偶問題 證明的過程 最大化問題M的任何一個解m的值都不超過最小化問題N的任何一個解n的值 可以找到M的一個解p和N的一個解q，且它們的值相等 p和q分別為各自問題的一個最優(yōu)解 簡潔的最優(yōu)性證明,總結,Knig定理,最大流最小割定理,最大最小定理,最大匹配,最小覆蓋,最大流,最小割,模型轉化,最大,最小,完全矛盾,互相轉化,注意總結、積累 勇于探索,參考文獻,Introduction to Graph Theory, Second Edition by Douglas B. West Network Flows: Theory, Algorithms and Applicati

9、ons by Ravindra K. Ahuja, Thomas L. Magnanti, and James B. Orlin Introductory Combinatorics, Third Edition by Richard A. Brualdi 運籌學教程（第三版） 胡運權 郭耀煌,謝謝大家，歡迎提問,更多的例子,二部圖中 最大獨立集的大小等于最小邊覆蓋數 頂點的最大度數等于最小邊染色數 3正則圖中 點聯(lián)通度等于邊聯(lián)通度,如何構造最大流,我們用d(j*)表示新圖中s*到j*的最短路的長度 對于每條邊(i*,j*)，d(j*)d(i*)+ci*j* G中的每條邊(i,j)，設G*與其

10、對應的邊為(i*,j*)，定義流量xij=d(j*)-d(i*) 反對稱性：xij=-xji 容量限制：xij=d(j*)-d(i*)ci*j,如何構造最大流,對于G中的任何一個異于s和t的節(jié)點k，定義割Q=k，V-k包含所有與k相關的邊。那么Q中的所有邊對應到G*就形成了一個環(huán)，稱為W*。 顯然 k的流入量等于流出量，即x滿足流量平衡,如何構造最大流,設P*是G*中從s*到t*的一條最短路 對于任意的(i*,j*) P*，都有d(j*)-d(i*)=ci*j* P*中的邊構成了原圖中的一個s-t割Q。根據上式和ci*j*=uij可得 對于任意的(i,j)Q，都有xij=uij。 x的流量等于

11、Q的容量 x是最大流，Q是最小割,復雜度問題,只考慮題目中給出的邊 需要通過寬搜得到所有的面，且需要處理面與面之間的關系 思維復雜度與編程復雜度均比較高 可以認為原來不存在的邊容量為0 不影響答案 面與面之間的關系清晰明了 大大降低思維和編程復雜度,最大最小定理和線性規(guī)劃,線性規(guī)劃 定義:在滿足一些線性等式或者不等式的條件下，最優(yōu)化一個線性函數 標準形式： 整數線性規(guī)劃,最大最小定理和線性規(guī)劃,對偶問題,最大最小定理和線性規(guī)劃,基本性質 弱對偶性 如果x是原問題的可行解，y是其對偶問題的可行解，則恒有c*x b*y 最優(yōu)性 如果x是原問題的可行解，y是其對偶問題的可行解，且有c*x = b*y，則x和y是各自問題的最優(yōu)解 強最優(yōu)性（對偶定理） 如果原問題及其對偶問題均有可行解，則兩者均有最優(yōu)解，且最優(yōu)解的目標函數值相同,最大最小定理和線性規(guī)劃,二部圖最大匹配 每個變量x對應一條邊 對于每個頂點v，S(v)表示所有與v關聯(lián)的邊的集合,最大最小定