圖論方法建模2

1、2021-11-16第十二講 圖與網(wǎng)絡(luò)建模方法圖與網(wǎng)絡(luò)建模方法漳州師范學(xué)院數(shù)學(xué)建模課件2021-11-16 主要內(nèi)容 匹配問題 旅行商問題 最小生成樹問題 最大流問題 最小費用最大流問題2021-11-16 三、最小生成樹問題Kruskal算法構(gòu)造最小生成樹2021-11-16 三、最小生成樹問題調(diào)用leasttree_2.m的m函數(shù)文件。命令形式： leasttree_2(a)功能：a是權(quán)矩陣，該矩陣中的主對角全部是0,并且不包含重復(fù)的權(quán)；返回樹的節(jié)點和權(quán)值。2021-11-16 三、最小生成樹問題 例12 用Kruskal算法求右圖的最小生成樹。 a(1,2)=50; a(1,3)=60;

2、a(2,4)=65; a(2,5)=40;a(3,4)=52;a(3,7)=45;a(4,5)=50; a(4,6)=30;a(4,7)=42;a(5,6)=70; leasttree_2(a)2021-11-16 三、最小生成樹問題調(diào)用mintreek.m的m函數(shù)文件。命令形式： a,b=mintreek (n,w)功能：w是權(quán)矩陣，該矩陣中的主對角全部是inf；n是頂點數(shù)；a返回最小生成樹的權(quán)的總長度,b是返回其具體的節(jié)點。并最終返回最小生成樹的圖形。2021-11-16 三、最小生成樹問題 例13 用Kruskal算法求右圖的最小生成樹。 M=Inf;a1=M,50,60,M,M,M,M

3、;a2=50,M,M,65,40,M,M;a3=60,M,M,52,M,M,45;a4=M,65,52,M,50,30,42;a5=M,40,M,50,M,70,M;a6=M,M,M,30,70,M,M;a7=M,M,45,42,M,M,M;w=a1;a2;a3;a4;a5;a6;a7n=7;a,b=mintreek(n,w)2021-11-16 三、最小生成樹問題調(diào)用kruskal.m的m函數(shù)文件。命令形式： out,len=kruskal (map)功能：map是輸入矩陣，map=起點1 終點1 邊長1;起點2 終點2 邊長2;.;起點n 終點n 邊長nout輸出邊陣:起點 終點;len輸

4、出最小生成樹的總長度;并最終返回最小生成樹的圖形。2021-11-16 三、最小生成樹問題 例14 用Kruskal算法求右圖的最小生成樹。 a1=1 2 50;1 3 60;a2=2 4 65;2 5 40;a3=3 4 52;3 7 45;a4=4 5 50;4 6 30;4 7 42;a5=5 6 70;map=a1;a2;a3;a4;a5out,len=kruskal(map)2021-11-16 三、最小生成樹問題 例15 用Kruskal算法求右圖的最小生成樹。 a1=1 2 50;1 3 60;a2=2 4 65;2 5 40;a3=3 4 52;3 7 45;a4=4 5 50

5、;4 6 30;4 7 42;a5=5 6 70;map=a1;a2;a3;a4;a5out,len=kruskal(map)2021-11-16 四、匹配問題例 指派問題 圖的匹配2021-11-16這個問題可以用圖的語言描述。其中 表示工人, 表示工作，邊 表示第i個人能勝任第j項工作，這樣就得到了一個二部圖G，用點集X表示 ，點集Y表示 ,二部圖G=(X,Y,E)。上述的工作分配問題就是要在圖G中找一個邊集E的子集，使得集中任何兩條邊沒有公共端點，最好的方案就是要使此邊集的邊數(shù)盡可能多，這就是匹配問題。 四、匹配問題nxxx,21nxxx,21nyyy,21),(jiyxnxxx,21n

6、yyy,212021-11-16二分圖的概念 二分圖又稱作二部圖，是圖論中的一種特殊模型。 設(shè)G=(V,R)是一個無向圖。如頂點集V可分割為兩個互不相交的子集，并且圖中每條邊依附的兩個頂點都分屬兩個不同的子集。則稱圖G為二分圖。112233445 四、匹配問題2021-11-16最大匹配 給定一個二分圖G，在G的一個子圖M中，M的邊集E中的任意兩條邊都不依附于同一個頂點，則稱M是一個匹配。 選擇這樣的邊數(shù)最大的子集稱為圖的最最大匹配問題大匹配問題。 如果一個匹配中，圖中的每個頂點都和圖中某條邊相關(guān)聯(lián)，則稱此匹配為完全完全匹配匹配，也稱作完備匹配。完備匹配。 四、匹配問題2021-11-16匈牙

7、利算法 求最大匹配的一種顯而易見的算法是：先找出全部匹配，然后保留匹配數(shù)最多的。但是這個算法的復(fù)雜度為邊數(shù)的指數(shù)級函數(shù)。 M中任意一條邊的端點v稱為（關(guān)于M的）飽和點，G中其他定點稱為非飽和點。 若P是圖G中一條連通兩個未匹配頂點的路徑，并且屬M的邊和不屬M的邊(即已匹配和待匹配的邊)在P上交替出現(xiàn)，則稱P為相對于M的一條增廣路徑。 四、匹配問題2021-11-16 結(jié)論： P的路徑長度必定為奇數(shù)，第一條邊和最后一條邊都不屬于M。 M為G的最大匹配當且僅當不存在相對于M的增廣路徑。 四、匹配問題2021-11-16）轉(zhuǎn)（置中有一邊飽和點，故是由于轉(zhuǎn)置可擴路的到求一條從）；否則作：飽和點轉(zhuǎn)（為若

8、擇一點則停止；否則，任意選）若（置非飽和點中尋找一個）在（）；否則轉(zhuǎn)（中的每一個頂點，結(jié)束飽和）若（中的一個初始匹配）任意?。ɑ静襟E：4,)6()2(),(,6)5(;)(,)(4;,3321yBBuSSyuMMyPEMMPMyxMyBSNyBSNBxSxMXXMMG 四、匹配問題2021-11-16例1 求二部圖G中的最大匹配。X1Y1Y2Y3Y4X2X3X4 四、匹配問題2021-11-16 M x S B N(s)Px2y2,x3y3 x1x1y2y2飽和點y2x2x1,x2y2y1,y2,y4y1非飽和點x1y2x2y1x1y2,x2,y1,x3y3x4x4y2,y3y2飽和y2x1

9、x4,x1y2y2,y3y3飽和y3x3x4,x1,x3y2,y3y2,y3N(s)=B結(jié)束BSNy)(Myu 四、匹配問題2021-11-16 最大匹配就是：X1Y1Y2Y3Y4X2X3X4 四、匹配問題2021-11-16 四、匹配問題調(diào)用pipei.m的m函數(shù)文件。格式：e,total=pipei(d)功能：d是二部圖矩陣(0-1矩陣)。e輸出匹配的路徑；total最大匹配的邊數(shù)。=wi,j成立(wi,j表示邊的權(quán))，且對所有的邊(i,j) in M,都有l(wèi)xi+lyj=wi,j成立，則M是圖G的一個最佳匹配。 四、匹配問題2021-11-16KM算法 對于任意的G和M，可行頂標都是存在

10、的： l(x) = maxw(x,y) l(y) = 0 欲求完全二分圖的最佳匹配，只要用匈牙利算法求其相等子圖的完備匹配；問題是當標號之后的Gl無完備匹配時怎么辦？1957年，Kuhn和Munkras給出了一個解決該問題的有效算法，用逐次修改可行頂標l(v)的辦法使對應(yīng)的相等子圖之最大匹配逐次增廣，最后出現(xiàn)完備匹配。 四、匹配問題2021-11-16 四、匹配問題例2 考慮完全的2部圖，其中 ， 。邊上的權(quán)如下矩陣。,521xxxX,521yyyY3312100110014422202214553W0)()(3)(, 1)(, 4)(, 2)(, 5)(5154321ylylxlxlxlxl

11、xl2021-11-16 修改方法如下： 先將一個未被匹配的頂點u(u in x)做一次增廣路，記下哪些結(jié)點被訪問那些結(jié)點沒有被訪問。求出d=minlxi+lyj-wi,j其中i結(jié)點被訪問，j結(jié)點沒有被訪問。然后調(diào)整lx和ly：對于訪問過的x頂點，將它的可行標減去d，對于所有訪問過的y頂點，將它的可行標增加d。修改后的頂標仍是可行頂標，原來的匹配M仍然存在，相等子圖中至少出現(xiàn)了一條不屬于M的邊，所以造成M的逐漸增廣。 四、匹配問題2021-11-16KM算法步驟 KuhnMunkras算法流程： (1)初始化可行頂標的值 (2)用匈牙利算法尋找完備匹配 (3)若未找到完備匹配則修改可行頂標的值

12、 (4)重復(fù)(2)(3)直到找到相等子圖的完備匹配為止 四、匹配問題2021-11-16 四、匹配問題調(diào)用km.m的m函數(shù)文件。命令形式： M,MaxZjpp=km(A,n)功能：A是輸入二部圖的權(quán)矩陣，n是匹配點。M輸出匹配矩陣;MaxZjpp輸出最優(yōu)匹配的總長度。A=3 5 5 4 1;2 2 0 2 2;2 4 4 1 0;0 1 1 0 0;1 2 1 3 3; M,MaxZjpp=km(A,5)2021-11-16 五、旅行商問題Euler圖和Hamilton圖2021-11-16 五、旅行商問題Euler圖和Hamilton圖2021-11-16 五、旅行商問題例5 旅行商問題 網(wǎng)

13、絡(luò)流2021-11-16 五、旅行商問題2021-11-16 五、旅行商問題調(diào)用tsp.m的m函數(shù)文件。命令形式： circle,sum=tsp(a,c1,c2)功能：a是輸入的權(quán)矩陣，c1是開始的圈,c2是改變的圈。circle輸出經(jīng)過的點;sum輸出最優(yōu)的總長度。2021-11-16 五、旅行商問題2021-11-16 五、旅行商問題a(1,2)=56;a(1,3)=35;a(1,4)=21;a(1,5)=51;a(1,6)=60;a(2,3)=21;a(2,4)=57;a(2,5)=78;a(2,6)=70;a(3,4)=36;a(3,5)=68;a(3,6)=68;a(4,5)=51;

14、a(4,6)=61;a(5,6)=13;a(6,:)=0;a=a+a;c1=5 1:4 6;c2=5 6 1:4;circle,sum=tsp(a,c1,c2)2021-11-16 六、最大流問題網(wǎng)絡(luò)中的流 2021-11-16 六、最大流問題例如 2021-11-16 六、最大流問題網(wǎng)絡(luò)中的流 2021-11-16 六、最大流問題網(wǎng)絡(luò)中的流 2021-11-16 六、最大流問題最大流 2021-11-16 六、最大流問題最大流的標號算法調(diào)用ford.m的m函數(shù)文件。命令形式： f,wf=ford(C,n)功能：C是輸入的容量矩陣，n是總的頂點數(shù)。f輸出最大流矩陣;wf輸出最大流量。2021-

15、11-16 六、最大流問題例4 求下圖中的最大流。2021-11-16 六、最大流問題n=8;c1=0 5 4 3 0 0 0 0;0 0 0 0 5 3 0 0;c2=0 0 0 0 0 3 2 0;0 0 0 0 0 0 2 0;c3=0 0 0 0 0 0 0 4; 0 0 0 0 0 0 0 3;c4= 0 0 0 0 0 0 0 5;0 0 0 0 0 0 0 0;C=c1;c2;c3;c4;f,wf=ford(C,n)2021-11-16 六、最大流問題最小費用最大流2021-11-16 六、最大流問題例如 2021-11-16 六、最大流問題最小費用最大流調(diào)用mford.m的m函數(shù)文件。命令形式： f,wf,zwf=mford(C,b,n)功能：C是輸入的容量矩陣，b是弧