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

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

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