第七講-圖論與幾何模型

第七講:圖論與幾何模型---水鵬朗雷達(dá)信號(hào)處理國(guó)防科技重點(diǎn)實(shí)驗(yàn)室數(shù)學(xué)建模實(shí)驗(yàn)(數(shù)學(xué)建?；A(chǔ)之續(xù))7.1哥尼斯堡七橋問(wèn)題Euler時(shí)代的哥尼斯堡城區(qū)(18世紀(jì))

現(xiàn)在的俄羅斯加里寧格勒市Euler問(wèn)題能否找到一條路徑從一個(gè)地方出發(fā)穿過(guò)每個(gè)橋僅一次而再回到出發(fā)地。幾何抽象幾何抽象的目的在于提純與問(wèn)題相關(guān)的因素(河流、橋、區(qū)域），剔除與問(wèn)題無(wú)關(guān)的因素(城區(qū)的地面景觀等），以便簡(jiǎn)化問(wèn)題。7.1哥尼斯堡七橋問(wèn)題ABCDABCDGraph(圖,無(wú)向圖）,圖論(GraphTheory)7.1哥尼斯堡七橋問(wèn)題圖的描述abcdefghi一個(gè)圖G由兩個(gè)集合構(gòu)成，頂點(diǎn)(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哥尼斯堡七橋問(wèn)題圖的描述abcdefghi基本術(shù)語(yǔ)與概念如果邊e的一個(gè)頂點(diǎn)是j,那么稱作邊e與頂點(diǎn)j是關(guān)聯(lián)的(incident).如果頂點(diǎn)i，j有邊相連,那么稱作頂點(diǎn)i和j是鄰接的(adjacent).頂點(diǎn)i的度(階數(shù))是指與頂點(diǎn)i關(guān)聯(lián)的邊的數(shù)目，記作degree(i).例如degree(a)=3;degree(b)=2;degree(i)=3.簡(jiǎn)單圖--每對(duì)頂點(diǎn)之間至多只有一條邊相連。7.1哥尼斯堡七橋問(wèn)題ABCD七橋問(wèn)題中頂點(diǎn)的階數(shù)Euler問(wèn)題的圖論表述：給定一個(gè)圖G,在什么條件下去發(fā)現(xiàn)通過(guò)每條邊盡一次的封閉路徑是存在的？直觀的必要條件：

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

圖G的所有頂點(diǎn)的階數(shù)是偶數(shù)-每塊區(qū)域進(jìn)入與離開(kāi)的次數(shù)相同7.1哥尼斯堡七橋問(wèn)題Euler問(wèn)題有解

圖G是連通的；

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

圖G是連通的；

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

計(jì)算機(jī)證明的正確性如何人工驗(yàn)證？

機(jī)器證明的理論基礎(chǔ)和局限性何在？KennethAppel

和

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

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

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

正交碼組分配問(wèn)題轉(zhuǎn)化為平面圖四色著色問(wèn)題！四個(gè)正交碼組7.2地圖著色問(wèn)題(工程應(yīng)用)衍生問(wèn)題

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

對(duì)于涉及三或四小區(qū)交匯的基站必須采用不同的正交碼組；在這些著色確定的情況下，在對(duì)其它頂點(diǎn)進(jìn)行著色；

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

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

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

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

如果城際旅行中，城市間邊的賦值是旅行時(shí)間，三角不等式將不在成立(由于各城市間旅行交通工具上的差異，例如：如果通過(guò)鐵路旅行，合肥-北京花費(fèi)的時(shí)間肯定比合肥-南京-北京花費(fèi)的時(shí)間成）。這時(shí)的TSP問(wèn)題變成：找出化費(fèi)時(shí)間最少經(jīng)過(guò)每個(gè)城市各一次的旅行路線。歐幾里得TSP問(wèn)題在很多實(shí)際問(wèn)題中，經(jīng)過(guò)每個(gè)城市僅一次的要求可以放松為“經(jīng)過(guò)每個(gè)城市至少一次”，這樣可以對(duì)問(wèn)題的求解帶來(lái)一些方便。7.3旅行商問(wèn)題求解TSP問(wèn)題的求解被證明是NP-hard的，意味著：“隨著城市數(shù)目的增加，任何求最優(yōu)路徑的算法的計(jì)算時(shí)間隨著城市數(shù)目至少是指數(shù)增加的”。因此，各種求解“次最優(yōu)，suboptimal”解的大量的算法應(yīng)運(yùn)而生：

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

遺傳算法方法；

線性規(guī)劃方法；

馬爾科夫鏈方法；…….越是疑難雜癥，“能治”的醫(yī)生越多！上述提到的各種方法都用到了很高深的數(shù)學(xué)理論，如果沒(méi)有現(xiàn)成軟件可利用，很難自己實(shí)現(xiàn)，數(shù)學(xué)建模中碰到類似問(wèn)題，如何解決？！最近鄰算法(NearestNeighborhood算法)=貪婪策略：旅行商總是選擇最近的沒(méi)有訪問(wèn)的城市最為下一個(gè)訪問(wèn)城市。大量的隨機(jī)分布城市實(shí)驗(yàn)表明：算法得到的平均路徑長(zhǎng)度比最短路徑長(zhǎng)25%。7.3旅行商問(wèn)題求解最近鄰算法介紹連通賦值圖的最短路徑問(wèn)題：在一個(gè)連通賦值圖G中，求任意兩點(diǎn)之間的最短路徑。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中可以求出任意兩點(diǎn)之間的最短路徑，所有最短路徑最為兩個(gè)頂點(diǎn)之間連接的邊構(gòu)成了一個(gè)完全圖(任意兩個(gè)頂點(diǎn)之間都有邊相連）。

連通圖中最短路徑的求法已經(jīng)有成熟的算法Matlab2012中的庫(kù)函數(shù)[dist,path]=graphshortestpath(G,S)細(xì)節(jié)看庫(kù)函數(shù)的說(shuō)明。7.3旅行商問(wèn)題求解3450.150.10.120.090.50.20.10.25123450.150.10.120.090.310.20.10.220.30.2112最短路徑構(gòu)成的完全圖13245選擇從1出發(fā)到其他城市的最短路徑可選擇頂點(diǎn){4,5}可選擇頂點(diǎn){2,4,5}7.3旅行商問(wèn)題求解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交通問(wèn)題-有向賦值圖隨著家庭用小汽車在大城市中的日益普及，交通擁堵問(wèn)題變成了大城市的“難治頑疾”?！跋尢?hào)出行”，“單行線”等應(yīng)急措施的出臺(tái)雖有所緩解，但北京城區(qū)的上班族亦然把一天1/8的時(shí)間消耗在路上。“單行線”也使得交通網(wǎng)絡(luò)更為復(fù)雜，很多路段難以實(shí)現(xiàn)“原路返”。交通網(wǎng)絡(luò)描述從“無(wú)向賦值圖”變成了“有向賦值圖”。道路四通八達(dá)，人“四不通”“八不達(dá)”“自行車”笑傲“寶馬”，我走了，你等著7.4交通問(wèn)題-有向賦值圖0.99全是單行道的6個(gè)十字路口的交通線路圖賦值矩陣表示:非零元素稀疏矩陣非對(duì)稱列表表示7.4交通問(wèn)題-有向賦值圖庫(kù)函數(shù)使用交通問(wèn)題中，更多關(guān)心的是從一個(gè)頂點(diǎn)到另一個(gè)頂點(diǎn)的最短路徑問(wèn)題：

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

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

位于湖的兩側(cè)，AB連線過(guò)O，見(jiàn)圖。現(xiàn)擬從A點(diǎn)步行到B點(diǎn)，在不得進(jìn)入湖中的限制下，問(wèn)怎樣的路徑最近。ABOrEFE′F′將湖想象成凸出地面的圓木，在AB間拉一根軟線，當(dāng)線被拉緊時(shí)將得到最短路徑。根據(jù)這樣的想象，猜測(cè)可以如下得到最短路徑：過(guò)A作圓的切線切圓于E，過(guò)B作圓的切線切圓于F。最短路徑為由線段AE、弧EF和線段FB連接而成的連續(xù)曲線（根據(jù)對(duì)稱性，AE′，弧E′F′，F(xiàn)′B連接而成的連續(xù)曲線也是）切線AE,BF,AE’,BF’和弧EF和E’F’圍成的平面圖形有何特點(diǎn)？7.5有障礙最短路徑幾何建模定義2.1（凸集）稱集合R為凸集，若x1、x2∈R及λ∈[0，1]，總有λx1+（1+λ）x2∈R。即若x1、x2∈R，則x1、x2的連線必整個(gè)地落在R中。凸集非凸集凸多邊形非凸多邊形平面凸集的定義7.5有障礙最短路徑幾何建模對(duì)平面凸集R與R外的一點(diǎn)K，存在直線l,l

分離R與K，即R與K分別位于l的兩側(cè)（注：對(duì)高維空間的凸集R與R外的一點(diǎn)K，則存在超平面分離R與K），見(jiàn)圖。凸集分離定理KlRKRp7.5有障礙最短路徑幾何建模由AE、EF、FB及AE′，E′F′，F(xiàn)′B圍成的區(qū)域R是一凸集；設(shè)Γ為最短路徑，Γ過(guò)R外的一點(diǎn)M，則必存在直線l分離M與R，由于路徑Γ是連續(xù)曲線，由A沿Γ到M，必交l于M1，由M沿Γ到B又必交l于M2。直線段M1M2的長(zhǎng)度必小于路徑M1MM2的長(zhǎng)度，與Γ是A到B的最短路徑矛盾；因此最短路徑必然在凸集內(nèi)。最短路徑證明ABOrEFE′F′M1M2MΓl設(shè)路徑經(jīng)湖的上方到達(dá)B點(diǎn)，則弧EF必在路徑上，又直線段AE是由A至E的最短路徑，直線FB是由F到B的最短路徑。7.5有障礙最短路徑幾何建模如果障礙區(qū)域是一個(gè)被封閉曲線包圍的平面凸集，A,B是凸集外的兩點(diǎn)，那么最短路徑必然是包含,A和B的最小凸集的邊界線被A和B分割的兩段曲線中短的一條。

推而廣之-IABAB7.5有障礙最短路徑幾何建模如果障礙區(qū)域是一個(gè)被封閉曲線包圍的平面非凸集，A,B是在包含的最小的凸集外的兩點(diǎn)，那么最短路徑必然是包含,A和B的最小凸集的邊界線被A和B分割的兩段曲線中短的一條。

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