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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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