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

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

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

3、輸通道，每條連接兩個水平或垂直相鄰的方格，最大運輸量為Li(1,1)內(nèi)有很多干草，F(xiàn)armer John希望將最多的干草運送到(R,C)內(nèi)求最大運輸量第7頁，共42頁，2022年，5月20日，11點33分，星期四例二 Moving the Hay一個R=C=3的例子，最大運輸量為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頁，共42頁，2022年，5月20日，11點33分，星期四分析直接求最大流以每個方格為點，每條通道為邊，邊的容量就是它的最大運輸量 從(1,1)到(R,

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

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

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

7、 f*)第17頁，共42頁，2022年，5月20日，11點33分，星期四對偶圖舉例4523161*2*3*4*第18頁，共42頁，2022年，5月20日，11點33分，星期四平面圖與其對偶圖的關系平面圖G與其對偶圖G*之間存在怎樣的關系呢？G的面數(shù)等于G*的點數(shù)，G*的點數(shù)等于G的面數(shù)，G與G*邊數(shù)相同G*中的環(huán)對應G中的割一一對應4523161*2*3*4*第19頁，共42頁，2022年，5月20日，11點33分，星期四s-t平面圖上最大流的快速求法如何利用這些性質(zhì)？直接求解仍然困難利用最大流最小割定理轉化模型根據(jù)平面圖與其對偶圖的關系，想辦法求出最小割第20頁，共42頁，2022年，5月2

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

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

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

11、共42頁，2022年，5月20日，11點33分，星期四參考文獻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運籌學教程（第三版） 胡運權 郭耀煌第28頁，共42頁，2022

12、年，5月20日，11點33分，星期四謝謝大家，歡迎提問！第29頁，共42頁，2022年，5月20日，11點33分，星期四更多的例子二部圖中最大獨立集的大小等于最小邊覆蓋數(shù)頂點的最大度數(shù)等于最小邊染色數(shù) 3正則圖中點聯(lián)通度等于邊聯(lián)通度第30頁，共42頁，2022年，5月20日，11點33分，星期四如何構造最大流？我們用d(j*)表示新圖中s*到j*的最短路的長度對于每條邊(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*第31

13、頁，共42頁，2022年，5月20日，11點33分，星期四如何構造最大流？對于G中的任何一個異于s和t的節(jié)點k，定義割Q=k，V-k包含所有與k相關的邊。那么Q中的所有邊對應到G*就形成了一個環(huán)，稱為W*。 顯然k的流入量等于流出量，即x滿足流量平衡第32頁，共42頁，2022年，5月20日，11點33分，星期四如何構造最大流？設P*是G*中從s*到t*的一條最短路對于任意的(i*,j*) P*，都有d(j*)-d(i*)=ci*j*P*中的邊構成了原圖中的一個s-t割Q。根據(jù)上式和ci*j*=uij可得對于任意的(i,j)Q，都有xij=uij。 x的流量等于Q的容量x是最大流，Q是最小割第

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

15、最大最小定理和線性規(guī)劃基本性質(zhì)弱對偶性如果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ù)值相同第37頁，共42頁，2022年，5月20日，11點33分，星期四最大最小定理和線性規(guī)劃二部圖最大匹配每個變量x對應一條邊對于每個頂點v，S(v)表示所有與v關聯(lián)的邊的集合第38頁，共42頁，2022年，5月20日，11點33分，星期四最大最小定理和線性規(guī)劃二部圖最小覆蓋每個變量y對應一個點第39頁，共42頁，2022年，5月20日，11點33分