平面圖最小割

平面圖最小割第一頁(yè)，共四十二頁(yè)，2022年，8月28日引入我們?cè)谛畔W(xué)競(jìng)賽中經(jīng)常會(huì)遇到一些涉及一個(gè)最大化問(wèn)題和一個(gè)最小化問(wèn)題的定理怎樣利用這些定理幫助我們解題呢？K?nig定理最大流—最小割定理第二頁(yè)，共四十二頁(yè)，2022年，8月28日K?nig定理主要內(nèi)容在任何一個(gè)二部圖G中，最大匹配數(shù)r(G)等于最小覆蓋數(shù)c(G)第三頁(yè)，共四十二頁(yè)，2022年，8月28日K?nig定理證明最大匹配數(shù)不超過(guò)最小覆蓋數(shù)任取一個(gè)最小覆蓋Q，一定可以構(gòu)造出一個(gè)與之大小相等的匹配Mr(G)≤c(G)r(G)=c(G)c(G)≤|Q|=|M|≤r

(G)c(G)≤r(G)第四頁(yè)，共四十二頁(yè)，2022年，8月28日K?nig定理應(yīng)用二部圖最小覆蓋和最大匹配的互相轉(zhuǎn)化[例一]MuddyFields第五頁(yè)，共四十二頁(yè)，2022年，8月28日最大流—最小割定理近年來(lái)，網(wǎng)絡(luò)流尤其是最大流問(wèn)題越來(lái)越多的出現(xiàn)在各類(lèi)信息學(xué)競(jìng)賽當(dāng)中最大流—最小割定理是整個(gè)最大流問(wèn)題的基礎(chǔ)與核心，其主要內(nèi)容是：最大流的流量不超過(guò)最小割的容量存在一個(gè)流x和一個(gè)割c，且x的流量等于c的容量第六頁(yè)，共四十二頁(yè)，2022年，8月28日[例二]

MovingtheHay一個(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)armerJohn希望將最多的干草運(yùn)送到(R,C)內(nèi)求最大運(yùn)輸量第七頁(yè)，共四十二頁(yè)，2022年，8月28日[例二]MovingtheHay一個(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)第八頁(yè)，共四十二頁(yè)，2022年，8月28日分析直接求最大流以每個(gè)方格為點(diǎn)，每條通道為邊，邊的容量就是它的最大運(yùn)輸量從(1,1)到(R,C)的最大運(yùn)輸量就是將這兩個(gè)方格對(duì)應(yīng)的點(diǎn)分別作為流網(wǎng)絡(luò)中的源和匯求出的最大流量效率？？？點(diǎn)數(shù)最大40000，邊數(shù)最大80000！TimeLimitExceeded!!!第九頁(yè)，共四十二頁(yè)，2022年，8月28日分析效率低下的原因沒(méi)有利用題目的特點(diǎn)，直接套用經(jīng)典算法特點(diǎn)題目中給出的是一個(gè)平面圖圖中的一個(gè)點(diǎn)為源點(diǎn)s，另外一個(gè)點(diǎn)為匯點(diǎn)t，且s和t都在圖中的無(wú)界面的邊界上第十頁(yè)，共四十二頁(yè)，2022年，8月28日分析452316f1f2f3f4第十一頁(yè)，共四十二頁(yè)，2022年，8月28日分析效率低下的原因沒(méi)有利用題目的特點(diǎn)，直接套用經(jīng)典算法特點(diǎn)題目中給出的是一個(gè)平面圖圖中的一個(gè)點(diǎn)為源點(diǎn)s，另外一個(gè)點(diǎn)為匯點(diǎn)t，且s和t都在圖中的無(wú)界面的邊界上我們稱這樣的平面圖為s-t平面圖第十二頁(yè)，共四十二頁(yè)，2022年，8月28日平面圖的性質(zhì)平面圖性質(zhì)（歐拉公式）如果一個(gè)連通的平面圖有n個(gè)點(diǎn)，m條邊和f個(gè)面，那么f=m-n+2每個(gè)平面圖G都有一個(gè)與其對(duì)偶的平面圖G*G*中的每個(gè)點(diǎn)對(duì)應(yīng)G中的一個(gè)面第十三頁(yè)，共四十二頁(yè)，2022年，8月28日對(duì)偶圖舉例4523161*2*3*4*第十四頁(yè)，共四十二頁(yè)，2022年，8月28日平面圖的性質(zhì)平面圖性質(zhì)（歐拉公式）如果一個(gè)連通的平面圖有n個(gè)點(diǎn)，m條邊和f個(gè)面，那么f=m-n+2每個(gè)平面圖G都有一個(gè)與其對(duì)偶的平面圖G*G*中的每個(gè)點(diǎn)對(duì)應(yīng)G中的一個(gè)面對(duì)于G中的每條邊ee屬于兩個(gè)面f1、f2，加入邊(f1*，f2*)第十五頁(yè)，共四十二頁(yè)，2022年，8月28日對(duì)偶圖舉例4523161*2*3*4*第十六頁(yè)，共四十二頁(yè)，2022年，8月28日平面圖的性質(zhì)平面圖性質(zhì)（歐拉公式）如果一個(gè)連通的平面圖有n個(gè)點(diǎn)，m條邊和f個(gè)面，那么f=m-n+2每個(gè)平面圖G都有一個(gè)與其對(duì)偶的平面圖G*G*中的每個(gè)點(diǎn)對(duì)應(yīng)G中的一個(gè)面對(duì)于G中的每條邊ee屬于兩個(gè)面f1、f2，加入邊(f1*，f2*)e只屬于一個(gè)面f，加入回邊(f*，f*)第十七頁(yè)，共四十二頁(yè)，2022年，8月28日對(duì)偶圖舉例4523161*2*3*4*第十八頁(yè)，共四十二頁(yè)，2022年，8月28日平面圖與其對(duì)偶圖的關(guān)系平面圖G與其對(duì)偶圖G*之間存在怎樣的關(guān)系呢？G的面數(shù)等于G*的點(diǎn)數(shù)，G*的點(diǎn)數(shù)等于G的面數(shù)，G與G*邊數(shù)相同G*中的環(huán)對(duì)應(yīng)G中的割一一對(duì)應(yīng)4523161*2*3*4*第十九頁(yè)，共四十二頁(yè)，2022年，8月28日s-t平面圖上最大流的快速求法如何利用這些性質(zhì)？直接求解仍然困難利用最大流—最小割定理轉(zhuǎn)化模型根據(jù)平面圖與其對(duì)偶圖的關(guān)系，想辦法求出最小割第二十頁(yè)，共四十二頁(yè)，2022年，8月28日利用最短路求最小割對(duì)于一個(gè)s-t平面圖，我們對(duì)其進(jìn)行如下改造：連接s和t，得到一個(gè)附加面對(duì)于一個(gè)s-t平面圖，我們對(duì)其進(jìn)行如下改造：求該圖的對(duì)偶圖G*，令附加面對(duì)應(yīng)的點(diǎn)為s*，無(wú)界面對(duì)應(yīng)的點(diǎn)為t*對(duì)于一個(gè)s-t平面圖，我們對(duì)其進(jìn)行如下改造：刪去s*和t*之間的邊123456781*3*2*4*5*7*6*8*sts*t*第二十一頁(yè)，共四十二頁(yè)，2022年，8月28日利用最短路求最小割一條從s*到t*的路徑，就對(duì)應(yīng)了一個(gè)s-t割！更進(jìn)一步，如果我們令每條邊的長(zhǎng)度等于它的容量，那么最小割的容量就等于最短路的長(zhǎng)度！分析一下時(shí)間復(fù)雜度新圖中的點(diǎn)數(shù)和邊數(shù)都是O(n)的使用二叉堆優(yōu)化的Dijkstra算法求最短路，時(shí)間復(fù)雜度為O(nlog2n)123456781*3*2*4*5*7*6*8*sts*t*第二十二頁(yè)，共四十二頁(yè)，2022年，8月28日利用最短路求最大流我們可以利用最短路算法得到的距離標(biāo)號(hào)構(gòu)造一個(gè)最大流[定理2.1]可以在O(nlog2n)的時(shí)間內(nèi)求出s-t平面圖上的最大流。第二十三頁(yè)，共四十二頁(yè)，2022年，8月28日小結(jié)回顧得到簡(jiǎn)單的最大流模型利用最大流—最小割定理進(jìn)行模型轉(zhuǎn)化根據(jù)平面圖的性質(zhì)解決最小割問(wèn)題構(gòu)造得到最大流第二十四頁(yè)，共四十二頁(yè)，2022年，8月28日最大—最小定理對(duì)比以上兩個(gè)定理[定義3.1]最大—最小定理是一類(lèi)描述同一個(gè)對(duì)象上的一個(gè)最大化問(wèn)題的解和一個(gè)最小化問(wèn)題的解之間的關(guān)系的定理。第二十五頁(yè)，共四十二頁(yè)，2022年，8月28日最大—最小定理共同點(diǎn)考察的兩個(gè)最優(yōu)化問(wèn)題互為對(duì)偶問(wèn)題證明的過(guò)程最大化問(wèn)題M的任何一個(gè)解m的值都不超過(guò)最小化問(wèn)題N的任何一個(gè)解n的值可以找到M的一個(gè)解p和N的一個(gè)解q，且它們的值相等p和q分別為各自問(wèn)題的一個(gè)最優(yōu)解簡(jiǎn)潔的最優(yōu)性證明第二十六頁(yè)，共四十二頁(yè)，2022年，8月28日總結(jié)K?nig定理最大流—最小割定理最大—最小定理最大匹配最小覆蓋最大流最小割模型轉(zhuǎn)化最大最小完全矛盾互相轉(zhuǎn)化注意總結(jié)、積累勇于探索第二十七頁(yè)，共四十二頁(yè)，2022年，8月28日參考文獻(xiàn)IntroductiontoGraphTheory,SecondEditionbyDouglasB.WestNetworkFlows:Theory,AlgorithmsandApplicationsbyRavindraK.Ahuja,ThomasL.Magnanti,andJamesB.OrlinIntroductoryCombinatorics,ThirdEditionbyRichardA.Brualdi運(yùn)籌學(xué)教程（第三版）胡運(yùn)權(quán)郭耀煌第二十八頁(yè)，共四十二頁(yè)，2022年，8月28日謝謝大家，歡迎提問(wèn)！第二十九頁(yè)，共四十二頁(yè)，2022年，8月28日更多的例子二部圖中最大獨(dú)立集的大小等于最小邊覆蓋數(shù)頂點(diǎn)的最大度數(shù)等于最小邊染色數(shù)3正則圖中點(diǎn)聯(lián)通度等于邊聯(lián)通度……第三十頁(yè)，共四十二頁(yè)，2022年，8月28日如何構(gòu)造最大流？我們用d(j*)表示新圖中s*到j(luò)*的最短路的長(zhǎng)度對(duì)于每條邊(i*,j*)，d(j*)≤d(i*)+ci*j*G中的每條邊(i,j)，設(shè)G*與其對(duì)應(yīng)的邊為(i*,j*)，定義流量xij=d(j*)-d(i*)反對(duì)稱性：xij=-xji容量限制：xij=d(j*)-d(i*)≤ci*j*第三十一頁(yè)，共四十二頁(yè)，2022年，8月28日如何構(gòu)造最大流？對(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滿足流量平衡第三十二頁(yè)，共四十二頁(yè)，2022年，8月28日如何構(gòu)造最大流？設(shè)P*是G*中從s*到t*的一條最短路對(duì)于任意的(i*,j*)∈P*，都有d(j*)-d(i*)=ci*j*P*中的邊構(gòu)成了原圖中的一個(gè)s-t割Q。根據(jù)上式和ci*j*=uij可得對(duì)于任意的(i,j)∈Q，都有xij=uij。x的流量等于Q的容量x是最大流，Q是最小割第三十三頁(yè)，共四十二頁(yè)，2022年，8月28日復(fù)雜度問(wèn)題只考慮題目中給出的邊需要通過(guò)寬搜得到所有的面，且需要處理面與面之間的關(guān)系思維復(fù)雜度與編程復(fù)雜度均比較高可以認(rèn)為原來(lái)不存在的邊容量為0不影響答案面與面之間的關(guān)系清晰明了大大降低思維和編程復(fù)雜度第三十四頁(yè)，共四十二頁(yè)，2022年，8月28日最大最小定理和線性規(guī)劃線性規(guī)劃定義:在滿足一些線性等式或者不等式的條件下，最優(yōu)化一個(gè)線性函數(shù)標(biāo)準(zhǔn)形式：整數(shù)線性規(guī)劃第三十五頁(yè)，共四十二頁(yè)，2022年，8月28日最大最小定理和線性規(guī)劃對(duì)偶問(wèn)題第三十六頁(yè)，共四十二頁(yè)，2022年，8月28日最大最小定理和線性規(guī)劃基本性質(zhì)弱對(duì)偶性如果x是原問(wèn)題的可行解，y是其對(duì)偶問(wèn)題的可行解，則恒有c*x≤

b*y最優(yōu)性如果x是原問(wèn)題的可行解，y是其對(duì)偶問(wèn)題的可行解，且有c*x=

b*y，則x和y是各自問(wèn)題的最優(yōu)解強(qiáng)最優(yōu)性（對(duì)偶定理）如果原問(wèn)題及其對(duì)偶問(wèn)題均有可行解，則兩者均有最優(yōu)解，且最優(yōu)解的目標(biāo)函數(shù)值相同第三十七頁(yè)，共四十二頁(yè)，2022年，8月28日最大最小定理和線性規(guī)劃二部圖最大匹配每個(gè)變量x對(duì)應(yīng)一條邊對(duì)于每個(gè)頂點(diǎn)v，S(v)表示所有與v關(guān)聯(lián)的邊的集合第三十八頁(yè)，共四十二頁(yè)，2022年，8月28日最大最小定理和線性規(guī)劃二部圖最小覆蓋每個(gè)變量y