運籌學(xué) 第一節(jié) 圖與網(wǎng)絡(luò)的基本知識

運籌學(xué)課件第一節(jié)圖與網(wǎng)絡(luò)的基本知識1第1頁，共56頁，2023年，2月20日，星期日圖的基本概念G=（V，E）子圖矩陣表示含元素的個數(shù)點的次邊圖點邊關(guān)系簡單圖多重圖連通圖樹生成子圖2第2頁，共56頁，2023年，2月20日，星期日第二節(jié)樹

主要內(nèi)容

一、樹的概念以及性質(zhì)二、圖的生成樹：深探法、廣探法和破圈法三、最小生成樹：避圈法和破圈法四、根樹及其應(yīng)用3第3頁，共56頁，2023年，2月20日，星期日樹是一類極其簡單而很有用的圖。多級輻射制的電信網(wǎng)絡(luò)、家譜、分類學(xué)、管理組織結(jié)構(gòu)等都是典型的樹圖。某企業(yè)的組織結(jié)構(gòu)圖總經(jīng)理生產(chǎn)經(jīng)理人力經(jīng)理銷售經(jīng)理車間主任銷售代表招聘人員一、樹的概念以及性質(zhì)ABCDEFN乒乓球單打比賽抽簽后，用圖表示相遇情況v1v2w1v3w2V4第4頁，共56頁，2023年，2月20日，星期日樹實際上是連通圖，但沒有圈。由所有節(jié)點(n)和相應(yīng)的邊(n-1)組成。定義14（樹）:一個無圈的連通無向圖稱為樹。樹中次為1的點為樹葉；次大于1的點為分枝點。bfedv1v2v3v4v5d(v1)=1;v1樹葉d(v2)=1;v2樹葉d(v5)=1;v5樹葉d(v4)=4;v4分枝點d(v3)=1;v3樹葉5第5頁，共56頁，2023年，2月20日，星期日例：判斷下列圖形是否為樹圖1v1v2e1樹圖2v1v2v3e1e2e36第6頁，共56頁，2023年，2月20日，星期日v2abcfedhg圖3v1v3v4v5圖4bfdgv1v2v3v5v4樹7第7頁，共56頁，2023年，2月20日，星期日abch圖5v1v2v3v4v5bced圖6v1v2v3v4v5樹樹8第8頁，共56頁，2023年，2月20日，星期日v4v3afdg圖7v1v2v5v3bfed圖8v1v2v4v5樹樹9第9頁，共56頁，2023年，2月20日，星期日樹的性質(zhì)：1、在圖中任意兩點之間必有一條而且只有一條鏈。2、

在圖中劃去一條邊，則圖不連通。3、

在圖中不相鄰的兩個頂點之間加一條邊，可得一個且僅得一個圈。4、圖中邊數(shù)有m=n-1（n為頂點數(shù)）10第10頁，共56頁，2023年，2月20日，星期日定理6:圖T=(V,E),點數(shù)=n;邊數(shù)=m；下列關(guān)于樹的說法等價。（1）T是一棵樹；（2）T無圈，且m=n-1；（3）T連通，且m=n-1；（4）T無圈，但任加一新邊得到唯一一個圈；（5）T連通，但任舍去一邊就不連通；（6）T任意兩點，有唯一鏈相連。11第11頁，共56頁，2023年，2月20日，星期日bcfedhgbfedbfdgbcedabchafdg圖3圖4圖5圖6圖7圖8a12第12頁，共56頁，2023年，2月20日，星期日二、圖的生成樹定義15如果圖T是G的一個生成子圖，而且T又是一棵樹，則稱圖T為一棵生成樹（支撐樹）。子圖定義：設(shè)G=（V，E）和G1=（V1，E1）。如果V1

V，E1

E，且E1邊僅與V1中的頂點相關(guān)聯(lián)，則稱G1為G的子圖；生成子圖定義：如果G1=（V1，E1

）是G=（V，E）子圖，并且V1

=V，則稱G1為G的生成子圖。13第13頁，共56頁，2023年，2月20日，星期日生成樹與子圖、生成子圖的關(guān)系

一個子圖與生成樹的區(qū)別是：子圖與原圖相比少邊又少點，生成樹與原圖相比少邊不少點。一個生成子圖與生成樹的區(qū)別是：生成子圖可能含有圈，生成樹無圈。圖中屬于生成樹的邊為樹枝，不在生成樹中的邊為弦。14第14頁，共56頁，2023年，2月20日，星期日子圖練習(xí)1：找出圖G的子圖，生成子圖，生成樹圖1e1e8e7e6e5e4e3e2v5v3v4v2v1e8e1e7e6e5e4e3v5v4v2v1圖G15第15頁，共56頁，2023年，2月20日，星期日生成子圖e1e8e7e6e5e4e3e2v5v3v4v2v1e1e8e6e4e3e2v5v3v4v2v1圖2圖G16第16頁，共56頁，2023年，2月20日，星期日生成子圖；生成樹；樹枝e2,e3,e5,e6;弦e1,e4,e7,e8e5e2e6圖3圖Ge3e1e8e7e6e5e4e3e2v5v3v4v2v1v3v2v1v4v517第17頁，共56頁，2023年，2月20日，星期日定理7圖G有生成樹的充分必要條件為圖G是連通圖。生成樹的求解方法：（1）深探法步驟：a.在點集V中任取一點v,給v標(biāo)號0；b.如果某點u已經(jīng)得到標(biāo)號i,檢查一端點為u的各邊，另一端是否已經(jīng)標(biāo)號。如果有（u,w）邊的w點未標(biāo)號，則給w以標(biāo)號i+1,記下邊（u,w）。令w代替u,繼續(xù)重復(fù)。如果有（u,w）邊的w已經(jīng)標(biāo)號，則退到標(biāo)號i-1的r點,

令r代替u,繼續(xù)重復(fù)。18第18頁，共56頁，2023年，2月20日，星期日012345678910111213u已經(jīng)得到標(biāo)號,檢查一端點為u的各邊，另一端w是否已經(jīng)標(biāo)號，有（u,w）邊的w已經(jīng)標(biāo)號，則退到標(biāo)號i-1的r點,令r代替u,繼續(xù)重復(fù)。r=5-1;r代替u19第19頁，共56頁，2023年，2月20日，星期日原則：不能成圈原則：不能成圈原則：不能成圈.0.1.3.4.5.2.6.7.8.9.10.11.12.1301234567891011121320第20頁，共56頁，2023年，2月20日，星期日（2）廣探法步驟：a.在點集V中任取一點v,給v標(biāo)號0；b.令所有標(biāo)號i的點集為Vi,檢查[Vi,V\Vi]中的邊端點是否已經(jīng)標(biāo)號，對所有的未標(biāo)號的點均標(biāo)號i+1,記下這些邊。c.對標(biāo)號i+1的點繼續(xù)重復(fù)步驟b，直至全部點得到標(biāo)號21第21頁，共56頁，2023年，2月20日，星期日01112222333412AB22第22頁，共56頁，2023年，2月20日，星期日14203331112222圖的生成樹不唯一1111022222333423第23頁，共56頁，2023年，2月20日，星期日（3）破圈法(深探法和廣探法核心是避免成圈)

步驟：從圖G任取一個圈,從圈中任舍棄一條邊,將此圈破掉。重復(fù)以上步驟直至無圈為止。圈1圈2圈3圈4圈5圈6v1v2v3v4v5v6v724第24頁，共56頁，2023年，2月20日，星期日練習(xí)2：分別使用深探法、廣探法、破圈法找出下圖的一個生成樹25第25頁，共56頁，2023年，2月20日，星期日01234使用深探法找出下圖的一個生成樹26第26頁，共56頁，2023年，2月20日，星期日使用廣探法找出下圖的一個生成樹０１１１２27第27頁，共56頁，2023年，2月20日，星期日使用破圈法找出下圖的一個生成樹圈1圈２圈３圈４28第28頁，共56頁，2023年，2月20日，星期日求最小樹的方法有避圈法和破圈法。三、最小生成樹定義16：在賦權(quán)圖G中，一棵生成樹所有樹枝上權(quán)的和，稱為生成樹的權(quán)。具有最小權(quán)的生成樹，稱為最小生成樹或最小樹或最小支撐樹。最小樹的應(yīng)用：設(shè)計長度最小的公路網(wǎng)把若干城市聯(lián)系起來；設(shè)計用料最省的電話線網(wǎng)把有關(guān)單位聯(lián)系起來。29第29頁，共56頁，2023年，2月20日，星期日例一個鄉(xiāng)有9個村，道路及其道路長度如圖，如何拉電線才能使電線總長度最短?1、避圈法（krusakal）步驟：每步從未選的邊中選取邊e,使它與已經(jīng)選的邊不構(gòu)成圈，且e是未選邊中的最小權(quán)邊，直到選夠n-1條邊。解（1）先將圖中邊按照大小順序由小到大排列(v0,v2)=1,(v3,v2)=1,(v3,v4)=1,(v1,v8)=1；(v0,v1)=2,(v0,v6)=2,(v5,v6)=2(v0,v3)=3,(v6,v7)=3;(v0,v4)=4,(v0,v5)=4,(v0,v8)=4,(v1,v2)=4,(v0,v7)=5,(v7,v8)=5,(v4,v5)=5V1V0V8V2V3V4V5V6V7145325114421235430第30頁，共56頁，2023年，2月20日，星期日V1V0V8V2V3V4V5V6V7145325114421235431第31頁，共56頁，2023年，2月20日，星期日定理8:用避圈法(kruskal)算法得到的子圖為一棵最小樹V1V0V8V2V3V4V5V6V713211212使用電話線最小長度L=1+1+1+1+2+2+2+3=1332第32頁，共56頁，2023年，2月20日，星期日2、破圈法步驟：(1)從圖G中任選一棵樹T1;(2)加上一條弦e1,T1+e1中立即生成一個圈。去掉此圈中的最大權(quán)邊，得到新樹T2,以T2代替T1，繼續(xù)重復(fù)檢查剩余的弦，直到全部弦檢查完畢。定理9：圖G的生成樹T為最小樹，當(dāng)且僅當(dāng)對任一弦e來講，e是T+e中與之對應(yīng)的圈ue中的最大權(quán)邊。33第33頁，共56頁，2023年，2月20日，星期日V1V0V8V2V3V4V5V6V7145325114421235434第34頁，共56頁，2023年，2月20日，星期日例：先求出一棵樹T1，加以弦（v1,v2），得到圈{v1v2v0v1},去掉最大權(quán)邊（v1,v2

）;再加上弦（v2,v3

），得到圈{v2v3v0v2},去掉最大權(quán)邊（v0,v3

）……,全部弦。2134142544152351V1V0V7V6V8V2V3V4V5使用電話線最小長度L=1+1+1+1+2+2+2+3=1335第35頁，共56頁，2023年，2月20日，星期日另一種破圈法：找圈，擦除最大邊以破圈。賦權(quán)圖G1542453134421512生成最小樹T12312112圈1圈2圈3圈4圈5圈6圈7圈8使用電話線最小長度L=1+1+1+1+2+2+2+3=1336第36頁，共56頁，2023年，2月20日，星期日V1V6V3V4V5V2V74323245172674練習(xí)3：破圈法求下圖的最小樹最小樹的權(quán)=3+3+2+2+1+2=1337第37頁，共56頁，2023年，2月20日，星期日93174123201516252836練習(xí)4：避圈法求下圖的最小樹最小樹的權(quán)=1+4+9+3+17+23=57v2v3v4v5v6v7v138第38頁，共56頁，2023年，2月20日，星期日根：根樹入次=0的點；葉:根樹出次=0的點；其他的頂點為分枝點。層次：由根到某一頂點的道路長度（假設(shè)每邊的長度為1），稱為點的層次。四、根樹及其應(yīng)用1、根樹對有向圖而言,根樹在計算機科學(xué)、決策論有重要應(yīng)用定義17：如果一個有向圖在不考慮邊的方向時是一棵樹，此有向圖為有向樹。定義18：有向樹T,恰好有一個結(jié)點入次=0，其余各點入次=1，樹T為根樹（外向樹）。39第39頁，共56頁，2023年，2月20日，星期日V1:根V1V4V9V8V7V6V5V2V10V3例V5,V6,V4,V7,V9,V10：葉V1,V2.V3,V8：分枝點V2,V3,V4的層次：1V5,V6,V7,V8,V9的層次：2V10層次：3v1入次=0其它點入次=1T根樹v5,v6出次=0v4出次=0v7,v9出次=0v10出次=0根樹應(yīng)用:系統(tǒng)的傳遞關(guān)系;指揮系統(tǒng)的上下級關(guān)系;計算機科學(xué)的應(yīng)用有向樹40第40頁，共56頁，2023年，2月20日，星期日定義19：在根樹中，如果每個頂點的出次等于m或零，稱此樹為完全m叉樹。如每個頂點的出次小于或等于m稱此樹為m叉樹。當(dāng)m=2時，為完全二叉樹、二叉樹。完全三叉樹四叉樹出次=3出次=3出次=0出次=3出次=2出次=4出次=1出次=041第41頁，共56頁，2023年，2月20日，星期日算法步驟：（1）將s個葉子按照權(quán)大小排序。（2）將二個具有最小權(quán)的葉子合并成一個分枝點，其權(quán)p1+p2;將新得到的分枝點作為一個葉子。令s=s-1,如果s=1，停止，否則轉(zhuǎn)（1）。實際問題中經(jīng)常討論葉子上帶權(quán)的二叉樹。有s個葉子的二叉樹T各個葉子的權(quán)分別為pi,根到葉子的層次為Li(i=1,2,…s),這樣葉子的二叉樹的總權(quán)數(shù)m(T)=滿足總權(quán)最小的二叉樹為最優(yōu)二叉樹或霍夫曼樹。42第42頁，共56頁，2023年，2月20日，星期日例：S=6,其權(quán)分別為4，3，3，2，2，1，求最優(yōu)二叉樹12234312234335643第43頁，共56頁，2023年，2月20日，星期日122343356915總權(quán)為m（T）=4×2+1

×4+2×4+2×3+3×2+3×2=38綠色為葉子;黑色為層次。44第44頁，共56頁，2023年，2月20日，星期日例:使用計算機進行圖書分類?，F(xiàn)有5類圖書共100萬冊，其中有A類50萬冊，有B類20萬冊，有C類5萬冊，有D類10萬冊，有E類15萬冊。問如何安排分揀過程，可使總的運算（比較）次數(shù)最??？2、最優(yōu)二叉樹的應(yīng)用解：先構(gòu)造一棵具有5個葉子的最優(yōu)二叉樹，令其葉子的權(quán)分別為50，20，5，10，15，然后構(gòu)造最優(yōu)二叉樹。45第45頁，共56頁，2023年，2月20日，星期日510152050153050CDEBA100A？B？ANYE？BNYD？ENYDNYCm（T）=5×4+10×4+15×3+20×2+50×1=19546第46頁，共56頁，2023年，2月20日，星期日思考題:如何將實際應(yīng)用與最小生成樹的算法聯(lián)系起來？47第47頁，共56頁，2023年，2月20日，星期日小結(jié)：1、樹的概念以及性質(zhì)。2、圖的生成樹：深探法、廣探法和破圈法。3、最小生成樹：避圈法和破圈法。4、根樹及其應(yīng)用。48第48頁，共56頁，2023年，2月20日，星期日49第49頁，共56頁，2023年，2月20日，星期日50第50頁，共56頁，2023年，2月20日，星期日證明：(1)T是一棵樹由于T是一棵樹，根據(jù)定義，T是連通且無圈?，F(xiàn)在需要證明邊數(shù)m=n-1。用歸納法：當(dāng)n=2，由于T是一棵樹，所以兩點之間只有1條邊，滿足m=n-1；假設(shè)當(dāng)n=k-1時命題成立，有k-1個頂點，有k-2條邊。bfeduvT(2)T無圈，且m=n-1T1eu51第51頁，共56頁，2023年，2月20日，星期日證明：(1)T是一棵樹當(dāng)n=k時，T是連通且無圈，k個頂點至少有1個點次為1.設(shè)點u，為懸掛點，邊e=(u,v);從T中去掉邊e和點u不會影響T的連通，得到T1:T1為樹只有k-1個頂點，有k-2條邊，再把e=(u,v)點u加上去，可知當(dāng)T有k個頂點時有k-1條邊。bfeduvT(2)T無圈，且m=n-1T1eu52第52頁，共56頁，2023年，2月20日，星期日證明：（2）T無圈，且m=n-1（3）T連通，且m=n-1只需要T證明是連通的。反證法：假設(shè)T不是連通的，可以分為L個連通子圖(L≥2)，設(shè)第i個子圖有ni個頂點，因為第i個連通子圖是樹，所以有ni-1條邊，L個子圖共