圖和網(wǎng)絡(luò)問題

圖和網(wǎng)絡(luò)問題第1頁，共47頁，2023年，2月20日，星期五1.圖的遍歷圖的深度優(yōu)先遍歷一般用棧結(jié)構(gòu)支持圖的廣度有限遍歷一般用隊列結(jié)構(gòu)支持圖的深度優(yōu)先遍歷和廣度優(yōu)先遍歷都可以產(chǎn)生一棵聲稱樹去掉連通無向圖的接合點后，該無向圖不再連通第2頁，共47頁，2023年，2月20日，星期五2.網(wǎng)絡(luò)流量2.1網(wǎng)絡(luò)流量的基本概念和性質(zhì)2.2Ford_Fulkerson法最大容量擴(kuò)張2.3最短路徑法容量擴(kuò)張2.4網(wǎng)絡(luò)最大流舉例第3頁，共47頁，2023年，2月20日，星期五2.1網(wǎng)絡(luò)流量的基本概念和性質(zhì)2.1.1網(wǎng)絡(luò)的四元組表示2.1.2容量函數(shù)和流量函數(shù)2.1.3流量函數(shù)約束條件2.1.4割集2.1.5割集的性質(zhì)2.1.6流量的剩余容量和剩余圖2.1.7瓶頸容量2.1.8最大流量最小割定理第4頁，共47頁，2023年，2月20日，星期五2.1.1網(wǎng)絡(luò)的四元組表示(G,s,t,c)G=(V,E)是一個有向圖圖中有兩個不同的頂點：源點s和收點tc(u,v)是頂點對(u,v)的容量函數(shù)常見問題：尋找從s到t的最大流量sabdcet6/84/65/52/23/54/65/52/22/2第5頁，共47頁，2023年，2月20日，星期五2.1.2容量函數(shù)在網(wǎng)絡(luò)(G,s,t,c)中，如果u、v是V中的任意頂點，則容量函數(shù)c(u,v)表示流經(jīng)u、v的最大允許流量若邊(u,v)E，則表示u到v的容量c(u,v)>0；否則,c(u,v)=0也就是說對任意點對(u,v)，c(u,v)0流量函數(shù)f(u,v)是一個點對到實數(shù)的映射，它不是任意的，它必須滿足流量約束條件sabdcet865256522第6頁，共47頁，2023年，2月20日，星期五2.1.3流量函數(shù)約束條件反對稱。對任意u,vV，有f(u,v)=-f(v,u)。如果f(u,v)>0，就稱f(u,v)是u到v的流量容量約束。對任意u,vV，有f(u,v)c(u,v)。如果f(u,v)=c(u,v)，則稱邊(u,v)是飽和的流量守恒。對任意uV-{s,t}，有vf(u,v)=0對任意vV，有f(v,v)=0sabdcet6/84/65/52/23/54/65/52/22/2第7頁，共47頁，2023年，2月20日，星期五2.1.4割集割集{S,T}是一個劃分，它把頂點V劃分成兩個子集S和T，使得sS，tT。如果用c(S,T)表示割集{S,T}的容量，則有用f(S,T)表示割集{S,T}的交叉流量f(S,T)表示S到T的所有正流量之和，減去T到S的所有正流量之和第8頁，共47頁，2023年，2月20日，星期五2.1.5割集的性質(zhì)如果f是G的一個流量，定義f的值|f|為：流量有這樣的性質(zhì)：如果f是G中的一個流量，{S,T}是G中的任意一個割集，則|f|=f(S,T)sabdcet6/84/65/52/23/54/65/52/22/2第9頁，共47頁，2023年，2月20日，星期五2.1.6流量的剩余容量和剩余圖流量f的剩余容量函數(shù)r定義為：對任意u,vV，r(u,v)=c(u,v)–f(u,v)流量f的剩余圖是一個有向圖R=(V,Ef)。其中，V是原圖的頂點集合，Ef={(u,v)|r(u,v)>0}容易觀察出：如果f(u,v)<c(u,v)，那么Ef中包含邊(u,v)和(v,u)；如果原圖u和v之間沒有邊，那么邊(u,v)和(v,u)都不在Ef中sabdcet6/84/65/52/23/54/65/52/22/2sabdcet2522262424523第10頁，共47頁，2023年，2月20日，星期五2.1.7瓶頸容量如果f是G中的一個流量，f的剩余圖R中，由s到t的有向路徑p稱為流量f的擴(kuò)張路徑。沿著擴(kuò)張路徑p的所有的階段剩余流量中的最小值稱為p的瓶頸容量如果把流量f沿著擴(kuò)張路徑p再壓入瓶頸容量的流量，則這條路徑上的流量飽和sabdcet6/84/65/52/23/54/65/52/22/2sabdcet2522262424523第11頁，共47頁，2023年，2月20日，星期五2.1.8最大流量最小割定理網(wǎng)絡(luò)(G,s,t,c)中，如果f是一個流量，那么下面的三個命題等價：存在一個容量為c(S,T)=|f|的割集{S,T}f是G中的最大流量不存在f的擴(kuò)張路徑最大流量最小割定理提供了尋找最大流量的一種方法：循環(huán)地尋找一條擴(kuò)張路徑，然后在擴(kuò)張路徑上的壓入瓶頸容量的流量，可以使得流量增大；這個過程持續(xù)至不能再找到擴(kuò)張路徑為止。但Ford_Fulkerson方法是每一次都尋找最大擴(kuò)張路徑第12頁，共47頁，2023年，2月20日，星期五2.2Ford_Fulkerson法最大容量擴(kuò)張sabdct8463546sabdct0/80/40/60/30/50/40/6sabdct84635460000000當(dāng)前容量/路徑容量：s當(dāng)前容量/路徑容量：8sa當(dāng)前容量/路徑容量：4sab000當(dāng)前容量/路徑容量：4sab4t當(dāng)前容量/路徑容量：4sab4當(dāng)前容量/路徑容量：8sa4當(dāng)前容量/路徑容量：3sac4當(dāng)前容量/路徑容量：3sac4t第13頁，共47頁，2023年，2月20日，星期五當(dāng)前容量/路徑容量：3sac4t當(dāng)前容量/路徑容量：3sac4當(dāng)前容量/路徑容量：8sa4當(dāng)前容量/路徑容量：s4sabdct8463546sabdct0/80/40/60/30/50/40/6sabdct8463546當(dāng)前容量/路徑容量：6s4d當(dāng)前容量/路徑容量：6s6dt當(dāng)前容量/路徑容量：6s6d當(dāng)前容量/路徑容量：6s6當(dāng)前容量/路徑容量：6結(jié)束6第14頁，共47頁，2023年，2月20日，星期五Ford_Fulkerson法分為若干相似的步驟，每一步都需要尋找一條具有最大瓶頸容量的剩余圖的路徑Ford_fulkerson法的步驟數(shù)量不會超過總的邊數(shù)。這是因為，每一次查找最大瓶頸容量的剩余圖時，會使得一條或多條邊從不飽和到飽和狀態(tài)。所以，步驟總數(shù)不會超過總邊數(shù)每個步驟需要用深度優(yōu)先完成最大瓶頸容量路徑的搜索，可以用回溯的方式或分支限界的方式搜索最優(yōu)路徑。第15頁，共47頁，2023年，2月20日，星期五2.3最短路徑法容量擴(kuò)張sabdct8463546s/0a/1b/2d/1c/2t/28463546t與s的最短距離是2，并不是3第16頁，共47頁，2023年，2月20日，星期五利用最短路徑法容量擴(kuò)張求解最大容量的問題時，算法比較簡單，也分為若干步（步驟總數(shù)也不會超過原圖的邊的總數(shù)）要利用Dijkstra算法發(fā)現(xiàn)從s到t的具有剩余容量的一條最短路徑（路徑長度的定義是路徑上邊的條數(shù)）對找到的最短路徑進(jìn)行容量擴(kuò)張依次重復(fù)上面的步驟，直至不能發(fā)現(xiàn)可擴(kuò)張路徑為止第17頁，共47頁，2023年，2月20日，星期五2.4網(wǎng)絡(luò)最大流舉例動物們成功出逃動物園，它們要從下圖左上角動物園出發(fā)，向著右下角它們的樂園進(jìn)發(fā)。每段道路都有容量，為了攔截動物，要在道路上布置與道路容量一致的警力。問：最少需要多少警力？下圖網(wǎng)格可達(dá)到200*200的規(guī)模第18頁，共47頁，2023年，2月20日，星期五最大流，最小割第19頁，共47頁，2023年，2月20日，星期五最短路徑三者統(tǒng)一第20頁，共47頁，2023年，2月20日，星期五3.二分圖3.1引例3.2二分圖相關(guān)定義和性質(zhì)3.3二分圖最大匹配的最大流方法3.4二分圖最大匹配的線性規(guī)劃方法3.5二分圖最大匹配的匈牙利樹方法3.6二分圖最大匹配應(yīng)用舉例第21頁，共47頁，2023年，2月20日，星期五3.1引例(紅娘問題)x1x2x3x4x5y1y2y3y4y5第22頁，共47頁，2023年，2月20日，星期五3.2二分圖相關(guān)定義和性質(zhì)3.2.1匹配和最大匹配3.2.2匹配點和自由點3.2.3交替回路和擴(kuò)張路徑3.2.4無向圖匹配的擴(kuò)張路徑定理3.2.5二分圖3.2.6可增廣鏈第23頁，共47頁，2023年，2月20日，星期五3.2.1匹配和最大匹配如果G=(V,E)是一個（普通的）無向圖，如果存在邊集ME，使得M中所有的邊都沒有公共頂點，則稱M是G的一個匹配M的邊數(shù)記為|M|邊數(shù)最多的匹配稱為最大匹配abcdabcd第24頁，共47頁，2023年，2月20日，星期五3.2.2匹配點和自由點如果M是G的一個匹配，邊e既屬于E也屬于M，則稱e是匹配的如果頂點vV，且存在一條匹配邊與v關(guān)聯(lián)，則稱頂點v是被許配的；否則，稱v是自由的abcde第25頁，共47頁，2023年，2月20日，星期五3.2.3交替回路和擴(kuò)張路徑設(shè)M是G的一個匹配。若G中存在一條路徑p，p是由匹配邊和非匹配邊交替構(gòu)成的，則稱p為交替路徑，其長度用|p|表示如果交替路徑p的兩個端點重合，則稱p為交替回路如果交替路徑p的兩個端點都是自由的，則稱p為M的擴(kuò)張路徑（或者稱為可增廣鏈）下圖中e->d->b->f就是M的一條擴(kuò)張路徑abcdef第26頁，共47頁，2023年，2月20日，星期五3.2.4無向圖匹配的擴(kuò)張路徑定理abcdef設(shè)M是G的一個匹配。若P是M的一條擴(kuò)張路徑，則把P的路徑上所有邊的匹配性質(zhì)翻轉(zhuǎn)，可以得到另一個匹配M，并且有|M|=|M|+1無向圖G的匹配是最大匹配，當(dāng)且僅當(dāng)G不包含M的擴(kuò)張路徑abcdef第27頁，共47頁，2023年，2月20日，星期五3.2.5二分圖如果無向圖G=(V,E)的頂點集V可以分為兩個子集X和Y，滿足XY=，XY=V，G的任何一條邊的兩個端點，一個在X中，另一個在Y中，則稱圖G是二分圖，二部圖，或偶圖定理：圖G是二分圖，當(dāng)且僅當(dāng)G中沒有奇數(shù)長度的回路x1x2x3x4x5y1y2y3y4y5第28頁，共47頁，2023年，2月20日，星期五3.2.6可增廣鏈解決引例問題二分圖的可擴(kuò)張路徑又稱為二分圖的可增廣鏈。利用可增廣鏈可以快速實現(xiàn)二分圖的最大匹配利用可增廣鏈求二分圖最大匹配的思路是：從空的匹配開始，循環(huán)地發(fā)現(xiàn)可增增廣鏈并翻轉(zhuǎn)該可增廣鏈第29頁，共47頁，2023年，2月20日，星期五x1x2x3x4x5y1y2y3y4y5x1x2x3x4x5y1y2y3y4y5第30頁，共47頁，2023年，2月20日，星期五x1x2x3x4x5y1y2y3y4y5x1x2x3x4x5y1y2y3y4y5第31頁，共47頁，2023年，2月20日，星期五x1x2x3x4x5y1y2y3y4y5x1x2x3x4x5y1y2y3y4y5第32頁，共47頁，2023年，2月20日，星期五x1x2x3x4x5y1y2y3y4y5x1x2x3x4x5y1y2y3y4y5第33頁，共47頁，2023年，2月20日，星期五3.3二分圖最大匹配的最大流方法x1x2x3x4x5y1y2y3y4y5第34頁，共47頁，2023年，2月20日，星期五3.4二分圖最大匹配的線性規(guī)劃方法x1x2y1y2y3y412345x1最多被許配一次x2的約束y1的約束y2的約束y3的約束y4的約束第35頁，共47頁，2023年，2月20日，星期五3.5二分圖最大匹配的匈牙利樹方法3.5.1交替路徑樹3.5.2在二分圖中發(fā)現(xiàn)交替路徑樹3.5.3匈牙利樹3.5.4利用匈牙利樹求解二分圖的最大匹配第36頁，共47頁，2023年，2月20日，星期五3.5.1交替路徑樹x1x2x3x4x5y1y2y3y4y5x1y2y3x2x3y1y4y5二分圖中的交替路徑樹以一個自由節(jié)點作為根。根到葉子節(jié)點的路徑上，不匹配與匹配的連線交替出現(xiàn)。每個節(jié)點的下面包含所有可能的子節(jié)點第37頁，共47頁，2023年，2月20日，星期五3.5.2在二分圖中發(fā)現(xiàn)交替路徑樹x1x2x3x4x5y1y2y3y4y5x1y2y3x2x3y1y4y5用廣度優(yōu)先遍歷的方式發(fā)現(xiàn)交替路徑樹某個節(jié)點在交替路徑樹中出現(xiàn)之后，便不再出現(xiàn)第38頁，共47頁，2023年，2月20日，星期五3.5.3匈牙利樹x1x2x3x4x5y1y2y3y4y5x4y2y3x1x3如果最終構(gòu)造的交替路徑樹的葉子節(jié)點全部是已許配了的節(jié)點，則這棵樹就是匈牙利樹出現(xiàn)匈牙利樹就意味著通過這些節(jié)點和邊不可能提高匹配的數(shù)量第39頁，共47頁，2023年，2月20日，星期五3.5.4利用匈牙利樹求解二分圖的最大匹配初始匹配為空，匹配數(shù)設(shè)為0。轉(zhuǎn)入下步。如果節(jié)點集為空，則轉(zhuǎn)入5)；否則轉(zhuǎn)入下步。用廣度優(yōu)先遍歷法求得一棵交替路徑樹。轉(zhuǎn)入下步。如果交替路徑樹是匈牙利樹，則匹配數(shù)增加該匈牙利樹中的匹配數(shù)，并在圖中刪除該樹轉(zhuǎn)入步驟2)；否則，翻轉(zhuǎn)交替路徑樹上的由根到葉子的最長路徑，轉(zhuǎn)入步驟2）。返回并退出匹配總數(shù)。第40頁，共47頁，2023年，2月20日，星期五3.6二分圖最大匹配應(yīng)用舉例3.6.1同聲傳譯問題3.6.2狗和主人問題3.6.3投籃問題第41頁，共47頁，2023年，2月20日，星期五3.6.1同聲傳譯問題某機構(gòu)需要6種語言的同聲傳譯，翻譯人員共5名，他們能進(jìn)行同聲傳譯工作的語言情況如圖所示。問：最多能有幾門語言能被同時進(jìn)行同聲傳譯？第4