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

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

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

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

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

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

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

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)閉合圖來解決二分圖模型。（特殊性）,牛刀宰雞,對癥下藥,改進(jìn)算法提出,必要條件,邊,,依賴,點,充分條件,邊,,創(chuàng)建,點,正向思維（被動）,逆向思維（主動）,重

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

9、構(gòu)圖從源向每個點連邊從每個點向匯連邊,1,2,s,t,,,,,,,,V’,對于每個點，割必會割斷它到源或它到匯的兩條邊中的一條不妨設(shè)，到匯的邊被割斷的點組成V’則V’中每個點連接匯的邊都在割內(nèi)選入V'的點的一些代價信息，可以加載到這條被割掉的邊上。,,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,,湊入最小割,微觀地，考察單獨的在V’中點v與v關(guān)聯(lián)所有E’內(nèi)的邊 = －（與v關(guān)聯(lián)所有割邊－與v關(guān)聯(lián)所有邊）,令 表示與點v關(guān)聯(lián)的總邊權(quán)和,v,s,t,,,每個點到匯的邊容量為,V’間的邊E’＋ V’的點權(quán)＝ － (V’與V’補(bǔ)集之間的邊－與V’關(guān)聯(lián)的所有邊－V’的點權(quán)),V’間的邊E’ ＝ － (V’與V’補(bǔ)集之間的邊－與V’關(guān)聯(lián)的所有邊),由于最小割算法只能處理非負(fù)邊權(quán)，故在每條邊的

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

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

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

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

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

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

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

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