國家集訓(xùn)隊(duì)2007論文集7[1].胡伯濤《最小割模型

1、最小割模型在信息學(xué)競(jìng)賽中的應(yīng)用Applications of Minimum Cut Modelin Informatics,胡伯濤 Amber[ADN.cn]福州第一中學(xué) Fuzhou No.1 Middle School,最小割定義,網(wǎng)絡(luò)的割[S,T] —— 將點(diǎn)集V劃分為S和T兩部分，(其中源s屬于S且匯t屬于T)，而從S指向T的邊組成割割容量 —— 割中所有邊的容量和最小割 —— 容量最小的割,,,,1

2、,2,3,4,t,,,,,s,,,,,,,最小割解法,最大流最小割定理網(wǎng)絡(luò)的最大流流值＝該網(wǎng)絡(luò)的最小割容量求解最小割的有力武器記 表示在點(diǎn)數(shù)為n，邊數(shù)為m的網(wǎng)絡(luò)中求最大流,兩個(gè)部分最大權(quán)閉合圖標(biāo)準(zhǔn)解答的一個(gè)更一般化的擴(kuò)展模型 改進(jìn)算法 達(dá)到用最大流解決該問題的理論下界,引入,NOI 2006 最大獲利最小割是最大流的對(duì)偶問題。不直觀，模型隱蔽。展示最小割模型應(yīng)用的巧妙構(gòu)圖方法和獨(dú)特思維方式,網(wǎng)絡(luò)流首次進(jìn)入N

3、OI,NOI 2006 最大獲利 (Profit)問題描述,簡(jiǎn)要描述有n個(gè)結(jié)點(diǎn)，m條無向邊可供建設(shè)。建立一個(gè)結(jié)點(diǎn)u有一定的花費(fèi)pu。建立一條無向邊有一定的非負(fù)收益we。建立一條無向邊(u, v)的必要條件是要先建立點(diǎn)u，點(diǎn)v。求最大獲利。,NOI 2006 最大獲利 (Profit)分析,目的：選出一個(gè)邊集E’, 點(diǎn)集V’。且最大化：限制條件：對(duì)于在E’中每條邊(u, v)，它的端點(diǎn)u，v一定要在V’中。提

4、出解決事件依賴關(guān)系的有力圖論工具：閉合圖。,必要條件,,邊,,依賴,點(diǎn),最大權(quán)閉合圖 定義,有向圖的閉合圖（closure）：閉合圖內(nèi)任意點(diǎn)的任意后繼也一定還在閉合圖中。 物理意義事物間依賴關(guān)系：一個(gè)事件要發(fā)生，它需要的所有前提也都一定要發(fā)生。最大權(quán)閉合圖是點(diǎn)權(quán)之和最大的閉合圖。,,其中{3, 4, 5}是一個(gè)閉合圖。3的后繼4，4的后繼5，都在閉合圖中。,1,2,3,4,5,,,,,,5,-6,7,0,-3,而{1, 4

5、, 5}不是一個(gè)閉合圖，因?yàn)辄c(diǎn)2是點(diǎn)1的后繼，但不在閉合圖中。,最大權(quán)閉合圖解決,復(fù)雜度為,解法略去,最大權(quán)閉合圖構(gòu)圖,,增加源s匯t 源s連接原圖的正權(quán)點(diǎn)，容量為相應(yīng)點(diǎn)權(quán)原圖的負(fù)權(quán)點(diǎn)連接匯t，容量為相應(yīng)點(diǎn)權(quán)的相反數(shù)原圖邊的容量為正無限.,1,2,3,4,5,,,,,,5,-6,7,0,-3,s,t,,,,,?,?,?,?,?,6,3,,最大權(quán)閉合圖解決,,復(fù)雜度為,閉合圖方案V’與不含正無限容量的割[S, T]一一對(duì)應(yīng),閉

6、合圖V’的權(quán)為正權(quán)點(diǎn)總和減去對(duì)應(yīng)割的容量,割[S, T]取最小時(shí)，閉合圖權(quán)取最大。,NOI 2006 最大獲利 (Profit)標(biāo)準(zhǔn)算法,將原題中的邊和點(diǎn)都看成事件。邊事件依賴邊的兩個(gè)端點(diǎn)事件的發(fā)生。這與閉合圖的性質(zhì)相似。構(gòu)造性地，將邊轉(zhuǎn)化為點(diǎn)事件。,2,1,,,e,NOI 2006 最大獲利 (Profit)標(biāo)準(zhǔn)算法,將所有邊都轉(zhuǎn)化為事件點(diǎn)，原圖便轉(zhuǎn)化為一個(gè)二分圖。這樣新構(gòu)造的二分圖的閉合圖就對(duì)應(yīng)了原問題的一個(gè)解。解決該二分圖的

7、最大權(quán)閉合圖即可,4,1,3,2,,,,,e1,e2,e3,e4,1,2,3,4,e1,e2,e3,e4,,,,,,,,,,轉(zhuǎn)二分圖,復(fù)雜度為,最大權(quán)閉合圖小結(jié),在任意帶權(quán)有向圖中，只要有依賴關(guān)系需要解決，最大權(quán)閉合圖都普遍適用。（普適性）在最大獲利的解決方法1中，最大權(quán)閉合圖來解決二分圖模型。（特殊性）,牛刀宰雞,對(duì)癥下藥,改進(jìn)算法提出,必要條件,邊,,依賴,點(diǎn),充分條件,邊,,創(chuàng)建,點(diǎn),正向思維（被動(dòng)）,逆向思維（主動(dòng)）,重

8、定義兩個(gè)端點(diǎn)都在點(diǎn)集V’里的所有邊組成了邊集E’即V’的導(dǎo)出子圖。,,V’間的邊E’＝ 與V’關(guān)聯(lián)的所有邊 － V’與V’補(bǔ)集之間的邊,,,改進(jìn)算法分析,先選點(diǎn)集V’再找V’之間的邊集E’,,1,3,4,2,8,7,6,5,,,,,,,,,,,圈內(nèi)的點(diǎn)組成V’藍(lán)邊組成E’紅邊組成V’與V’補(bǔ)集之間的邊,?,補(bǔ)集轉(zhuǎn)化再次逆向思維,V’,E’,割,,最小割,,最大化,,改進(jìn)算法嘗試構(gòu)圖,選出點(diǎn)集V’對(duì)于每個(gè)點(diǎn)：選或不選

9、構(gòu)圖從源向每個(gè)點(diǎn)連邊從每個(gè)點(diǎn)向匯連邊,1,2,s,t,,,,,,,,V’,對(duì)于每個(gè)點(diǎn)，割必會(huì)割斷它到源或它到匯的兩條邊中的一條不妨設(shè)，到匯的邊被割斷的點(diǎn)組成V’則V’中每個(gè)點(diǎn)連接匯的邊都在割內(nèi)選入V'的點(diǎn)的一些代價(jià)信息，可以加載到這條被割掉的邊上。,,V’間的邊E’＝ 與V’關(guān)聯(lián)的所有邊 － V’與V’補(bǔ)集之間的邊,V’間的邊E’＝ － (V’與V’補(bǔ)集之間的邊－V’關(guān)聯(lián)的所有邊),改進(jìn)算法分析,,v,3,

10、2,,,,,,V’,4,5,,湊入最小割,微觀地，考察單獨(dú)的在V’中點(diǎn)v與v關(guān)聯(lián)所有E’內(nèi)的邊 = －（與v關(guān)聯(lián)所有割邊－與v關(guān)聯(lián)所有邊）,令 表示與點(diǎn)v關(guān)聯(lián)的總邊權(quán)和,v,s,t,,,每個(gè)點(diǎn)到匯的邊容量為,V’間的邊E’＋ V’的點(diǎn)權(quán)＝ － (V’與V’補(bǔ)集之間的邊－與V’關(guān)聯(lián)的所有邊－V’的點(diǎn)權(quán)),V’間的邊E’ ＝ － (V’與V’補(bǔ)集之間的邊－與V’關(guān)聯(lián)的所有邊),由于最小割算法只能處理非負(fù)邊權(quán)，故在每條邊的

11、容量加上一個(gè)足夠大的數(shù)U即可。,改進(jìn)算法構(gòu)圖,1,2,s,t,,,,,每個(gè)點(diǎn)向匯連的邊的容量為,考慮點(diǎn)權(quán)：,每個(gè)點(diǎn)到匯的邊容量增加該點(diǎn)點(diǎn)權(quán)的兩倍,最后，保留原圖的邊，容量即為原邊權(quán)。,,,湊入最小割,,改進(jìn)算法解決,通過以上公式變形，可知答案為其中c[S,T]為最小割，證明從略,復(fù)雜度為,改進(jìn)算法對(duì)比,最大權(quán)閉合圖,改進(jìn)算法,點(diǎn)數(shù),n,邊數(shù),0.71s,40.41s,n+m,,,n+m,n+m,實(shí)際效果,,,改進(jìn)算法小結(jié)

12、,改進(jìn)動(dòng)機(jī)利用最小割的想法不斷的完善這個(gè)想法得出極為精妙的構(gòu)造,,,,兩次逆向思維,微觀的觀察,分別將邊權(quán)，點(diǎn)權(quán)因素湊入最小割,數(shù)學(xué)美,論文特點(diǎn),研究的重點(diǎn)是最小割模型的應(yīng)用不僅僅給出了結(jié)論，還著重闡述得出結(jié)論的分析過程。不僅授之以魚，還授之以漁。分析過程，是以Polya在數(shù)學(xué)思想方法論中的精華－－《怎樣解題表》作為貫串思維的主線。如剛才的構(gòu)造過程就充分的展示了這一特點(diǎn)。,論文研究?jī)?nèi)容,主要研究四個(gè)方面的應(yīng)用基

13、于最小割定義的直接應(yīng)用最大權(quán)閉合圖最大密度子圖二分圖的最小點(diǎn)權(quán)覆蓋集與最大點(diǎn)權(quán)獨(dú)立集,剛才所談的例題最大獲利便涉及了最大權(quán)閉合圖，最大密度子圖這兩個(gè)方面的內(nèi)容。其中改進(jìn)算法可以作為求解最大密度子圖的一個(gè)子過程。,論文研究?jī)?nèi)容,Sorry for poor time.,感謝,感謝越南的Thanh Vy感謝郭華陽提供原創(chuàng)題感謝王欣上的測(cè)試實(shí)驗(yàn)感謝CCF提供給我一個(gè)展示自我的舞臺(tái),謝謝大家Thanks to you all,

14、Amber[ADN.cn]hupo001@gmail.com,改進(jìn)算法證明,關(guān)于實(shí)現(xiàn)效率,本人實(shí)現(xiàn)的Preflow Push40.41s ? 0.71s王欣上提供的Dinic測(cè)試：1.7s ? 0.3s,總結(jié),轉(zhuǎn)化過程的模式 Transforming Pattern建立一一對(duì)應(yīng)關(guān)系割的性質(zhì) Property of Cut不存在任何一條s到t的路徑 將點(diǎn)集分成兩類 技巧用正無限的容量排除不參與決策的邊使用割的定

15、義式來分析最優(yōu)性利用與源或匯關(guān)聯(lián)的邊容量處理點(diǎn)權(quán),最大權(quán)閉合圖 － 證明,該通過對(duì)以上網(wǎng)絡(luò)的最小割的求解，可以得到原問題的解。概念：若一個(gè)割不包含正無限容量的邊，稱該割為簡(jiǎn)單割。最小割必是簡(jiǎn)單割。閉合圖V1與簡(jiǎn)單割[S, T]間有一一對(duì)應(yīng)關(guān)系,,因?yàn)樵诤?jiǎn)單割中，S到T間的邊都不是正無限容量的邊，即都不是原圖的邊。故一一對(duì)應(yīng)關(guān)系成立。,最大權(quán)閉合圖 － 證明,,,,由最小割的定義，有：,,,,,,,所以得到：,式(1),最大權(quán)閉合圖

16、 － 證明,又由閉合圖的定義，得到：,式(2),將式(1)與式(2)加起來，得到：,,總復(fù)雜度為,最大密度子圖 － 定義,定義一個(gè)無向圖的密度(density)為該圖的邊數(shù)與該圖的點(diǎn)數(shù)的比值 最大密度子圖是一個(gè)具有最大密度的子圖 由于目標(biāo)是求最大, 可以直接把子圖重定義為的子圖點(diǎn)集的導(dǎo)出子圖,,其中在虛線內(nèi)的點(diǎn)與邊組成最大密度子圖，密度為 5/4,最大密度子圖 － 主算法,這是0-1分?jǐn)?shù)規(guī)劃的模型 對(duì)答案值的二分查找，將分?jǐn)?shù)規(guī)劃

17、轉(zhuǎn)化為一般規(guī)劃對(duì)于一個(gè)答案的猜測(cè)值g，新函數(shù),,,,,形式化地重新敘述本模型,最大密度子圖 － 主算法,性質(zhì): 1. 具有單調(diào)性; 2.又根據(jù)Dinkelbach定理, 函數(shù)圖像與x軸的交點(diǎn), 即為目標(biāo)解.,對(duì)答案進(jìn)行二分查找. 設(shè)二分查找的次數(shù)為k, 則總復(fù)雜度為,最大密度子圖 － 初步算法,基本的限制條件: 邊(u, v)存在于子圖中的必要條件為點(diǎn)u, v也存在于子圖中. 根據(jù)這必要條件的關(guān)系, 想到使用最大權(quán)閉合圖的方法解

18、決. 依然是將邊看成點(diǎn)即可.,,復(fù)雜度為,需要改進(jìn)?。?！,最大密度子圖 － 改進(jìn)算法,,,,,×（－1）,×2,最大密度子圖 － 改進(jìn)算法,將上面的思路整理一下在原圖點(diǎn)集的基礎(chǔ)上增加源和匯；將每條原無向邊替換為兩條容量為1的有向邊；連接源s到每個(gè)點(diǎn)，容量為U；連接匯t到每個(gè)點(diǎn)，容量為U+2g-dv。U為一個(gè)足夠大的數(shù)。,,,,最大密度子圖 － 改進(jìn)算法,,改進(jìn)算法證明,,復(fù)雜度為,推廣1：改進(jìn)算法的點(diǎn)權(quán)和