圖論與幾何模型

第七講:圖論與幾何模型---水鵬朗數(shù)學建模理論與實驗7.1哥尼斯堡七橋問題Euler時代的哥尼斯堡城區(qū)(18世紀)

現(xiàn)在的俄羅斯加里寧格勒市(俄羅斯“飛地”)Euler問題能否找到一條路徑:從一個地方出發(fā)穿過每座橋僅一次再回到出發(fā)地。幾何抽象幾何抽象的目的在于提純與問題相關(guān)的因素(河流、橋、區(qū)域），剔除與問題無關(guān)的因素(城區(qū)的地面景觀等)，以便簡化問題描述。7.1哥尼斯堡七橋問題ABCDABCDGraph(圖,無向圖),圖論(GraphTheory)7.1哥尼斯堡七橋問題圖的描述abcdefghi一個圖G由兩個集合構(gòu)成，頂點(vertex)集合V(G)和邊(Edge)集合E(G).V(G)={a,b,c,d,e,f,g,h,i}E(G)={ac,ad,af,bd,bg,ch,di,ef,ei,fg,gh,hi}連接矩陣表示7.1哥尼斯堡七橋問題abcdefghi基本術(shù)語與概念如果邊e的一個頂點是j,那么稱作邊e與頂點j是關(guān)聯(lián)的(incident).如果頂點i，j有邊相連,那么稱作頂點i和j是鄰接的(adjacent).頂點i的度(階數(shù))是指與頂點i關(guān)聯(lián)的邊（或者鄰接的頂點）的數(shù)目，記作degree(i).例如degree(a)=3;degree(b)=2;degree(i)=3.簡單圖--每對頂點之間至多只有一條邊相連。給定一個頂點序列{i,…,j

},如果相鄰兩個頂點都有邊相連，那么，該頂點序列定義了一條以i,j為端點的路徑(path).如果兩個頂點有路徑相連，稱作兩個頂點是連通的。7.1哥尼斯堡七橋問題ABCD七橋問題中頂點的階數(shù)Euler問題的圖論表述：給定一個圖G,什么條件下通過每條邊僅一次的封閉路徑是存在的？直觀的必要條件：

圖G必須是連通的，即任意兩個頂點都有路徑相連(連通圖)；

圖G的所有頂點的階數(shù)是偶數(shù)-進入和離開每個頂點的次數(shù)相同7.1哥尼斯堡七橋問題Euler問題有解

圖G是連通的；

圖G所有頂點的階數(shù)是偶數(shù)哥尼斯堡七橋問題是無解的：沒有一條路徑經(jīng)過每座橋各一次，再回到出發(fā)地。松弛Euler問題：經(jīng)過每座橋各一次，但不要求回到出發(fā)點回路開路Euler圖：圖論中的重要類型和基礎(chǔ)松弛Euler問題:什么條件下，在一個圖G中能夠找到一條路徑經(jīng)過每條邊各一次？

圖G是連通的；

圖G僅有兩個頂點階數(shù)是奇數(shù)。7.1哥尼斯堡七橋問題8橋情況：松弛Euler問題有解4354ADCBDCAABDBACDABDC7.1哥尼斯堡七橋問題9橋情況：松弛Euler問題有解4455ACBDBABDBCACDAABDC如果9橋情況下想讓Euler問題有解，第九座橋應(yīng)如何建？44467.1哥尼斯堡七橋問題10橋情況：Euler問題有解4466ACBDBDBCAACDAB從任意一個頂點出發(fā)都可以經(jīng)過所有橋一次再回到出發(fā)頂點。7.2地圖著色問題(四色猜想-問題)什么是四色猜想？圖中復(fù)雜的平面圖形中，可以用四種顏色(紅、黃、綠、藍）把不同區(qū)域清楚標識，相鄰區(qū)域顏色不同。該結(jié)論具有普適性嗎？美國地圖也可以用四種顏色標識不同的州?？磥碓摻Y(jié)論似乎具有普適性---四色猜想。再看10000幅地圖，也不能證明結(jié)論—數(shù)學從來不相信有限歸納。給定任意一個平面地圖，“用四種顏色著色地圖以便于任何兩個具有共同邊界(長度大于0)的區(qū)域用不同的顏色”是可能的嗎?7.2地圖著色問題(四色猜想-問題)從猜想到定理還留下什么？1852年，地圖著色問題第一次被FrancisGuthrie正式提出，拉開了100多年的“四色猜想”證明歷程。1890年，Heawood證明了“五色定理”，也就是任何的平面地圖可以用五種顏色著色，相鄰區(qū)域具有不同顏色?！鞍倌贽D(zhuǎn)身”艱難但不完美，從1976年起，質(zhì)疑從未平息。引發(fā)哲學級的思考：

計算機證明的正確性如何人工驗證？

機器證明的理論基礎(chǔ)和局限性何在？AI過熱的時候，更需要冷靜的腦袋—哲學思考KennethAppel

和

WolfgangHaken在1976年給出了“四色定理”的證明，但第一個主要定理的證明是通過計算機完成的。該證明被普遍認為是正確的，從而實現(xiàn)了從“四色猜想”到“四色定理”的艱難轉(zhuǎn)身。7.2地圖著色問題(四色猜想-問題)四色問題的圖論建模我國行政區(qū)域的五色著色問題的解；非專業(yè)拼圖業(yè)余愛好者作品。數(shù)學問題的難點不在于個例處理，而在于一個結(jié)論的“真理性”---邊界條件內(nèi)沒有例外的普適性。。四色問題的圖論描述：僅用四種顏色，能夠?qū)θ我馄矫鎴D的頂點進行著色以便相鄰頂點具有不同顏色嗎？7.2地圖著色問題(工程應(yīng)用)通信網(wǎng)絡(luò)基站配置問題如右圖所示，在西安市城區(qū)布置了很多手機基站，各基站覆蓋范圍相互重疊，為了減少基站間的信號相互干擾，各基站采用不同的正交碼組(正交碼組之間即使區(qū)域重疊也互不干擾)，這樣的碼組至少需要多少個？正交碼組在基站間如何配置？試建立數(shù)學模型并給出解決問題的思路。7.2地圖著色問題(工程應(yīng)用)圖論建模方法用每個基站作為圖的頂點；

如果兩個基站覆蓋區(qū)域相互重疊，基站對應(yīng)的頂點用一條邊相連(表示這兩個頂點是鄰接的)；

按照“四色定理”，平面圖可用四種不同顏色著色，相鄰頂點顏色不同；顏色對應(yīng)正交碼組；因此，理論上四個正交碼組就足夠了！

正交碼組配置問題轉(zhuǎn)化為平面圖的著色問題！四個正交碼組7.2地圖著色問題(工程應(yīng)用)平面圖：存在一種頂點配置模式，使得圖在該頂點配置下邊是互不相交的，或者邊把平面分割為以圖的頂點為頂點的互不重疊的多邊形區(qū)域。頂點位置移動7.2地圖著色問題(工程應(yīng)用)衍生問題

網(wǎng)絡(luò)中出現(xiàn)少量三小區(qū)交疊區(qū)域和四小區(qū)交疊區(qū)域情況下，牽扯到更復(fù)雜的圖的四色著色問題。

對于涉及三或四小區(qū)交疊的基站必須采用不同的正交碼組；在這些著色確定的情況下，再對其它頂點進行著色---殘圖著色問題。

如果出現(xiàn)五小區(qū)交疊情況，四個正交碼組是不夠的，至少需要5個正交碼組。四小區(qū)交疊區(qū)域7.3旅行商問題(TSP問題)-賦值圖給定一個城市列表以及每兩個城市之間的距離，找出一條最短的行程，經(jīng)過每個城市各一次并最終返回出發(fā)城市。(TravellingSalesmanProblem---19世紀由以色列數(shù)學家W.R.Hamilton和英國數(shù)學家ThomasKirkman首次作為數(shù)學問題正是提出，該問題的研究一直持續(xù)到今天。從中衍生出了許多求解算法和實際應(yīng)用問題：郵遞員問題、電子線路布線問題、DNA序列分析等)。西安銀川蘭州西寧拉薩成都400km900km烏魯木齊600km800km500km1200km2000km1500km1300km1000km1200km

部分城市間航線由于航班數(shù)目太少而忽略；

各城市可以看成一個平面圖G的頂點，城市間的航線看成連接頂點的邊；航線里程可以看成邊的賦值。從而產(chǎn)生了一個賦值平面圖。

圖必須是連通的，任意兩個頂點有路徑相連；否則問題無解。7.3旅行商問題(TSP問題)-賦值圖123567400km1000km4600km800km500km1200km2000km1500km1300km1000km1200km賦值圖的表示V(G)={1,2,…,7}-頂點集E(G)={…}---邊集合關(guān)聯(lián)矩陣C賦值矩陣W7.3旅行商問題求解大多數(shù)旅行商問題的應(yīng)用中，節(jié)點之間的距離滿足三角不等式,意味著城際間沒有捷徑可走(繞道總比直達遠）。

如果城際旅行中，城市間邊的賦值是旅行時間，三角不等式將不再成立(由于各城市間旅行交通工具上的差異，例如：如果通過鐵路旅行，合肥-北京花費的時間肯定比合肥-南京-北京花費的時間長)。這時的TSP問題變成：找出化費時間最少且經(jīng)過每個城市各一次的旅行路線。歐幾里德TSP問題很多實際問題中，經(jīng)過每個城市僅一次的要求可以放松為“經(jīng)過每個城市至少一次”，這樣可對問題求解帶來一些方便。

賦值圖不滿足三角不等式情況下旅行商問題:非歐幾里德TSP問題7.3旅行商問題求解TSP問題的求解被證明是NP-hard的，意味著：“隨著城市數(shù)目增加，任何求最優(yōu)路徑算法的計算時間隨著城市數(shù)目至少是指數(shù)增長的”。因此，各種求“次最優(yōu)，suboptimal”解的算法應(yīng)運而生：

神經(jīng)網(wǎng)絡(luò)方法；

遺傳算法；

線性規(guī)劃；

馬爾科夫鏈方法；

蟻群算法。。。。。。越是疑難雜癥，“能治”的醫(yī)生就越多！7.3旅行商問題求解來自生物啟發(fā)的蟻群算法

群體智慧和體驗的優(yōu)勢；在大群體和大時間跨度下，走的人多的常常是某種意義下的“最優(yōu)路線”。7.3旅行商問題求解上面提到的各種方法都用到了高深的數(shù)學理論，如果沒有現(xiàn)成軟件可利用，很難自己實現(xiàn)，數(shù)學建模中碰到類似問題，如何解決？！最近鄰算法(NearestNeighborhood算法)=貪婪策略：旅行商總是選擇最近的沒有訪問的城市作為下一個訪問城市。大量的隨機分布城市實驗表明：算法得到的平均路徑長度比最短路徑長25%。星際旅行路線尋優(yōu)7.3旅行商問題求解最近鄰算法介紹連通賦值圖的最短路徑問題：在一個連通賦值圖G中，求任意兩點之間的最短路徑。123450.150.10.120.090.50.20.10.251-5的路徑：1-4-5(0.3),1-3-5(0.35),1-3-4-5(0.32),1-2-5(0.65),1-2-3-5(0.49),1-2-3-4-5(0.46)最短路徑是：1-4-5===0.3.

類似地，在圖G中可以求出任意兩點之間的最短路徑，所有最短路徑作為兩個頂點之間連接的邊構(gòu)成了一個完全圖(任意兩個頂點之間都有邊相連）。

連通圖中最短路徑的求法已經(jīng)有成熟的算法Matlab2012中的庫函數(shù)[dist,path]=graphshortestpath(G,S)細節(jié)看庫函數(shù)的說明。7.3旅行商問題求解3450.150.10.120.090.50.20.10.25123450.150.10.120.090.310.20.10.220.30.2112最短路徑構(gòu)成的完全圖13245選擇從1出發(fā)到其他城市的最短路徑可選擇頂點{4,5}可選擇頂點{2,4,5}7.3旅行商問題求解3450.150.10.120.090.310.20.10.220.30.2112最短路徑：1:2----{1,2}1:3---{1,3}1:4---{1,4}1:5---{1,4,5}2:3---{2,3}2:4---{2,3,4}2:5---{2,3,4,5}3:4---{3,4}3:5---{3,4,5}4:5---{4,5}最近鄰算法{1,3},0.1{3,2},0.09{2,3,4},0.21{4,5},0.1最優(yōu)行程：132345410.1+0.09+0.21+0.1+0.3=0.8

7.4交通問題-有向賦值圖隨著家庭用小汽車在大城市中的日益普及，交通擁堵問題變成了大城市的“難治頑疾”?！跋尢柍鲂小保皢涡芯€”等應(yīng)急措施的出臺雖有所緩解，但北京城區(qū)的上班族亦然把一天1/8的時間消耗在路上?！皢涡芯€”也使得交通網(wǎng)絡(luò)更為復(fù)雜，很多路段難以實現(xiàn)“原路返”。交通網(wǎng)絡(luò)描述從“無向賦值圖”變成了“有向賦值圖”。道路四通八達，人“四不通”“八不達”“自行車”笑傲“寶馬”，我走了，你等著7.4交通問題-有向賦值圖0.99全是單行道的6個十字路口的交通線路圖賦值矩陣表示:非零元素稀疏矩陣非對稱列表表示7.4交通問題-有向賦值圖庫函數(shù)使用交通問題中，更多關(guān)心的是從一個頂點到另一個頂點的最短路徑問題：

在交通不很擁堵的時期，主要考慮的是最短路程的路徑；邊的賦值是距離。

今天城市交通中，更多考慮的是花費最短時間的路徑；邊的賦值是時間。[dist,path]=graphshortestpath(DG,1,6)最短路徑長度最短路徑連接賦值列表出發(fā)節(jié)點到達節(jié)點動態(tài)交通問題：實際交通網(wǎng)絡(luò)中，各交通線路上擁堵情況隨時間周期性變化，圖的賦值用時間的函數(shù)代替，這樣導(dǎo)致了動態(tài)交通問題。在賦值函數(shù)連續(xù)變化的情況下如何根據(jù)現(xiàn)在的最優(yōu)路徑微調(diào)得到下一時段的最優(yōu)路徑是經(jīng)?？紤]的問題。7.5有障礙最短路徑幾何建模設(shè)有一個半徑為r的圓形湖，圓心為O。A、B

位于湖的兩側(cè)，AB連線過O，見圖?，F(xiàn)擬從A點步行到B點，在不得進入湖中的限制下，問怎樣的路徑最近。ABOrEFE′F′將湖想象成凸出地面的圓木，在AB間拉一根軟線，當線被拉緊時將得到最短路徑。根據(jù)這樣的想象，猜測可以如下得到最短路徑：過A作圓的切線切圓于E，過B作圓的切線切圓于F。最短路徑為由線段AE、弧EF和線段FB連接而成的連續(xù)曲線（根據(jù)對稱性，AE′，弧E′F′，F(xiàn)′B連接而成的連續(xù)曲線也是）

切線AE,BF,AE’,BF’和弧EF和E’F’圍成的平面圖形有何特點？7.5有障礙最短路徑幾何建模定義2.1（凸集）稱集合R為凸集，若x1、x2∈R及λ∈[0，1]，總有λx1+（1+λ）x2∈R。即若x1、x2∈R，則x1、x2的連線必整個地落在R中。凸集非凸集凸多邊形非凸多邊形平面凸集的定義7.5有障礙最短路徑幾何建模對平面凸集R與R外的一點K，存在直線l,l

分離R與K，即R與K分別位于l的兩側(cè)（注：對高維空間的凸集R與R外的一點K，則存在超平面分離R與K），見圖。凸集分離定理KlRKRp7.5有障礙最短路徑幾何建模由AE、EF、FB及AE′，E′F′，F(xiàn)′B圍成的區(qū)域

是凸集；設(shè)Γ為最短路徑，Γ過

外的一點M，則必存在直線l分離M與

，由于路徑Γ是連續(xù)曲線，由A沿Γ到M，必交l于M1，由M沿Γ到B又必交l于M2。直線段M1M2的長度必小于路徑M1MM2的長度，與Γ是A到B的最短路徑相矛盾；因此最短路徑必然在凸集

內(nèi)。最短路徑證明ABOrEFE′F′M1M2MΓl設(shè)路徑經(jīng)湖的上方到達B點，則弧EF必在路徑上，又直線段AE是由A至E的最短路徑，直線FB是由F到B的最短路徑。7.5有障礙最短路徑幾何建模最短路徑的證明ABOrEFE′F′

如圖所示：E,F是過A,B點圓的切線的切點，E’和F’是圓上的另外兩個非切點。我們需要證明：路徑:線段AE+圓弧EF+線段BF<路徑：線段AE’+圓弧E’F’+線段BF’注意：點E’和F’必然在圓弧EF之外的弧段上。線段AE’+弧段E’E>線段AE(兩點之間的路徑直線段最短)7.5有障礙最短路徑幾何建模如果障礙區(qū)域是一個被封閉曲線包圍的平面凸集

，A,B是凸集外的兩點，那么最短路徑必然是包含,A和B的最小凸集的邊界線被A和B分割的兩段曲線中短的一條。

推而廣之-I-凸障礙區(qū)域

AB

AB7.5有障礙最短路徑幾何建模如果障礙區(qū)域是一個被封閉曲線包圍的平面非凸集

，A,B是在包含的最小凸集外的兩點，那么最短路徑必然是包含,A和B的最小凸集的邊界線被A和B分割的兩段曲線中短的一條。

推而廣之-II-非凸障礙區(qū)域問題ABl1l2DAB

7.5有障礙最短路徑幾何建模若可行區(qū)域的邊界是光滑曲面。則最短路徑必由下列弧組成，它們或者是空間中的自然最短曲線，或者是可行區(qū)域的邊界弧。而且，組成最短路徑的各段弧在連接點處必定相切。注：在平面上可行區(qū)域是指障礙區(qū)域的補集。注：該定理在1973年被J.W.Craggs證明。推而廣之-III-多障礙區(qū)域問題障礙區(qū)域障礙區(qū)域ABC1C27.5有障礙最短路徑幾何建模實際應(yīng)用-小汽車移庫問題一輛汽車停于A處并垂直于AB方向，此汽車可轉(zhuǎn)的最小圓半徑為R，求不倒車而由A到B的最短路徑。情況1：AB>2RABR7.5有障礙最短路徑幾何建模實際應(yīng)用-小汽車移庫問題一輛汽車停于A處并垂直于AB方向，此汽車可轉(zhuǎn)的最小圓半徑為R，求不倒車而由A到B的最短路徑。情況2：AB<2RABAB兩條路徑中較短的一條7.5有障礙最短路徑幾何建模實際應(yīng)用-小汽車移庫問題假設(shè)一輛停于A處與AB成θ1角度的汽車到B處去，已知B處要求的停車方向必須與AB成θ2角，試找出最短路徑(除可轉(zhuǎn)的最小圓半徑為R外，不受其它限止)。

1

2C1C2兩條路徑中較短的一條AB7.6島礁巡航問題近百年來，民族的屈辱史從海上開始。今天，從陸地大國走向海洋大國的路途漫長而曲折，海權(quán)維護仍舊是我們心中的痛！美麗的黃巖島釣魚島南海諸島造島神器"天鯨"號自航絞吸式挖泥船總長127.5m，型寬22m，吃水6m，設(shè)計航速12節(jié)，總裝機功率為19200KW，最大挖深-30m，最大排泥距離6000m