第七講-圖論與幾何模型

第七講:圖論與幾何模型---水鵬朗雷達信號處理國防科技重點實驗室數學建模實驗(數學建模基礎之續(xù))7.1哥尼斯堡七橋問題Euler時代的哥尼斯堡城區(qū)(18世紀)

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

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

圖G的所有頂點的階數是偶數-每塊區(qū)域進入與離開的次數相同7.1哥尼斯堡七橋問題Euler問題有解

圖G是連通的；

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

圖G是連通的；

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

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

機器證明的理論基礎和局限性何在？KennethAppel

和

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

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

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

正交碼組分配問題轉化為平面圖四色著色問題！四個正交碼組7.2地圖著色問題(工程應用)衍生問題

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

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

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

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

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

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

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

神經網絡方法；

遺傳算法方法；

線性規(guī)劃方法；

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

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

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

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

位于湖的兩側，AB連線過O，見圖?，F(xiàn)擬從A點步行到B點，在不得進入湖中的限制下，問怎樣的路徑最近。ABOrEFE′F′將湖想象成凸出地面的圓木，在AB間拉一根軟線，當線被拉緊時將得到最短路徑。根據這樣的想象，猜測可以如下得到最短路徑：過A作圓的切線切圓于E，過B作圓的切線切圓于F。最短路徑為由線段AE、弧EF和線段FB連接而成的連續(xù)曲線（根據對稱性，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的兩側（注：對高維空間的凸集R與R外的一點K，則存在超平面分離R與K），見圖。凸集分離定理KlRKRp7.5有障礙最短路徑幾何建模由AE、EF、FB及AE′，E′F′，F(xiàn)′B圍成的區(qū)域R是一凸集；設Γ為最短路徑，Γ過R外的一點M，則必存在直線l分離M與R，由于路徑Γ是連續(xù)曲線，由A沿Γ到M，必交l于M1，由M沿Γ到B又必交l于M2。直線段M1M2的長度必小于路徑M1MM2的長度，與Γ是A到B的最短路徑矛盾；因此最短路徑必然在凸集內。最短路徑證明ABOrEFE′F′M1M2MΓl設路徑經湖的上方到達B點，則弧EF必在路徑上，又直線段AE是由A至E的最短路徑，直線FB是由F到B的最短路徑。7.5有障礙最短路徑幾何建模如果障礙區(qū)域是一個被封閉曲線包圍的平面凸集，A,B是凸集外的兩點，那么最短路徑必然是包含,A和B的最小凸集的邊界線被A和B分割的兩段曲線中短的一條。

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

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