圖經(jīng)典運籌學

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

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