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

1、淺析最大最小定理在信息學(xué)競(jìng)賽中的應(yīng)用第1頁(yè)，共42頁(yè)，2022年，5月20日，11點(diǎn)33分，星期四引入我們?cè)谛畔W(xué)競(jìng)賽中經(jīng)常會(huì)遇到一些涉及一個(gè)最大化問題和一個(gè)最小化問題的定理怎樣利用這些定理幫助我們解題呢？Knig定理最大流最小割定理第2頁(yè)，共42頁(yè)，2022年，5月20日，11點(diǎn)33分，星期四Knig定理主要內(nèi)容在任何一個(gè)二部圖G中，最大匹配數(shù)r(G)等于最小覆蓋數(shù)c(G)第3頁(yè)，共42頁(yè)，2022年，5月20日，11點(diǎn)33分，星期四Knig定理證明最大匹配數(shù)不超過最小覆蓋數(shù)任取一個(gè)最小覆蓋Q，一定可以構(gòu)造出一個(gè)與之大小相等的匹配Mr(G) c(G)r(G) = c(G)c(G) |Q| =

2、 |M| r (G) c(G) r(G)第4頁(yè)，共42頁(yè)，2022年，5月20日，11點(diǎn)33分，星期四Knig定理應(yīng)用二部圖最小覆蓋和最大匹配的互相轉(zhuǎn)化例一 Muddy Fields第5頁(yè)，共42頁(yè)，2022年，5月20日，11點(diǎn)33分，星期四最大流最小割定理近年來(lái)，網(wǎng)絡(luò)流尤其是最大流問題越來(lái)越多的出現(xiàn)在各類信息學(xué)競(jìng)賽當(dāng)中最大流最小割定理是整個(gè)最大流問題的基礎(chǔ)與核心，其主要內(nèi)容是：最大流的流量不超過最小割的容量存在一個(gè)流x和一個(gè)割c，且x的流量等于c的容量第6頁(yè)，共42頁(yè)，2022年，5月20日，11點(diǎn)33分，星期四例二 Moving the Hay一個(gè)牧場(chǎng)由R*C個(gè)格子組成牧場(chǎng)內(nèi)有N條干草運(yùn)

3、輸通道，每條連接兩個(gè)水平或垂直相鄰的方格，最大運(yùn)輸量為L(zhǎng)i(1,1)內(nèi)有很多干草，F(xiàn)armer John希望將最多的干草運(yùn)送到(R,C)內(nèi)求最大運(yùn)輸量第7頁(yè)，共42頁(yè)，2022年，5月20日，11點(diǎn)33分，星期四例二 Moving the Hay一個(gè)R=C=3的例子，最大運(yùn)輸量為7數(shù)據(jù)規(guī)模：R,C 200(1,1)(1,2)(1,3)(2,1)(2,2)(2,3)(3,2)(3,3)5,53,25,52,21,16,64,17,6(3,1)第8頁(yè)，共42頁(yè)，2022年，5月20日，11點(diǎn)33分，星期四分析直接求最大流以每個(gè)方格為點(diǎn)，每條通道為邊，邊的容量就是它的最大運(yùn)輸量 從(1,1)到(R,

4、C)的最大運(yùn)輸量就是將這兩個(gè)方格對(duì)應(yīng)的點(diǎn)分別作為流網(wǎng)絡(luò)中的源和匯求出的最大流量效率？點(diǎn)數(shù)最大40000，邊數(shù)最大80000！Time Limit Exceeded!第9頁(yè)，共42頁(yè)，2022年，5月20日，11點(diǎn)33分，星期四分析效率低下的原因沒有利用題目的特點(diǎn)，直接套用經(jīng)典算法特點(diǎn)題目中給出的是一個(gè)平面圖圖中的一個(gè)點(diǎn)為源點(diǎn)s，另外一個(gè)點(diǎn)為匯點(diǎn)t，且s和t都在圖中的無(wú)界面的邊界上第10頁(yè)，共42頁(yè)，2022年，5月20日，11點(diǎn)33分，星期四分析452316f1f2f3f4第11頁(yè)，共42頁(yè)，2022年，5月20日，11點(diǎn)33分，星期四分析效率低下的原因沒有利用題目的特點(diǎn)，直接套用經(jīng)典算法特點(diǎn)

5、題目中給出的是一個(gè)平面圖圖中的一個(gè)點(diǎn)為源點(diǎn)s，另外一個(gè)點(diǎn)為匯點(diǎn)t，且s和t都在圖中的無(wú)界面的邊界上我們稱這樣的平面圖為s-t平面圖第12頁(yè)，共42頁(yè)，2022年，5月20日，11點(diǎn)33分，星期四平面圖的性質(zhì)平面圖性質(zhì)（歐拉公式）如果一個(gè)連通的平面圖有n個(gè)點(diǎn)，m條邊和f個(gè)面，那么f=m-n+2每個(gè)平面圖G都有一個(gè)與其對(duì)偶的平面圖G*G*中的每個(gè)點(diǎn)對(duì)應(yīng)G中的一個(gè)面第13頁(yè)，共42頁(yè)，2022年，5月20日，11點(diǎn)33分，星期四對(duì)偶圖舉例4523161*2*3*4*第14頁(yè)，共42頁(yè)，2022年，5月20日，11點(diǎn)33分，星期四平面圖的性質(zhì)平面圖性質(zhì)（歐拉公式）如果一個(gè)連通的平面圖有n個(gè)點(diǎn)，m條邊和

6、f個(gè)面，那么f=m-n+2每個(gè)平面圖G都有一個(gè)與其對(duì)偶的平面圖G*G*中的每個(gè)點(diǎn)對(duì)應(yīng)G中的一個(gè)面對(duì)于G中的每條邊ee屬于兩個(gè)面f1、f2，加入邊(f1*， f2*)第15頁(yè)，共42頁(yè)，2022年，5月20日，11點(diǎn)33分，星期四對(duì)偶圖舉例4523161*2*3*4*第16頁(yè)，共42頁(yè)，2022年，5月20日，11點(diǎn)33分，星期四平面圖的性質(zhì)平面圖性質(zhì)（歐拉公式）如果一個(gè)連通的平面圖有n個(gè)點(diǎn)，m條邊和f個(gè)面，那么f=m-n+2每個(gè)平面圖G都有一個(gè)與其對(duì)偶的平面圖G*G*中的每個(gè)點(diǎn)對(duì)應(yīng)G中的一個(gè)面對(duì)于G中的每條邊ee屬于兩個(gè)面f1、f2，加入邊(f1*， f2*)e只屬于一個(gè)面f，加入回邊(f*，

7、 f*)第17頁(yè)，共42頁(yè)，2022年，5月20日，11點(diǎn)33分，星期四對(duì)偶圖舉例4523161*2*3*4*第18頁(yè)，共42頁(yè)，2022年，5月20日，11點(diǎn)33分，星期四平面圖與其對(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)4523161*2*3*4*第19頁(yè)，共42頁(yè)，2022年，5月20日，11點(diǎn)33分，星期四s-t平面圖上最大流的快速求法如何利用這些性質(zhì)？直接求解仍然困難利用最大流最小割定理轉(zhuǎn)化模型根據(jù)平面圖與其對(duì)偶圖的關(guān)系，想辦法求出最小割第20頁(yè)，共42頁(yè)，2022年，5月2

8、0日，11點(diǎn)33分，星期四利用最短路求最小割對(duì)于一個(gè)s-t平面圖，我們對(duì)其進(jìn)行如下改造：連接s和t，得到一個(gè)附加面對(duì)于一個(gè)s-t平面圖，我們對(duì)其進(jìn)行如下改造：求該圖的對(duì)偶圖G*，令附加面對(duì)應(yīng)的點(diǎn)為s*，無(wú)界面對(duì)應(yīng)的點(diǎn)為t*對(duì)于一個(gè)s-t平面圖，我們對(duì)其進(jìn)行如下改造：刪去s*和t*之間的邊123456781*3*2*4*5*7*6*8*sts*t*第21頁(yè)，共42頁(yè)，2022年，5月20日，11點(diǎn)33分，星期四利用最短路求最小割一條從s*到t*的路徑，就對(duì)應(yīng)了一個(gè)s-t割！更進(jìn)一步，如果我們令每條邊的長(zhǎng)度等于它的容量，那么最小割的容量就等于最短路的長(zhǎng)度！分析一下時(shí)間復(fù)雜度新圖中的點(diǎn)數(shù)和邊數(shù)都是O

9、(n)的使用二叉堆優(yōu)化的Dijkstra算法求最短路，時(shí)間復(fù)雜度為O(nlog2n)123456781*3*2*4*5*7*6*8*sts*t*第22頁(yè)，共42頁(yè)，2022年，5月20日，11點(diǎn)33分，星期四利用最短路求最大流我們可以利用最短路算法得到的距離標(biāo)號(hào)構(gòu)造一個(gè)最大流定理2.1 可以在O(nlog2n)的時(shí)間內(nèi)求出s-t平面圖上的最大流。第23頁(yè)，共42頁(yè)，2022年，5月20日，11點(diǎn)33分，星期四小結(jié)回顧得到簡(jiǎn)單的最大流模型利用最大流最小割定理進(jìn)行模型轉(zhuǎn)化根據(jù)平面圖的性質(zhì)解決最小割問題構(gòu)造得到最大流第24頁(yè)，共42頁(yè)，2022年，5月20日，11點(diǎn)33分，星期四最大最小定理對(duì)比以上

10、兩個(gè)定理定義3.1最大最小定理是一類描述同一個(gè)對(duì)象上的一個(gè)最大化問題的解和一個(gè)最小化問題的解之間的關(guān)系的定理。第25頁(yè)，共42頁(yè)，2022年，5月20日，11點(diǎn)33分，星期四最大最小定理共同點(diǎn)考察的兩個(gè)最優(yōu)化問題互為對(duì)偶問題證明的過程最大化問題M的任何一個(gè)解m的值都不超過最小化問題N的任何一個(gè)解n的值可以找到M的一個(gè)解p和N的一個(gè)解q，且它們的值相等p和q分別為各自問題的一個(gè)最優(yōu)解簡(jiǎn)潔的最優(yōu)性證明第26頁(yè)，共42頁(yè)，2022年，5月20日，11點(diǎn)33分，星期四總結(jié)Knig定理最大流最小割定理最大最小定理最大匹配最小覆蓋最大流最小割模型轉(zhuǎn)化最大最小完全矛盾互相轉(zhuǎn)化注意總結(jié)、積累勇于探索第27頁(yè)，

11、共42頁(yè)，2022年，5月20日，11點(diǎn)33分，星期四參考文獻(xiàn)Introduction to Graph Theory, Second Edition by Douglas B. WestNetwork Flows: Theory, Algorithms and Applications by Ravindra K. Ahuja, Thomas L. Magnanti, and James B. OrlinIntroductory Combinatorics, Third Edition by Richard A. Brualdi運(yùn)籌學(xué)教程（第三版） 胡運(yùn)權(quán) 郭耀煌第28頁(yè)，共42頁(yè)，2022

12、年，5月20日，11點(diǎn)33分，星期四謝謝大家，歡迎提問！第29頁(yè)，共42頁(yè)，2022年，5月20日，11點(diǎn)33分，星期四更多的例子二部圖中最大獨(dú)立集的大小等于最小邊覆蓋數(shù)頂點(diǎn)的最大度數(shù)等于最小邊染色數(shù) 3正則圖中點(diǎn)聯(lián)通度等于邊聯(lián)通度第30頁(yè)，共42頁(yè)，2022年，5月20日，11點(diǎn)33分，星期四如何構(gòu)造最大流？我們用d(j*)表示新圖中s*到j(luò)*的最短路的長(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*)反對(duì)稱性：xij=-xji容量限制：xij=d(j*)-d(i*)ci*j*第31

13、頁(yè)，共42頁(yè)，2022年，5月20日，11點(diǎn)33分，星期四如何構(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*。 顯然k的流入量等于流出量，即x滿足流量平衡第32頁(yè)，共42頁(yè)，2022年，5月20日，11點(diǎn)33分，星期四如何構(gòu)造最大流？設(shè)P*是G*中從s*到t*的一條最短路對(duì)于任意的(i*,j*) P*，都有d(j*)-d(i*)=ci*j*P*中的邊構(gòu)成了原圖中的一個(gè)s-t割Q。根據(jù)上式和ci*j*=uij可得對(duì)于任意的(i,j)Q，都有xij=uij。 x的流量等于Q的容量x是最大流，Q是最小割第

14、33頁(yè)，共42頁(yè)，2022年，5月20日，11點(diǎn)33分，星期四復(fù)雜度問題只考慮題目中給出的邊需要通過寬搜得到所有的面，且需要處理面與面之間的關(guān)系思維復(fù)雜度與編程復(fù)雜度均比較高可以認(rèn)為原來(lái)不存在的邊容量為0不影響答案面與面之間的關(guān)系清晰明了大大降低思維和編程復(fù)雜度第34頁(yè)，共42頁(yè)，2022年，5月20日，11點(diǎn)33分，星期四最大最小定理和線性規(guī)劃線性規(guī)劃定義:在滿足一些線性等式或者不等式的條件下，最優(yōu)化一個(gè)線性函數(shù) 標(biāo)準(zhǔn)形式：整數(shù)線性規(guī)劃第35頁(yè)，共42頁(yè)，2022年，5月20日，11點(diǎn)33分，星期四最大最小定理和線性規(guī)劃對(duì)偶問題第36頁(yè)，共42頁(yè)，2022年，5月20日，11點(diǎn)33分，星期四

15、最大最小定理和線性規(guī)劃基本性質(zhì)弱對(duì)偶性如果x是原問題的可行解，y是其對(duì)偶問題的可行解，則恒有c*x b*y最優(yōu)性如果x是原問題的可行解，y是其對(duì)偶問題的可行解，且有c*x = b*y，則x和y是各自問題的最優(yōu)解強(qiáng)最優(yōu)性（對(duì)偶定理）如果原問題及其對(duì)偶問題均有可行解，則兩者均有最優(yōu)解，且最優(yōu)解的目標(biāo)函數(shù)值相同第37頁(yè)，共42頁(yè)，2022年，5月20日，11點(diǎn)33分，星期四最大最小定理和線性規(guī)劃二部圖最大匹配每個(gè)變量x對(duì)應(yīng)一條邊對(duì)于每個(gè)頂點(diǎn)v，S(v)表示所有與v關(guān)聯(lián)的邊的集合第38頁(yè)，共42頁(yè)，2022年，5月20日，11點(diǎn)33分，星期四最大最小定理和線性規(guī)劃二部圖最小覆蓋每個(gè)變量y對(duì)應(yīng)一個(gè)點(diǎn)第39頁(yè)，共42頁(yè)，2022年，5月20日，11點(diǎn)33分