兩極相通淺析最大最小定理在信息學(xué)競(jìng)賽中的應(yīng)用

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

2、學(xué)競(jìng)賽當(dāng)中最大流最小割定理是整個(gè)最大流問(wèn)題的基礎(chǔ)與，其主要內(nèi)容是：1.2.最大流的流量不超過(guò)最小割的容量存在一個(gè)流x和一個(gè)割c，且x的流量等于c的容量例二 Moving the Hay一個(gè)牧場(chǎng)由R*C個(gè)格子組成牧場(chǎng)內(nèi)有N條干草通道，每條連接兩個(gè)量為L(zhǎng)i水平或垂直相鄰的方格，最大(1,1)內(nèi)有很多干草，F(xiàn)armer John希望將最多的干草運(yùn)送到(R,C)內(nèi)求最大量例二 Moving the Hay一個(gè)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、接求最大流以每個(gè)方格為點(diǎn)，每條通道為邊，邊的容量就是它的最大量從(1,1)到(R,C)的最大量就是將這兩個(gè)方格對(duì)應(yīng)的點(diǎn)分別作為流網(wǎng)絡(luò)中的源和匯求出的最大流量效率？點(diǎn)數(shù)最大40000，邊數(shù)最大80000！分析效率低下的原因沒(méi)有利用題目的特點(diǎn)，直接套用經(jīng)典算法特點(diǎn)題目中給出的是一個(gè)平面圖圖中的一個(gè)點(diǎn)為源點(diǎn)s，另外一個(gè)點(diǎn)為匯點(diǎn)t，且s和t都在圖中的面的邊界上分析24f2f11f335f46分析效率低下的原因沒(méi)有利用題目的特點(diǎn)，直接套用經(jīng)典算法特點(diǎn)題目中給出的是一個(gè)平面圖圖中的一個(gè)點(diǎn)為源點(diǎn)s，另外一個(gè)點(diǎn)為匯點(diǎn)t，且s和t都在圖中的面的邊界上稱這樣的平面圖為s-t平面圖平面圖的性質(zhì)平面圖性質(zhì)1.通的平面

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

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

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

7、小割定理進(jìn)行模型轉(zhuǎn)化根據(jù)平面圖的性質(zhì)解決最小割問(wèn)題構(gòu)造得到最大流最大最小定理對(duì)比以上兩個(gè)定理定義3.1最大最小定理是一類描述同一個(gè)對(duì)象上的一個(gè)最大化問(wèn)題的解和一個(gè)最小化問(wèn)題的解之間的關(guān)系的定理。最大最小定理共同點(diǎn)的兩個(gè)最優(yōu)化問(wèn)題互為對(duì)偶問(wèn)題證明的過(guò)程最大化問(wèn)題M的任何一個(gè)解m的值都不超過(guò)最小化問(wèn)題N的任何一個(gè)解n的值可以找到M的一個(gè)解p和N的一個(gè)解q，且它們的值相等p和q分別為各自問(wèn)題的一個(gè)最優(yōu)解簡(jiǎn)潔的最優(yōu)性證明總結(jié)Knig定理最大匹配最小覆蓋最大最小定理最大流最小割定理最大流最小割最大注意總結(jié)、積累勇于探索完全互相轉(zhuǎn)化最小參考文獻(xiàn)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.運(yùn)籌學(xué)（第三版）大家，歡迎提問(wèn)！的例子二部圖中最大獨(dú)立集的大小等于最小邊覆蓋數(shù)頂點(diǎn)的最大度數(shù)等于最小邊染色數(shù)3正則圖中點(diǎn)度等于邊度如何構(gòu)造最大流？用d(j*)表示新圖中s*到j(luò)

9、*的最短路的長(zhǎng)度對(duì)于每條邊(i*,j*)，d(j*)d(i*)+ci*j*G中的每條邊(i,j)，設(shè)G*與其對(duì)應(yīng)的邊為(i*,j*)，定義流量xij=d(j*)-d(i*)稱性：xij=-xji容量限制：xij=d(j*)-d(i*)ci*j*如何構(gòu)造最大流？對(duì)于G中的任何一個(gè)異于s和t的節(jié)點(diǎn)k，定義割Q=k，V-k包含所有與k相關(guān)的邊。那么Q中的所有邊對(duì)應(yīng)到G*就形成了一個(gè)環(huán)，稱為W*。顯然(dj* d (i) (i*, *)*k的流入量等于流出量，即x滿足流量平衡如何構(gòu)造最大流？設(shè)P*是G*中從s*到t*的一條最短路對(duì)于任意的(i*,j*) P*，都有d(j*)-d(i*)=ci*j*P*

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

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