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

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