圖經(jīng)典運籌學(xué)

圖經(jīng)典運籌學(xué)第一頁，共四十三頁，2022年，8月28日※歌尼斯堡七橋難題普萊格爾河第二頁，共四十三頁，2022年，8月28日結(jié)論：不存在這樣一種走法。用A、B表示兩座小島，C、D表示兩岸，連線AB表示A、B之間有一座橋。問題簡化為：ABCD在該圖中，從任一點出發(fā)，能否通過每條線段一次且僅僅一次后又回到原來的出發(fā)點七橋問題的數(shù)學(xué)模型：第三頁，共四十三頁，2022年，8月28日類似的問題：一筆畫問題字的一筆畫：如“中、日、口、串”等可一筆畫而：“田、目”等不能一筆畫圖的一筆畫：可一筆畫不可一筆畫第四頁，共四十三頁，2022年，8月28日圖論的應(yīng)用范圍：1、中國郵路問題：郵遞員如何選擇適當?shù)耐哆f路線，使每條街道至少走過一次且所走的總路程最短？2、最短路問題：一個鄉(xiāng)有9個自然村，其間道路如下圖所示，要以村為中心建有線廣播網(wǎng)，如要求沿道路架設(shè)廣播線，應(yīng)如何架設(shè)使所用電線最短411524431235514211212312第五頁，共四十三頁，2022年，8月28日已知一個地區(qū)的交通網(wǎng)絡(luò)如下圖所示，其中點代表居民小區(qū)，邊表示公路，問區(qū)中心醫(yī)院應(yīng)建在哪個小區(qū)，可使離醫(yī)院最遠的小區(qū)居民就診時所走的路程最近？結(jié)論：把醫(yī)院建在v6，可使離醫(yī)院最遠的小區(qū)居民就診時所走的路程最近即求圖的中心3、選址問題603015182515202030第六頁，共四十三頁，2022年，8月28日例：在一個輸油管道網(wǎng)中，最大流問題4、網(wǎng)絡(luò)流問題：旅客流、車流、貨物流26173224215344第七頁，共四十三頁，2022年，8月28日§5.1圖第八頁，共四十三頁，2022年，8月28日------由若干個點和連接這些點的某些連線所組成的圖形vi——圖中的點，稱為頂點。ei——圖中的連線，稱為邊。m(G)=|E|——G的邊數(shù)，簡記為mn(G)=|V|——G的頂點數(shù)，簡記為n一、圖的概念記V={vi}，E={ei},G=（V，E）圖G——一個圖代表具體事物代表事物之間的聯(lián)系Gm=6,n=55.1基本概念第九頁，共四十三頁，2022年，8月28日有向圖無向圖——邊e=（vi,vj）有方向——邊e=（vi,vj）無方向此時（vi,vj）=（vj,vi）e4=（v3，v4）=（v4，v3）e4=（v3，v4）≠（v4，v3）e5=（v3，v4）=（v4，v3）此時（vi,vj）≠（vj,vi）vi為始點，vj為終點有向圖無向圖e5=（v4，v3）≠（v3，v4）第十頁，共四十三頁，2022年，8月28日二、常用名詞：1、端點和關(guān)聯(lián)邊：2、相鄰點和相鄰邊：3、多重邊與環(huán)：4、多重圖和簡單圖：第十一頁，共四十三頁，2022年，8月28日5、次：6、懸掛點和懸掛邊：7、孤立點：8、奇點與偶點：，G的邊數(shù)m=6第十二頁，共四十三頁，2022年，8月28日定理1在圖G=(V,E)中，所有點的次之和是邊數(shù)m的兩倍。證明：由于每條邊均與兩個頂點關(guān)聯(lián)，因此在計算頂點的次時每條邊都計算了兩遍所以頂點次數(shù)的總和等于邊數(shù)的二倍。三、次的性質(zhì)第十三頁，共四十三頁，2022年，8月28日定理5.2在任何圖G=(V,E)中，奇點的個數(shù)為偶數(shù)證明：（定理5.1）只有偶數(shù)個奇數(shù)相加才能得到偶數(shù)第十四頁，共四十三頁，2022年，8月28日簡單鏈鏈四、鏈：初等第十五頁，共四十三頁，2022年，8月28日圈或回路簡單圈初等圈道路第十六頁，共四十三頁，2022年，8月28日連通圖不連通圖第十七頁，共四十三頁，2022年，8月28日六、賦權(quán)圖（網(wǎng)絡(luò)）對圖G=（V，E），若對每一條邊e，都有一個實數(shù)w(e)與之對應(yīng)，e的權(quán)則稱圖G=（V，E）為賦權(quán)圖，或網(wǎng)絡(luò)權(quán)w(e)通常表示距離、費用、容量等如公路交通圖：Vi表示城市，ei表示公路w(ei）表示公路ei的長度如w(e2）=50：城市v2到城市v3的距離是50公里第十八頁，共四十三頁，2022年，8月28日5.2歐拉圖與中國回路問題開鏈一筆畫問題第十九頁，共四十三頁，2022年，8月28日圈存在歐拉回路：該圖特點：該圖不存在歐拉回路歐拉圖第二十頁，共四十三頁，2022年，8月28日定理5.3無向連通圖G為歐拉圖的充要條件是G中無奇點已知G=（V,E)為歐拉圖，即存在一條歐拉回路C，C經(jīng)過G的每一條邊，由于G為連通圖，所以G中的每個點至少在C中出現(xiàn)一次證明：必要性第二十一頁，共四十三頁，2022年，8月28日充分性：若無向連通圖G=(V,E)中無奇點，則G為歐拉圖例：第二十二頁，共四十三頁，2022年，8月28日第二十三頁，共四十三頁，2022年，8月28日第二十四頁，共四十三頁，2022年，8月28日例：判斷下圖是否為歐拉圖，若是，求出歐拉回路定理5.3無向連通圖G為歐拉圖的

充要條件是G中無奇點第二十五頁，共四十三頁，2022年，8月28日定理5.3無向連通圖G為歐拉圖的充要條件是G中無奇點推論無向連通圖G有歐拉道路的充要條件是G中恰有兩個奇點第二十六頁，共四十三頁，2022年，8月28日一筆畫問題：1、一個連通圖的頂點都是偶點，沒有奇點，則該圖可以一筆畫出2、一個連通圖的頂點恰有兩個奇點，其余均為偶點，則從任一奇點出發(fā)，可以一筆畫出該圖，而終點則是另一個奇點。（從任一點出發(fā)均可）3、一個連通圖的頂點有兩個以上的奇點，則該圖不能一筆畫出第二十七頁，共四十三頁，2022年，8月28日田日中白回不連通可一筆畫可一筆畫不可一筆畫可一筆畫可一筆畫不可一筆畫不可一筆畫第二十八頁，共四十三頁，2022年，8月28日二、中國郵路問題提出問題的人：管梅谷教授時間：1962年提出的問題：一個郵遞員從郵局出發(fā)分送郵件，要走完他負責投遞的所有街道，最后再返回郵局，應(yīng)如何選擇投遞路線，才能使所走的路線最短？郵路問題的圖論描述：取一無向賦權(quán)連通圖G=（V，E）E中的每一條邊對應(yīng)一條街道每條邊的非負權(quán)l(xiāng)(e)=街道的長度V中某一個頂點為郵局，其余為街道的交叉點在G上找一個圈，該圈過每邊至少一次，且圈上所有邊的權(quán)和最小第二十九頁，共四十三頁，2022年，8月28日1、若G中的頂點均為偶點，即G中存在歐拉回路，則該回路過每條邊一次且僅一次，此回路即為所求的投遞路線郵路問題的圖論描述：在無向連通賦權(quán)G=（V，E）上找一個圈，該圈過每邊至少一次，且圈上所有邊的權(quán)和最小2、G中有奇點：不存在歐拉回路投遞路線：至少有一街道要重復(fù)走一次或多次第三十頁，共四十三頁，2022年，8月28日即不存在每條街道走一次且只走一次的投遞路線分析：重復(fù)邊結(jié)論：選擇最佳投遞路線=選擇重復(fù)邊的權(quán)和最小的路線111111111第三十一頁，共四十三頁，2022年，8月28日111111111111111111第三十二頁，共四十三頁，2022年，8月28日反之，對郵路圖G，對該鏈上的每一條邊增加一條重復(fù)邊111111111111111111投遞路線歐拉圖第三十三頁，共四十三頁，2022年，8月28日結(jié)論：對任意一個含奇點的郵路圖G，由于奇點的個數(shù)為偶數(shù)個，把每兩個配成一對，由于G為連通圖，每對奇點之間至少存在一條鏈，對該條鏈上的每一條邊增加一條重復(fù)邊，可得一歐拉圖，該歐拉圖對應(yīng)一條投遞路線尋找最佳投遞路線方法：在原郵路圖上增加一些重復(fù)邊得一個歐拉圖，，在所得歐拉圖上找出一條歐拉回路。計算重復(fù)邊的權(quán)和，重復(fù)邊權(quán)和最小歐拉回路既為所求的最佳投遞路線管梅谷——奇偶點圖上作業(yè)法第三十四頁，共四十三頁，2022年，8月28日奇偶點圖上作業(yè)法：例：求解右圖所示的郵路問題第一步：確定一個初始可行方案方法：檢查圖G中是否有奇點無奇點：，找出一條以v1為起點的歐拉回路，該回路就是最佳投遞路線有奇點：圖G已是歐拉圖把所有奇點兩兩配成一對，每對奇點找一條鏈，在該條鏈上的每一條邊增加一條重復(fù)邊，得一個歐拉圖G1，由G1所確定的歐拉回路即為一個可行方案v2，v8，v4，v6G中有奇點：取v2到v4的一條鏈：v2v1v6v7v8v9v4取v6到v8的一條鏈：v6v1v2v3v4v9v8G243469544354第三十五頁，共四十三頁，2022年，8月28日G1顯然G1不是最佳方案G1是歐拉圖，第二步：調(diào)整可行方案，使重復(fù)邊權(quán)和下降重復(fù)邊權(quán)和=若圖中某條邊有兩條或多于兩條的重復(fù)邊同時去掉偶數(shù)條，G2使圖中每一條邊最多有一條重復(fù)邊G2的重復(fù)邊權(quán)和=24346954435步驟1、可得到重復(fù)邊權(quán)和較小的歐拉圖4G22434695443545121第三十六頁，共四十三頁，2022年，8月28日24346954435G2是歐拉圖，重復(fù)邊權(quán)和=21G242、使圖中每個初等圈重復(fù)邊的權(quán)和不大于該圈權(quán)和的一半9個初等圈24346954435G24G3G3是歐拉圖，重復(fù)邊權(quán)和=17第三十七頁，共四十三頁，2022年，8月28日G32434695443546（1）v1v2v5v6v116√7（2）v6v5v8v7v614√10（3）v2v3v4v5v224√4（4）v5v4v9v8v516√G3的初等圈權(quán)和重復(fù)邊權(quán)和13（5）v1v2v5v8v7v6v124×G4243469544354第三十八頁，共四十三頁，2022年，8月28日G42434695443547（1）v1v2v5v6v116√4（2）v6v5v8v7v614√4（3）v2v3v4v5v224√8（4）v5v4v9v8v516√G4的初等圈權(quán)和重復(fù)邊權(quán)和11（5）v1v2v5v8v7v6v124√（6）v2v3v4v9v8v5v2324√（8）v6v5v4v9v8v7v6（7）v1v2v3v4v5v6v12811√224√（9）v1v2v3v4v9v8v7v6v1367√G4是最佳方案第三十九頁，共四十三頁，2022年，8月28日奇偶點圖上作業(yè)法：第一步：確定一個初始可行方案方法：檢查圖G中是否有奇點。無奇點：，找出一條以v0為起點的歐拉回路，該回路就是最佳投遞路線有奇點：圖G已是歐拉圖把所有奇點兩兩配成一對，每對奇點找一條鏈，在該條鏈上的每一條邊增加一條重復(fù)邊第二步：調(diào)整可行方案，使重復(fù)邊權(quán)和下降1、使圖中每一條邊最多有一條重復(fù)邊若圖中某條邊有兩條或多于兩條的重復(fù)邊，同時去掉偶數(shù)條2、使圖中每個初等圈重復(fù)邊的權(quán)和≤該圈權(quán)和的一半若圖中某初等圈重復(fù)邊的權(quán)和大于該圈權(quán)和的一半去掉圈中的重復(fù)邊同時將圈中沒有重復(fù)邊的邊加上重復(fù)邊第四十頁，共四十三頁，2022年，8月28日23261542312232615423