兩極相通淺析最大最小定理在信息學競賽中的應用

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

2、學競賽當中最大流最小割定理是整個最大流問題的基礎與，其主要內容是：1.2.最大流的流量不超過最小割的容量存在一個流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(1,2)(1,3)(1,1)5,53,25,5(2,3)1,1(2,2)2,2(2,1)4,16,6(3,3)(3,1)(3,2)7,6數(shù)據(jù)規(guī)模：R,C 200分析直

3、接求最大流以每個方格為點，每條通道為邊，邊的容量就是它的最大量從(1,1)到(R,C)的最大量就是將這兩個方格對應的點分別作為流網絡中的源和匯求出的最大流量效率？點數(shù)最大40000，邊數(shù)最大80000！分析效率低下的原因沒有利用題目的特點，直接套用經典算法特點題目中給出的是一個平面圖圖中的一個點為源點s，另外一個點為匯點t，且s和t都在圖中的面的邊界上分析24f2f11f335f46分析效率低下的原因沒有利用題目的特點，直接套用經典算法特點題目中給出的是一個平面圖圖中的一個點為源點s，另外一個點為匯點t，且s和t都在圖中的面的邊界上稱這樣的平面圖為s-t平面圖平面圖的性質平面圖性質1.通的平面

4、圖有n個點，（公式）如果m條邊和f個面，那么f=m-n+22.每個平面圖G都有一個與其對偶的平面圖G*G*中的每個點對應G中的一個面對偶圖舉例242*11*3*354*6平面圖的性質平面圖性質1.通的平面圖有n個點，（公式）如果m條邊和f個面，那么f=m-n+22.每個平面圖G都有一個與其對偶的平面圖G*G*中的每個點對應G中的一個面對于G中的每條邊ee屬于兩個面f1、f2，加入邊(f1*， f2*)對偶圖舉例242*11*3*354*6平面圖的性質平面圖性質1.通的平面圖有n個點，（公式）如果m條邊和f個面，那么f=m-n+22.每個平面圖G都有一個與其對偶的平面圖G*G*中的每個點對應G中

5、的一個面對于G中的每條邊ee屬于兩個面f1、f2，加入邊(f1*， f2*)e只屬于一個面f，加入回邊(f*， f*)對偶圖舉例242*11*3*354*6平面圖與其對偶圖的關系平面圖G與其對偶圖G*之間存在怎樣的關系呢？G的面數(shù)等于G*的點數(shù)，G*的點數(shù)等于G的面數(shù)，G與G*邊數(shù)相同G*中的環(huán)對應G中的割一一對應242*11*3*354*6s-t平面圖上最大流的快速求法如何利用這些性質？直接求解仍然利用最大流最小割定理轉化模型根據(jù)平面圖與其對偶圖的關系，想辦法求出最小割利用最短路求最小割對于一個s-t平面圖，對其進行如下改造：求刪連去接圖s*和的和t，對t*得偶之到圖間一G的*個邊，附令加附

6、面加面對應的點為s*，對應的點為t*t*8*面255*7*6*s1t3683*2*4*47s*1*利用最短路求最小割一條從s*到t*的路徑，就對應了一個s-t割！更進一步，如果t*8*令每5 條邊的長度等于它的容量，那么最小割的容量就等于最短路的5*7*6*長度！s1t368分析一下時間復3*雜度2*4*新圖中的點數(shù)和邊數(shù)都是O(n)的47使用二叉堆優(yōu)化的Di1j*kss*tra算法求最短路，時間復雜度為O(nlog2n)利用最短路求最大流可以利用最短路算法得到的距離標號構造一個最大流定理2.1可以在O(nlog2n)的時間內求出s-t平面圖上的最大流。小結回顧得到簡單的最大流模型利用最大流最

7、小割定理進行模型轉化根據(jù)平面圖的性質解決最小割問題構造得到最大流最大最小定理對比以上兩個定理定義3.1最大最小定理是一類描述同一個對象上的一個最大化問題的解和一個最小化問題的解之間的關系的定理。最大最小定理共同點的兩個最優(yōu)化問題互為對偶問題證明的過程最大化問題M的任何一個解m的值都不超過最小化問題N的任何一個解n的值可以找到M的一個解p和N的一個解q，且它們的值相等p和q分別為各自問題的一個最優(yōu)解簡潔的最優(yōu)性證明總結Knig定理最大匹配最小覆蓋最大最小定理最大流最小割定理最大流最小割最大注意總結、積累勇于探索完全互相轉化最小參考文獻roduction to Graph Theory, Seco

8、nd Edition by Douglas B. West Network Flows: Theory, Algorithmsand Applications by Ravindra K. Ahuja, Thomas L. Magnanti, and James B. Orlinroductory Combinatorics, Third Edition by Richard A. BrualdiI.II.III.IV.運籌學（第三版）大家，歡迎提問！的例子二部圖中最大獨立集的大小等于最小邊覆蓋數(shù)頂點的最大度數(shù)等于最小邊染色數(shù)3正則圖中點度等于邊度如何構造最大流？用d(j*)表示新圖中s*到j

9、*的最短路的長度對于每條邊(i*,j*)，d(j*)d(i*)+ci*j*G中的每條邊(i,j)，設G*與其對應的邊為(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*。顯然(dj* d (i) (i*, *)*k的流入量等于流出量，即x滿足流量平衡如何構造最大流？設P*是G*中從s*到t*的一條最短路對于任意的(i*,j*) P*，都有d(j*)-d(i*)=ci*j*P*

10、中的邊了原圖中的一個s-t割Q。根據(jù)上式和ci*j*=uij對于任意的(i,j)Q，都有xij=uij。x的流量等于Q的容量x是最大流，Q是最小割復雜度問題只考慮題目中給出的邊需要通過寬搜得到所有的面，且需要處理面與面之間的關系思維復雜度與編程復雜度均比較高可以認為原來不存在的邊容量為0不影響面與面之間的關系清晰明了大大降低思維和編程復雜度最大最小定理和線性規(guī)劃線性規(guī)劃定義:在滿足一些線性等式或者不等式的條件下，最優(yōu)化一個線性函數(shù)標準形式：maxzcxs t A x 0整數(shù)線性規(guī)劃最大最小定理和線性規(guī)劃對偶問題maxzcxminwybA yTs t .x 0y 0最大最小定理和線性規(guī)劃基本性質

11、弱對偶性如果x是原問題的可行解，y是其對偶問題的可行解，則恒有c*x b*y最優(yōu)性如果x是原問題的可行解，y是其對偶問題的可行解，且有c*x = b*y，則x和y是各自問題的最優(yōu)解強最優(yōu)性（對偶定理）如果原問題及其對偶問題均有可行解，則兩者均有最優(yōu)解，且最優(yōu)解的目標函數(shù)值相同最大最小定理和線性規(guī)劃二部圖最大匹配每個變量x對應一條邊對于每個頂點v，S(v)表示所有與v關聯(lián)的邊的集合max xeeE(G), xe 0,1v.v Ve最大最小定理和線性規(guī)劃二部圖最小覆蓋每個變量y對應一個點 yvv)(minv V (0,1.),vu v) E Gyu yv最大最小定理和線性規(guī)劃弱對偶性：最大匹配的大小不超過最小覆蓋的大小最優(yōu)性：如果一個匹配M和一個覆蓋S的大小相等，那么M就是最大匹配，S就是最小覆蓋強對偶性最大匹配等于最小覆蓋弱對偶性的證明nm cj 1 i 1i yi證明nnmmn x jc xAij yiAj xyi因為jjj 1 j 1i 1i 1j 1mmnmnbi yi yi