平面圖最小割

1、1淺析最大最小定理在信息學(xué)競(jìng)賽中的應(yīng)用淺析最大最小定理在信息學(xué)競(jìng)賽中的應(yīng)用2 我們?cè)谛畔W(xué)競(jìng)賽中經(jīng)常會(huì)遇到一些涉及一個(gè)最大化問題和一個(gè)最小化問題的定理 怎樣利用這些定理幫助我們解題呢？Knig定理定理最大流最大流最小割定理最小割定理3 主要內(nèi)容n在任何一個(gè)二部圖G中，最大匹配數(shù)r(G)等于最小覆蓋數(shù)c(G)4 證明n最大匹配數(shù)不超過最小覆蓋數(shù)n任取一個(gè)最小覆蓋Q，一定可以構(gòu)造出一個(gè)與之大小相等的匹配Mr(G) c(G)r(G) = c(G)c(G) |Q| = |M| r (G) c(G) r(G)5 應(yīng)用n二部圖最小覆蓋和最大匹配的互相轉(zhuǎn)化n例一 Muddy Fields6近年來，網(wǎng)絡(luò)流尤其

2、是最大流問題越來越多的出現(xiàn)在各類信息學(xué)競(jìng)賽當(dāng)中最大流最小割定理是整個(gè)最大流問題的基礎(chǔ)與核心，其主要內(nèi)容是：最大流的流量不超過最小割的容量1.存在一個(gè)流x和一個(gè)割c，且x的流量等于c的容量7 一個(gè)牧場(chǎng)由R*C個(gè)格子組成 牧場(chǎng)內(nèi)有N條干草運(yùn)輸通道，每條連接兩個(gè)水平或垂直相鄰的方格，最大運(yùn)輸量為L(zhǎng)i (1,1)內(nèi)有很多干草，F(xiàn)armer John希望將最多的干草運(yùn)送到(R,C)內(nèi) 求最大運(yùn)輸量8 一個(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)9 直

3、接求最大流n以每個(gè)方格為點(diǎn)，每條通道為邊，邊的容量就是它的最大運(yùn)輸量 n從(1,1)到(R,C)的最大運(yùn)輸量就是將這兩個(gè)方格對(duì)應(yīng)的點(diǎn)分別作為流網(wǎng)絡(luò)中的源和匯求出的最大流量 效率？n點(diǎn)數(shù)最大40000，邊數(shù)最大80000！Time Limit Exceeded!10 效率低下的原因n沒有利用題目的特點(diǎn)，直接套用經(jīng)典算法 特點(diǎn)n題目中給出的是一個(gè)平面圖n圖中的一個(gè)點(diǎn)為源點(diǎn)s，另外一個(gè)點(diǎn)為匯點(diǎn)t，且s和t都在圖中的無界面的邊界上11452316f1f2f3f412 效率低下的原因n沒有利用題目的特點(diǎn)，直接套用經(jīng)典算法 特點(diǎn)n題目中給出的是一個(gè)平面圖n圖中的一個(gè)點(diǎn)為源點(diǎn)s，另外一個(gè)點(diǎn)為匯點(diǎn)t，且s和t

4、都在圖中的無界面的邊界上n我們稱這樣的平面圖為s-t平面圖平面圖13平面圖性質(zhì) （歐拉公式）如果一個(gè)連通的平面圖有n個(gè)點(diǎn)，m條邊和f個(gè)面，那么f=m-n+2 每個(gè)平面圖G都有一個(gè)與其對(duì)偶的平面圖G*n G*中的每個(gè)點(diǎn)對(duì)應(yīng)G中的一個(gè)面144523161*2*3*4*15平面圖性質(zhì) （歐拉公式）如果一個(gè)連通的平面圖有n個(gè)點(diǎn)，m條邊和f個(gè)面，那么f=m-n+2 每個(gè)平面圖G都有一個(gè)與其對(duì)偶的平面圖G*n G*中的每個(gè)點(diǎn)對(duì)應(yīng)G中的一個(gè)面n 對(duì)于G中的每條邊en e屬于兩個(gè)面f1、f2，加入邊(f1*， f2*)164523161*2*3*4*17平面圖性質(zhì) （歐拉公式）如果一個(gè)連通的平面圖有n個(gè)點(diǎn)，m

5、條邊和f個(gè)面，那么f=m-n+2 每個(gè)平面圖G都有一個(gè)與其對(duì)偶的平面圖G*n G*中的每個(gè)點(diǎn)對(duì)應(yīng)G中的一個(gè)面n 對(duì)于G中的每條邊en e屬于兩個(gè)面f1、f2，加入邊(f1*， f2*)n e只屬于一個(gè)面f，加入回邊(f*， f*)184523161*2*3*4*19 平面圖G與其對(duì)偶圖G*之間存在怎樣的關(guān)系呢？nG的面數(shù)等于G*的點(diǎn)數(shù)，G*的點(diǎn)數(shù)等于G的面數(shù)，G與G*邊數(shù)相同nG*中的環(huán)對(duì)應(yīng)G中的割一一對(duì)應(yīng)4523161*2*3*4*20 如何利用這些性質(zhì)？n直接求解仍然困難n利用最大流最小割定理轉(zhuǎn)化模型轉(zhuǎn)化模型根據(jù)平面圖與其對(duì)偶圖的關(guān)系，想辦法求出最小割21 對(duì)于一個(gè)s-t平面圖，我們對(duì)其進(jìn)

6、行如下改造：n連接s和t，得到一個(gè)附加面附加面 對(duì)于一個(gè)s-t平面圖，我們對(duì)其進(jìn)行如下改造：n求該圖的對(duì)偶圖G*，令附加面對(duì)應(yīng)的點(diǎn)為s*，無界面對(duì)應(yīng)的點(diǎn)為t* 對(duì)于一個(gè)s-t平面圖，我們對(duì)其進(jìn)行如下改造：n刪去s*和t*之間的邊123456781*3*2*4*5*7*6*8*sts*t*22 一條從s*到t*的路徑，就對(duì)應(yīng)了一個(gè)s-t割！ 更進(jìn)一步，如果我們令每條邊的長(zhǎng)度等于它的容量，那么最小割的容量就等于最短路的長(zhǎng)度！ 分析一下時(shí)間復(fù)雜度n新圖中的點(diǎn)數(shù)和邊數(shù)都是O(n)的n使用二叉堆優(yōu)化的Dijkstra算法求最短路，時(shí)間復(fù)雜度為O(nlog2n)123456781*3*2*4*5*7*6*

7、8*sts*t*23 我們可以利用最短路算法得到的距離標(biāo)號(hào)構(gòu)造一個(gè)最大流 定理2.1 n可以在O(nlog2n)的時(shí)間內(nèi)求出s-t平面圖上的最大流。24 回顧得到簡(jiǎn)單的最大流模型利用最大流最小割定理進(jìn)行模型轉(zhuǎn)化根據(jù)平面圖的性質(zhì)解決最小割問題構(gòu)造得到最大流25 對(duì)比以上兩個(gè)定理 定義3.1n最大最大最小定理最小定理是一類描述同一個(gè)對(duì)象上的一個(gè)最大化問題的解和一個(gè)最小化問題的解之間的關(guān)系的定理。26 共同點(diǎn)n考察的兩個(gè)最優(yōu)化問題互為對(duì)偶問題n證明的過程n最大化問題M的任何一個(gè)解m的值都不超過最小化問題N的任何一個(gè)解n的值n可以找到M的一個(gè)解p和N的一個(gè)解q，且它們的值相等np和q分別為各自問題的一

8、個(gè)最優(yōu)解 簡(jiǎn)潔的最優(yōu)性證明27Knig定理定理最大流最大流最小割定理最小割定理最大最大最小定理最小定理最大匹配最大匹配最小覆蓋最小覆蓋最大流最大流最小割最小割模型轉(zhuǎn)化最大最大最小最小完全矛盾完全矛盾互相轉(zhuǎn)化互相轉(zhuǎn)化注意總結(jié)、積累注意總結(jié)、積累勇于探索勇于探索28Introduction to Graph Theory, Second Edition by Douglas B. WestNetwork Flows: Theory, Algorithms and Applications by Ravindra K. Ahuja, Thomas L. Magnanti, and James B.

9、OrlinIntroductory Combinatorics, Third Edition by Richard A. Brualdi運(yùn)籌學(xué)教程（第三版） 胡運(yùn)權(quán) 郭耀煌29謝謝大家，歡迎提問！30 二部圖中n最大獨(dú)立集的大小等于最小邊覆蓋數(shù)n頂點(diǎn)的最大度數(shù)等于最小邊染色數(shù) 3正則圖中n點(diǎn)聯(lián)通度等于邊聯(lián)通度 31 我們用d(j*)表示新圖中s*到j(luò)*的最短路的長(zhǎng)度n對(duì)于每條邊(i*,j*)，d(j*)d(i*)+ci*j* G中的每條邊(i,j)，設(shè)G*與其對(duì)應(yīng)的邊為(i*,j*)，定義流量xij=d(j*)-d(i*)n反對(duì)稱性：xij=-xjin容量限制：xij=d(j*)-d(i*)c

10、i*j*32 對(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滿足流量平衡0*)(*)(*)*,(Wjiidjd33 設(shè)P*是G*中從s*到t*的一條最短路n對(duì)于任意的(i*,j*) P*，都有d(j*)-d(i*)=ci*j* P*中的邊構(gòu)成了原圖中的一個(gè)s-t割Q。根據(jù)上式和ci*j*=uij可得n對(duì)于任意的(i,j)Q，都有xij=uij。 x的流量等于Q的容量nx是最大流，Q是最小割34 只考慮題目中給出的邊n需要通過寬搜得到所有的面，且需要處理面與面之間的關(guān)系n思維復(fù)

11、雜度與編程復(fù)雜度均比較高 可以認(rèn)為原來不存在的邊容量為0n不影響答案n面與面之間的關(guān)系清晰明了n大大降低思維和編程復(fù)雜度35 線性規(guī)劃n定義:在滿足一些線性等式或者不等式的條件下，最優(yōu)化一個(gè)線性函數(shù) n標(biāo)準(zhǔn)形式： 整數(shù)線性規(guī)劃0. .maxxbxAtsxcz36 對(duì)偶問題0. .minycAytsbywT0. .maxxbxAtsxcz37 基本性質(zhì)n弱對(duì)偶性n如果x是原問題的可行解，y是其對(duì)偶問題的可行解，則恒有c*x b*yn最優(yōu)性n如果x是原問題的可行解，y是其對(duì)偶問題的可行解，且有c*x = b*y，則x和y是各自問題的最優(yōu)解n強(qiáng)最優(yōu)性（對(duì)偶定理）n如果原問題及其對(duì)偶問題均有可行解，則

12、兩者均有最優(yōu)解，且最優(yōu)解的目標(biāo)函數(shù)值相同38 二部圖最大匹配n每個(gè)變量x對(duì)應(yīng)一條邊n對(duì)于每個(gè)頂點(diǎn)v，S(v)表示所有與v關(guān)聯(lián)的邊的集合)(1),(1 , 0),(. .maxvSeeeEeexGVvxGEetsx39 二部圖最小覆蓋n每個(gè)變量y對(duì)應(yīng)一個(gè)點(diǎn)1),(),(1 , 0),(. .min)(vuvGVvvyyGEvuyGVvtsy40 弱對(duì)偶性：n最大匹配的大小不超過最小覆蓋的大小 最優(yōu)性：n如果一個(gè)匹配M和一個(gè)覆蓋S的大小相等，那么M就是最大匹配，S就是最小覆蓋 強(qiáng)對(duì)偶性n最大匹配等于最小覆蓋41miiinjjjybxc11 minjijijiminjjijmiiiminjijijjnjmiiijnjjj